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
If you require only that the growth rate be a polynomial in $n$ for fixed $k$, then you get the definition of the parameterized complexity class XP, which is certainly an object of interest, so there's nothing wrong with considering it.
You get the definition of FPT if you further impose the condition that the degree of the polynomial in $n$ remains fixed ...
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] = \...
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
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
In his dissertation thesis "Modifizierte parametrische Komplexitatstheorie", Mark Weyer considered, among other things, hierarchies within FPT w.r.t. the function f and reductions between them. He also did indeed relate these sub-hierarchies to fragments of FO and MSO: Chapter 6 is essentially about the relation between FO/MSO (the number of quantifier ...
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 ...
12
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 ...
11
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 ...
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
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
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
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
The complement problems Minimum (Edge) Bipartization and MaxCut are both in FPT, so the conjecture is false.
9
It is possible to prove the fixed-parameter tractability of various graph-theoretical problems (e.g., finding a path of length k or finding k disjoint triangles) using algebraic techniques by reducing the problem to questions about certain polynomials. See for example the following very readable paper by Ryan Williams:
http://arxiv.org/abs/0807.3026v3
and ...
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
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')|$. ...
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 $...
7
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]$-...
Only top voted, non community-wiki answers of a minimum length are eligible
