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
54
questions
10
votes
2answers
2k 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 ...
3
votes
1answer
125 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 ...
2
votes
0answers
80 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 ...
10
votes
0answers
239 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 ...
0
votes
0answers
112 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 ...
3
votes
0answers
129 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]$?
8
votes
4answers
265 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 ...
1
vote
1answer
118 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 ...
1
vote
0answers
94 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$...
1
vote
1answer
182 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 $...
3
votes
1answer
132 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$...
3
votes
0answers
103 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 ...
2
votes
0answers
127 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-...
3
votes
1answer
130 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)...
5
votes
2answers
361 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$ ...
7
votes
3answers
544 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?
8
votes
2answers
211 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 ...
4
votes
0answers
83 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)$ ...
16
votes
0answers
290 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 $...
3
votes
1answer
314 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 ...
-6
votes
3answers
150 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 ...
6
votes
2answers
227 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$...
9
votes
1answer
290 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 ...
10
votes
1answer
502 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 ...
15
votes
2answers
806 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 ...
8
votes
1answer
385 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?
...
-1
votes
1answer
129 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)$ (...
1
vote
1answer
142 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 ...
6
votes
1answer
220 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 ...
8
votes
2answers
464 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 ...
3
votes
0answers
110 views
Multiple knapsack fpt?
It was an open question whether multiple knapsack is fpt wrt standard
parameter. Since at SODA 2009 Jansen has presented an EPTAS for
multiple knapsack and an EPTAS implies the existense of an fpt ...
7
votes
0answers
145 views
Is 4-colors precoloring extension for planar graphs fixed parameter tractable?
Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable).
Assume you are given a set of $k$ constraints of the form "$v_i \text{ is ...
10
votes
2answers
355 views
Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?
Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), I was wondering how parameterized problems are affected by these attributes.
...
4
votes
1answer
368 views
FPT algorithm for mixed integer program
It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer ...
1
vote
1answer
95 views
Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm
EDIT: I'm sorry if this question belongs more to cs.SE, I've had a dilemma about where to put it. Please let me know if it's inappropriate.
I'm currently implementing the Vertex Cover problem solving ...
7
votes
2answers
200 views
Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?
The $q$-Dimensional $p$-Matching is defined as follows:
Given disjoint universes $U_1,\ldots,U_q$, think
of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element
from ...
1
vote
1answer
206 views
Node-weighted steiner problem with few terminals
Consider the node-weighted steiner problem:
Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$.
Output: a minimum weight subset ...
5
votes
0answers
125 views
Is minimum weight simple cycles through specified vertics fixed parameter tractable?
The problem formulation is as follows:
Input: Undirected graph $G=(V,E)$, a set of vertices $S\subseteq |V|$, a weight function $w:E\to \mathbb{R}$ and a threshold $T\in \mathbb{R}$.
Parameter:...
4
votes
1answer
355 views
Vertex disjoint simple paths of length k
A lot of effort has been invested in finding simple k-paths, as well as in finding vertex disjoint paths.
Is there any known parametrized algorithm that given a graph $G=(V,E)$, decides whether there ...
15
votes
1answer
214 views
Clique-width expressions with logarithmic depth
When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree ...
18
votes
4answers
1k views
Open problems related to Graph isomorphism
Presently I am doing literature survey on Graph isomorphism (GI) problem.
I would like to know some open questions related to the following
What are the graph parameters for which fixed parameter ...
4
votes
1answer
497 views
On Random Self-reducible properties
Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$.
1) Is $k$-sum random self-reducible?
That ...
14
votes
5answers
938 views
Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs
Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in $S$...
18
votes
7answers
1k views
Books/Lecture Notes on Parametrized Complexity
I would like to learn about Parametrized Complexity (both on the algorithmic side and on the hardness side). What books/lecture notes can I read on this subject?
10
votes
1answer
352 views
What is the motivation behind the definition of fixed parameter tractability?
Wikipedia writes:
FPT contains the fixed parameter tractable problems, which are those
that can be solved in time $f(k)\cdot|x|^{O(1)}$ for some computable function $f$. Typically,
this ...
7
votes
3answers
483 views
Algebraic formulation for packing problem
My question is regarding the algebraic formulation for packing problems in graphs.
Taking an example, suppose I am interested in the problem of finding if there is a packing of k edge disjoint ...
2
votes
1answer
232 views
Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$
By "complement problems", I mean the two problems' objective functions are complement. For example, the vertex cover and its complement independent set in this sense. For a graph $G(V,E)$, their ...
7
votes
2answers
491 views
Variants of Cluster-Vertex-Deletion problem
The Unweighted Cluster-Vertex-Deletion problem is the following:
Input: An undirected graph G = (V, E) and a nonnegative number k
Output: Is there a subset X ⊆ V with |X| ≤ k such that deleting all ...
13
votes
1answer
241 views
Elementary bounds on parameter in fixed-parameter tractability?
In the definition of (strong) fixed-parameter tractability, the time bound is an expression of the form $$f(k).p(|x|),$$ where the input instance is $(x,k)$ with parameter $k$, $p$ is a polynomial, ...
19
votes
1answer
510 views
FPT vs W[P] - Parameterized Complexity
In parametrized complexity, $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$. It is conjectured that each of the containments is proper.
If $...
