29
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 one more edge than the minimum length cycle. (See the first three sentences of the abstract here: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-...
15
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 mechanics while integration is art", they're not inviting you to formalize "mechanics" and "art" and prove the statement, they're trying to convey a general ...
14
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 have communicated this problem to many people, and taught it in cs266 at Stanford, due to its connection to solving $k$-Sat. (Several open problem sessions at ...
14
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 strict under the assumption $\mathrm{FPT} \neq \mathrm{W[P]}$?
For $t \geq 1$, does the equality $\mathrm{W}[t] = \mathrm{W}[t + 1]$ imply $\mathrm{W}[t] = \...
13
For the second question: Fixing rank-width (equivalently, fixing clique-width), polynomial time solvability of GI is not known. Recently, Mamadou Kanté posed an open question if the graph isomorphism problem can be solved in polynomial time for graphs of bounded linear rank-width.
13
For the first question: Graph Isomorphism has been considered for at least the following parameters for which fixed-parameter tractability is still open.
pathwidth / treewidth (see [2], has been asked here), maybe solved: http://arxiv.org/abs/1404.0818
cutwidth / bandwidth [1]
treewidth-k vertex deletion set size (feedback vertex set number in [7])
tree / ...
13
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$ is the exponent for fast matrix multiplication. For 4-cycle-free graphs, plugging in $\omega<2.373$ and $m=O(n^{3/2})$ (else there is a $4$-cycle ...
13
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 OR-cross-composes into the k-FLIP-SAT problem; by the results in the cited paper, this is sufficient. Concretely, we build a polynomial-time algorithm whose ...
13
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 neighborhood of the vertex.
Therefore, if we omit polynomial factors, the time complexity of maximum clique in graphs with degree at most $d$ is the same as ...
11
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 vertices $s$ and $t$ is a rooted minor of a graph $G$ with roots $s$ and $t$, iff there is a function $f \colon V(H) \to 2^{V(G)}$ which assigns to each vertex of $...
10
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 $\#W[1]$-hard.
A more interesting example (decision is even in $P$ while counting is parameterized-hard) would be counting $k$-matchings in bipartite graph.
...
10
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 implies being in XP for parameters: min dominating set, max independent set, minimum clique cover, distance to cograph, distance to co-cluster, distance to clique, ...
10
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 Wahlström.
9
Dawar and Kreutzer have shown that the problem is fixed-parameter tractable on nowhere dense classes of graphs, which includes the planar graphs, the graphs of bounded (local) tree-width and all classes with (locally) excluded minors.
Dvorak has shown that there is a polynomial time constant factor approximation for classes of bounded expansion, which ...
9
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 Robertson and Seymour. NP-Hard for $k=2$ when $G$ is directed - from work of Fortune, Hopcroft and Wylie (1980).
9
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 and remove them from the graph. We now have a graph $G'$ with $|E(G')|\le |E(G)|-2k$. It is easy to find a vertex cover of $G'$ with size at most $|E(G')|$. ...
9
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 parameterized version we are also given an integer $k$ and asked whether a solution of size at most $k$ exists.
In this paper we prove that (R1) the problem is W$[1]$-...
8
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 boundedness of the vertex-cover number counts. CoRR abs/1407.2929 (2014)
7
$(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!). The problem here is to select $k$ vertices (centers) so that all other vertices are at distance at most $r$ from the closest center. This generalizes $k$-...
7
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 corresponds to a constraint $x_1 + x_3 + (1-x_4) + (1-x_6) \geq 1$, when all variables are forced to take values $0$ and $1$.
Hence if integer programming in $...
6
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" problem, and it was proved W[1]-hard (parameterized by the number of vertices) by Bodlaender, myself and Penninkx, even on planar graphs.
Input is a simple directed ...
6
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 a nutshell, an ideal parameter $k$ for a problem should give you two things:
The problem is fixed-parameter tracable for parameter $k$ with a good running ...
6
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 Scheme) but it is known that MaxSAT parametrized by clique-width (resp. neighbor diversity) is W[1]-hard.
The theorem mostly relies on a result of [2] that roughly ...
6
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 graph of maximum degree at most $\Delta^*$. (If $\Delta^*=0$ this problem is just Coloring).
In [1] we showed the following regarding this problem parameterized ...
6
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 size of a reasonable encoding of a CNF $F$, $k$ is the (primal/incidence) treewidth and $c$ and $d$ are constants.
In this answer, I will denote by SAT(ptw) the ...
5
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$
clauses?
Max Leaf: Does $G$ have a spanning tree with at least $k$
leaves?
Longest Path / Cycle: Does $G$ contain a simple path / cycle on at least $k$
...
5
For the third question: The survey paper of Brandstadt, Le, and Spinrad, Graph Classes: A Survey, SIAM, 1999, contains several graph classes for which GI-completeness is not known. One such class is trapezoid graphs. Another class is circular arc graphs which is mentioned as open problem in the introduction of the paper, Tractabilities and Intractabilities ...
answered Dec 20 '13 at 13:50
Mohammad Al-Turkistany
20.5k4 gold badges57 silver badges144 bronze badges
5
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 input a graph $G$, an integer $r$, and a tree-decomposition of $G$ of width $w$, computes an optimal $r$-dominating set of $G$ in time $O((2r+1)^wn)$.
...
5
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 logarithmic depth. The result is given in the paper "Graph operations characterizing rank-width and balanced graph expressions" by Courcelle and Kanté, WG '08. I quote ...
Only top voted, non community-wiki answers of a minimum length are eligible