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-...
23
A good place to start is "Parameterized Complexity Theory" by Jörg Flum and Martin Grohe, published by Springer.
17
Sorry for the self-advertisement, but this spring we have been developing a hybrid undergrad/grad course at Stanford on Parameterized Algorithms and Complexity. We've tried to "re-do" many of the proofs of the core theorems in the literature, in a way that's somewhat more accessible to undergraduates. The scribe notes are (mostly) online. However we have not ...
15
An (optimal) $r$-domination for $G$ is an (optimal) domination for the $r$th power $G^r$ and vice versa
($G^r$ is obtained from $G$ by adding new edges between distinct vertices of distance at most $r$).
The following facts are well known: (1) All powers of a strongly chordal graph are strongly chordal
(A. Lubiw, Master thesis; see also Dahlhaus & ...
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
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] = \...
14
Daniel Marx has several interesting talks on FPT and related topics on his website.
http://www.cs.bme.hu/~dmarx/
http://www.cs.bme.hu/~dmarx/talk.php
See also the recent collection of essays/book on the occasion of the 60th birthday of Mike Fellows.
http://link.springer.com/book/10.1007/978-3-642-30891-8/page/1
Update (Nov 2014): Marek Cygan et al (long ...
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 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 ...
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
It is quite easy to do dynamic programming on graphs of treewidth $k$ for this problem.
One can keep for each vertex in a bag the shortest distance to some vertex in the partial solution and the distance to future solution needed to dominate the undominated vertices.
This in total gives a table size of $O(r^k)$ so for fixed $r$ this problem is FPT ...
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
See http://fpt.wikidot.com/books-and-survey-articles.
I also prefer Flum and Grohe, especially for the hardness part, whereas the book by Niedermeier is more focused on the algorithmic side. Note that there are some technical differences between the two, for instance the definition of a parameter as polynomial time computable function in the book of Flum and ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
