29
votes
Accepted
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
Yes, this is known. It appears in one of the must-cite references on triangle finding...
Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most ...
- 26.7k
16
votes
Accepted
What is a natural problem in theory of computation?
To be clear, it's not meant to be formalizable. It's not a theorem, it's an observation about the world -- it's okay if "natural" is subjective here. For analogy, if someone says "differentiation is ...
- 7,140
14
votes
Accepted
FPT vs W[P] - Parameterized Complexity
This question is tricky as the answer (as far as I know) is still "don't know".
To add some weight to this, Flum & Grohe [1] give as open problems (p. 164):
Is the $\mathrm{W}$-hierarchy ...
- 1,158
14
votes
Accepted
Complexity of k-clique for hypergraphs
It is not known if there is an $\varepsilon > 0$, $c > 2$, and $k > c$ such that $(c,k)$ hyperclique is in $n^{k-\varepsilon}$ time. Note that the case of $k \leq c$ is trivial. For years I ...
- 26.7k
13
votes
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
It's not quadratic, but Alon Yuster and Zwick ("Finding and counting given length cycles", Algorithmica 1997) give an algorithm for finding triangles in time $O(m^{2\omega/(\omega+1)})$, where $\omega$...
- 50.5k
13
votes
Accepted
Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas
The problem does not have a polynomial kernel unless NP is in coNP/poly. The cross-composition technique from our paper applies in a nontrivial way.
Let me show how the classic Vertex Cover problem ...
- 5,245
13
votes
Accepted
Best parameterized algorithm for maximum clique
Maximum clique in graphs with degree $d$ can be reduced to $n$ instances of maximum clique in a graph with at most $d$ vertices: for each vertex, compute maximum clique in the induced subgraph of the ...
- 1,527
11
votes
Accepted
Parametrized complexity of the 2-Long Paths Problem
Your problem is fixed-parameter tractable, which follows from the heavy machinery of Robertson & Seymour. Your problem can be stated in terms of rooted minors. A graph $H$ with designated root ...
- 5,245
10
votes
Accepted
What is the best known FPT result for 3-hitting set?
According to the Parameterized Complexity Wiki, the currently best known FPT algorithm for 3-Hitting-Set has a complexity of $2.076^k \cdot n^{O(1)}$, the algorithm is from the PhD thesis of Magnus ...
- 4,511
10
votes
Accepted
Easy decision hard counting Parametrized
Finding $k$-path (simple paths of length $k$) in a graph is in $FPT$ and can be done in $O^*(2^k)$ with a randomized algorithm or $O^*(2.62^k)$ deterministically.
This is while Counting $k$-paths is $...
- 9,378
10
votes
Accepted
Implications of a problem being in XP when parameterized by diameter
I think Figure 1 (page 4) of the paper "New Races in Parameterized Algorithmics" of Komusiewicz and Niedermeier is what you are looking for.
In particular, being in XP for the parameter diameter ...
- 190
9
votes
Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?
The disjoint paths problem: given $G$ and $k$ pairs of nodes, are there node disjoint paths connecting the given pairs. Parameterized by $k$, in FPT when $G$ is undirected from the seminal work of ...
- 6,754
9
votes
Nonstandard dual parametrization of graph problems
I think this problem is FPT. Suppose that the graph contains a path on $2k+1$ vertices. Then, I claim the answer is YES: we select the second, fourth, sixth, etc. vertices of this path in a solution ...
- 3,156
9
votes
Accepted
W[1]-hard problems with FPT time approximation algorithms
In the Directed Odd Cycle Transversal problem the input is a graph $G$ and the task is to find a smallest set $S$ of vertices such that $G-S$ has no (directed) cycles of odd length. In the ...
- 3,236
7
votes
Hard problems for bounded vertex cover
$(k,r)$-center is another (arguably natural) problem that is $W[1]$-hard parameterized by vertex cover. (See a recent preprint by Katsikarelis, me, and Paschos here - sorry about the self-promotion!). ...
- 3,156
7
votes
Accepted
Consequences of faster parameterized integer programming
An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally ...
- 5,245
6
votes
Hard problems for bounded vertex cover
Here is a problem (with lists!) which is known to be W[1]-hard parameterized by Vertex Cover (indeed, even by the number of vertices in the input graph). The problem is known as the "Arc Supply" ...
- 3,236
6
votes
When we say a parameter is good for a problem?
In my opinion, this is actually one of the main questions in parameterized algorithms. There is a number of articles that discuss the "art" of problem parameterization, I list a few of them below.
In ...
- 1,670
6
votes
W[1]-hard problems with FPT time approximation algorithms
In [1], the authors prove that MaxSAT parametrized by the clique-width (resp. neighbor diversity) of the incidence graph of the CNF formula has an FPT-AS (Fixed Parameter Tractable Approximation ...
- 2,049
6
votes
W[1]-hard problems with FPT time approximation algorithms
In Defective Coloring we are given a graph $G$ and an integer $\Delta^*$ and are asked to partition the vertices of $G$ into the minimum possible number of color classes so that each class induces a ...
- 3,156
6
votes
Accepted
Complexity of SAT parameterized by treewidth
FPT results
The complexity of SAT, #SAT and MaxSAT parametrized by primal and incidence treewidth is FPT for all cases and of the form $2^{ck}\|F\|^d$ where $\|F\|=\sum_{C \in F} |var(C)|$ is the ...
- 2,049
5
votes
On integer programming
It's NP-hard. Given an integer programming problem $P$, add an irrelevant variable $z$ with no constraints; call the resulting problem $P'$. Now if $P$ has no solutions, then $P'$ has no solutions; ...
- 11k
5
votes
Accepted
On integer programming
(1) As finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete (indeed, it is $\mathsf{ASP}$-complete, see Theorem 3.5 of [1]), and we can encode 3SAT as an integer ...
- 36.1k
5
votes
Accepted
Nonstandard dual parametrization of graph problems
Let $n:=|V(G)|$ and $m:= |E(G)|$. The dual parameter $m-k$ is always at least as large as $m-n$ which in turn is at least as large as the size of a feedback edge set, a set of edges whose removal ...
- 1,670
5
votes
Accepted
Natural maximization problems in FPT
Here are a few:
Max Cut: Can one color the vertices of an input graph $G$ black and white so that at least $k$ edges go from black to white?
Max Sat: Is there an assignment that satisfies at least $k$...
- 3,236
5
votes
Clique-width expressions with logarithmic depth
After a while I found an answer in the literature, so I'm posting it here in case it is useful to someone else.
It is in fact possible to re-balance clique-width expressions so that they have ...
- 3,156
5
votes
Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs
There is a recent paper by Glencora Borradaile, Hung Le: Optimal Dynamic Program for r-Domination Problems over Tree Decompositions (IPEC 2016). Here they show that there is an algorithm that given as ...
- 3,236
5
votes
Accepted
Fixed parameter tractable Integer Programming and $FPP$
You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are ...
- 386
5
votes
W[1]-hard problems with FPT time approximation algorithms
The k-cut problem is to remove a minimum number of edges to create at least k components. W[1] hard when parameterized by k but admits a 2-approximation for any k.
- 6,754
Only top scored, non community-wiki answers of a minimum length are eligible