Questions tagged [fixed-parameter-tractable]

algorithms for parameterized problems where the run-time is polynomial in the input size, but depends arbitrarily on the parameter

Filter by
Sorted by
Tagged with
0 votes
0 answers
154 views

What's the connection between branchwidth and treewidth

I understand that treewidth and branchwidth are essentially equivalent for a fixed graph, given that $branchwidth(G) = Θ(treewidth(G))$. However, my question pertains to a specific case involving ...
Jxb's user avatar
  • 315
-1 votes
1 answer
108 views

Need more explaination on this 'generality'

I am trying to understand how this proof works I don't understand, why this f' is nondecreasing? What kind of generality makes us come up with such kind of assumption? Please, I am weak.
Edee's user avatar
  • 111
-1 votes
1 answer
116 views

Parameters: Twin cover and Vertex cover

I am a research scholar, currently working on parameterized algorithms. I am working on a problem and have been exploring various parameters for which the problem remains unsolved. I have read the ...
Balchandar Reddy's user avatar
0 votes
0 answers
81 views

Tractability with respect to multiple parameters

I am working on the decision version of an NP-complete problem. The problem is known to be fixed parameter tractable(FPT) with respect to the solution size $k$ as the parameter. If I consider another ...
Balchandar Reddy's user avatar
1 vote
0 answers
61 views

The "branch-depth" parameter and its use in FPT algorithms

Let $P=(v_1,\dots,v_q)$ be an induced path in the undirected graph $G(V,E)$. In [1], the authors define the branch depth of $P$ to be $b(P)=|N_G[\{v_1,\dots,v_{q-1}\}]|-1$. Further, in [1] it is shown ...
BBK's user avatar
  • 95
0 votes
1 answer
94 views

Is there FPT or XP algorithms known for Shortest Steiner cycle and $(a,b)$-Steiner path problem

Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems. The Shortest Steiner cycle problem is defined ...
advocateofnone's user avatar
1 vote
0 answers
65 views

Is there an FPT or XP algorithm known for this version of $k$-edge disjoint paths problem?

The shortest $k$-edge disjoint paths problem is defined as follows: Input: An undirected graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Find (if exist) $k$-pairwise ...
advocateofnone's user avatar
2 votes
1 answer
205 views

Maximize a special monotone submodular function - is it easier?

I am looking for a way to optimize the function $f$, defined below. First, fix some positive integer $k$ and let $c_1$ and $c_2$ be non-negative vectors in $\mathbb{R}^n$. Let $g$ be an increasing ...
Karagounis Z's user avatar
0 votes
0 answers
75 views

Parameterized Complexity of Vertex Multicut

Let $G$ be an undirected graph, $\{(s_1,t_1),\dots,(s_k,t_k)\}$ a collection of pairs of vertices, and $p$ an integer. The Vertex Multicut problem asks if there is a set $S$ of at most $p$ vertices ...
BBK's user avatar
  • 95
3 votes
1 answer
157 views

Parameterized algorithm when the parameter is not known in advance?

In the setting of parameterized algorithms, we are typically given the problem instance as well as the value of the parameter. However, it seems like in applications the value of the parameter should ...
Karagounis Z's user avatar
3 votes
0 answers
89 views

Exact FPT Algorithm for Continuous Euclidean $k$-Means

The continuous Euclidean $k$-means problem is defined as follows: Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ ...
Inuyasha Yagami's user avatar
0 votes
0 answers
68 views

Dynamic programming algorithm to find a colorful subset of disjoint sets

Suppose there is a set $F=\{X_1 ,...,X_m\}$, such that $\forall 1\leq i\leq m: |X_i|=3.$ Suppose we color the elements of $\bigcup F$ in $3k$ colors. We wish to know if there is a subset $F'\...
user avatar
2 votes
1 answer
245 views

DFSA and NFSA intersection problem

Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem. For unbounded $k$ it is known the problem is $PSPACE$ ...
Turbo's user avatar
  • 12.8k
17 votes
0 answers
598 views

Linear-time algorithm to test if clique number equals degeneracy bound?

Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique. A well-known bound on the clique number is $\omega\le d+1$, which is ...
Austin Buchanan's user avatar
7 votes
1 answer
167 views

Reducing Parameterized Problems (whose solution size can be "large") to W[i]-complete problems (for fixed i)

Note: Originally, this question was asked via a comment in this question, but was asked to post a separate question. :) I'm looking for any known reductions of the following: Given a parameterized ...
Haden Hooyeon Lee's user avatar
2 votes
1 answer
135 views

Proving membership in W-hierarchy when problem is not parameterized by its solution size

I'm curious about the following general problem: Suppose that we have a parameterized problem whose input is $x$ and parameter is $k$ (which is NOT the size of a solution but something about the input)...
Haden Hooyeon Lee's user avatar
9 votes
1 answer
221 views

What is the best upper bound on the running time of the graph minor algorithm?

A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained ...
Michal's user avatar
  • 91
3 votes
3 answers
972 views

Best parameterized algorithm for maximum clique

I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "...
user2316602's user avatar
2 votes
1 answer
97 views

Diameter vs. Tractability

I would like to find examples of (unweighted) optimization problems $\Pi$ that satisfy 1) or 2): 1) $\Pi$ is NP-hard but polytime solvable in the class of graphs with diameter $\le k$, for all $k\ge ...
Mathieu Mari's user avatar
5 votes
1 answer
515 views

Complexity of SAT parameterized by treewidth

Many papers state that Boolean satisfiability is in FPT when parameterized by primal, dual, or incidence treewidth. What are the best known time complexities of these parameterized algorithms? In ...
Laakeri's user avatar
  • 1,767
14 votes
3 answers
3k views

What is a natural problem in theory of computation?

In Stephen Cook's paper on the P vs NP problem,[1] he states the following [2]: Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm. My question ...
Curious Yogurt's user avatar
3 votes
1 answer
203 views

Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?

I understand that Disjoint Feedback Vertex Set (= looking for a solution $X$ of size $k$ given a solution $W$ of size $k+1$ s.t. $X \subseteq V \setminus W$ ) can be solved in time $4^k poly(n)$, see ...
yassin's user avatar
  • 161
2 votes
0 answers
112 views

Best algorithms for real linear programming

Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of ...
Turbo's user avatar
  • 12.8k
10 votes
0 answers
274 views

Have people looked for parameterized algorithms for problems that are not in NP?

Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the ...
PHD candidate's user avatar
0 votes
0 answers
145 views

What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?

In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$. $KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey ...
Turbo's user avatar
  • 12.8k
3 votes
0 answers
149 views

What are the consequences if $W[i]=W[i-1]$?

$FPT=W[1]$ does not collapse the $W$ hierarchy however falsifies $ETH$ belief. Is there non-trivial consequence if $W[i]=W[i-1]$ and any other consequence at $W[1]$?
Turbo's user avatar
  • 12.8k
9 votes
5 answers
1k views

W[1]-hard problems with FPT time approximation algorithms

I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are: R1. W[1]-hard. R2. Admit a (preferably constant) approximation algorithm ...
R B's user avatar
  • 9,438
1 vote
1 answer
175 views

When we say a parameter is good for a problem?

I am studying parameterized complexity. I have seen few parameterized algorithm for problems like vertex cover, feedback vertex set etc. I have difficulty in determining when a parameter is said to be ...
abaa's user avatar
  • 121
1 vote
0 answers
146 views

Fixed dimension Integer programming minus LLL in fixed parameter $NC$?

If you remove LLL part then is remaining part of a. Lenstra algorithm b. Barvinok algorithm in $O(f(n)(\log(mL))^c)$ time on $O(g(n)(mL)^c)$ processors with fixed $c>0$ in fixed $n$ dimension, $m$ ...
Turbo's user avatar
  • 12.8k
2 votes
1 answer
250 views

Fixed parameter tractable Integer Programming and $FPP$

Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $...
Turbo's user avatar
  • 12.8k
3 votes
1 answer
147 views

Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$...
JFK's user avatar
  • 31
3 votes
0 answers
105 views

Fixed parameter Integer Programming circuit depth complexity

It is well known Lenstra's and Kannan's algorithm achieves $n$-variable parameter $L$-bit integer programming solvability in $O(n^nL)$ time and $O(L)$ space. If implemented as an arithmetic circuit ...
Turbo's user avatar
  • 12.8k
2 votes
0 answers
243 views

Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth

I would like to cite a paper/report/etc that solves the following problem polynomially in $n$: Given a weighted directed graph $G=(V,E)$, $|V|=n$, of bounded treewidth $k \in \mathbb{N}$ and a source-...
cs_student_273's user avatar
3 votes
1 answer
139 views

Consequences of faster parameterized integer programming

Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space. Is there any consequence if it can be done in $k^{O(k^\alpha)}$ time and $O(k^c)$ space for some $\alpha\in(0,1)...
Turbo's user avatar
  • 12.8k
5 votes
2 answers
416 views

On integer programming

Integer programming is NP-hard. What is the status of integer programming problem that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ ...
Turbo's user avatar
  • 12.8k
7 votes
3 answers
711 views

Hard problems for bounded vertex cover

We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?
Kumar's user avatar
  • 2,014
8 votes
2 answers
260 views

Nonstandard dual parametrization of graph problems

One fundamental result in parameterized complexity of graph problems is that VERTEX COVER parameterized by the solution size $k$ is fixed-parameter-tractable (FPT). On the other hand, when ...
Florent Foucaud's user avatar
4 votes
0 answers
95 views

Fixed-parameter tractability of string homomorphism

String homomorphism is a function $h: \Sigma \to \Sigma^*$, which naturally defines a homomorphism on strings from $\Sigma^*$ with respect to concatenation. We denote $H(s) = h(s_1)h(s_2)\dots h(s_n)$ ...
Ivan Smirnov's user avatar
18 votes
0 answers
408 views

Complexity of the homomorphism problem parameterized by treewidth

The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows: Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in $...
a3nm's user avatar
  • 8,916
3 votes
1 answer
597 views

What is the best known FPT result for 3-hitting set?

My research problem involves solving a special instance of the 3-Hitting Set problem, and I was wondering whether my result is actually significant (i.e. if it is better than the best known result for ...
user1441057's user avatar
-6 votes
2 answers
188 views

Fixed parameter tractability [closed]

Lets say I have an algorithm with complexity $O(n^k)$ where $n$ is the size of the input and $k$ is a parameter. Clearly this is superpolynomial; but in fixed parameter tractability we restrict $k$ to ...
Héctor van den Boorn's user avatar
6 votes
2 answers
254 views

Parametrized complexity of the 2-Long Paths Problem

Consider the following problem: Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$...
R B's user avatar
  • 9,438
11 votes
1 answer
435 views

Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas

The k-FLIP SAT parametrized problem is defined as: Input: a 3-CNF formula $\varphi$ with $n$ variables and a truth assignment $\sigma : [n] \to \{0,1\}$ Parameter: $k$ Question: can we transform the ...
Marzio De Biasi's user avatar
10 votes
1 answer
629 views

Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic

Berman–Hartmanis conjecture: all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms[1]. I am interested in a more fine-grained ...
user avatar
15 votes
2 answers
1k views

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

The $k$-cycle problem is as follows: Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges. Question: Does there exist a (proper) $k$-cycle in $G$? Background: For any ...
Michael Wehar's user avatar
10 votes
1 answer
929 views

Complexity of k-clique for hypergraphs

Classic Problem: Let a number $k$ be given. The $k$-clique problem is as follows. Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent? ...
Michael Wehar's user avatar
-1 votes
1 answer
183 views

FPT algorithm equivalent definitions [closed]

On this page, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover. But how the complexity given for Vertex Cover, $O(kn+1.274^k)$ (...
Greg82's user avatar
  • 113
1 vote
1 answer
164 views

Natural maximization problems in FPT

Is there a natural (and hopefully well-known) maximization problem that is known to be in FPT? For instance, Vertex Cover is in FPT, but it's a minimization problem. I'm looking for natural ...
Haden Hooyeon Lee's user avatar
6 votes
1 answer
243 views

Easy decision hard counting Parametrized

It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P. Is there a problem, that exhibits the same behavior in ...
Paramar's user avatar
  • 447
8 votes
2 answers
501 views

Implications of a problem being in XP when parameterized by diameter

Let $X$ be an NP-complete graph problem. Suppose $X$ is solvable in polynomial time on graphs of bounded diameter. In other words, $X$ parameterized by diameter is in XP. (Recall a problem is in XP if ...
Juho's user avatar
  • 3,160