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 ...
user avatar
15 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 ...
user avatar
  • 7,052
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 ...
user avatar
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 ...
user avatar
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$...
user avatar
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 ...
user avatar
  • 5,225
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 ...
user avatar
  • 1,422
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 ...
user avatar
  • 5,225
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 $...
user avatar
  • 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 ...
user avatar
  • 190
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 3,236
8 votes
Accepted

Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?

Our recent paper shows that counting k-matchings is #W[1]-hard even in bipartite graphs. This answers your question. Radu Curticapean, Dániel Marx: Complexity of counting subgraphs: only the ...
user avatar
  • 1,968
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!). ...
user avatar
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 ...
user avatar
  • 5,225
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" ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 1,855
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 ...
user avatar
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 ...
user avatar
  • 1,855
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 ...
user avatar
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$...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 3,236
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 ...
user avatar
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; ...
user avatar
  • 10.4k
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible