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
61
questions
15
votes
0answers
453 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 ...
7
votes
1answer
125 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 ...
2
votes
1answer
90 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)...
9
votes
1answer
202 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 ...
3
votes
3answers
512 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 "...
2
votes
1answer
95 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 ...
4
votes
1answer
259 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 ...
11
votes
2answers
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 ...
3
votes
1answer
139 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
86 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
247 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
125 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
140 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]$?
9
votes
5answers
626 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
134 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
103 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$ ...
1
vote
1answer
215 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
140 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
104 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
172 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
132 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
379 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
630 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
226 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
84 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
316 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
408 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
155 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
240 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$...
11
votes
1answer
331 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
579 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
988 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 ...
9
votes
1answer
554 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
157 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
151 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
229 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
480 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
122 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
147 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
402 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
408 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
97 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
213 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
213 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 $S \...
5
votes
0answers
128 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: $|S|=...
4
votes
1answer
392 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
254 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
544 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
1k 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$...
