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 ...


17

Predicting the future is nigh impossible, especially so for cutting-edge research. I don't think anyone predicted how much impact deep learning is now having or that cryptography would be taken over by indistinguishability obfuscation. That said, I will say this much: I don't see any particular reason to expect parameterized complexity to take over. It's a ...


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 & ...


14

Consider the parity function (or any other function that depends on all/most bits of the input). For the parity function, $T(w) = \Theta(|w|)$. So $$f_n = \Theta(n).$$ On the other hand, $$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$ Note that $K(2^{2^n}) = O(n)$. Thus $$...


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

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even for fixed $E_1$, since language universality corresponds to $E_1=\Sigma^*$. It is indeed hard to find a modern readable PSPACE-hardness proof for regular ...


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

I believe the title of this paper is self-explanatory and answers your question: On product covering in 3-tier supply chain models: Natural complete problems for W[3] and W[4]


12

Answering my own question, there's now a preprint on arXiv showing that double-exponential is the correct dependence, assuming the exponential time hypothesis. See "Known algorithms for EDGE CLIQUE COVER are probably optimal", Marek Cygan, Marcin Pilipczuk, and Michał Pilipczuk, arXiv:1203.1754 and SODA 2013


12

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

From the comment above: $p$-HYPERGRAPH-(NON)-DOMINATING-SET is W[3]-complete under fpt-reductions: A hypergraph $H = (V,E)$ consists of a set $V$ of vertices and a set $E$ of hyperedges. Each hyperedge is as subset of $V$. In a 3-hypergraph all edges have size 3. If $H = (V,E)$ is a 3-hypergraph, every $a \in V$ induces a graph $H^a = (V^a, E^a)$ given by: ...


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

My favorite resource for this subject is the book Sparsity by Jaroslav Nešetřil and Patrice Ossona de Mendez. It has quite a bit of material specifically about tree-depth, including algorithmic aspects. And for a more brief and quick introduction, there's always the Wikipedia article.


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

Given the interest in this question, I thought it might be helpful to point out more explicitly the reason we should not be at all surprised by the answer and try to give some direction for refinements of the question. This collects and expands on some comments. I apologize if this is "obvious"! Consider the set of strings of Kolmogorov complexity $n$: $$J^...


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

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

Ball and Trap I remains $W[1]$-hard when restricted to binary trees. Theorem 5 states: Theorem 5. Ball and Trap I remains $W[1]$-hard restricted to binary trees, the maximum number of traps per vertex is one per color, and balls are placed on neither leaves nor parents of leaves.


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

Correction: I have claimed (see below) that "Independent Dominating Set" is a special case of ExactCover. This claim was wrong, as two vertices in the ind-dom set may have overlapping neighborhoods. In fact, "Exact Cover" is contained in W[1]. It is recognizable by a tail-nondeterministic RAM (as introduced by Flum & Grohe), and therefore lies in W[1]: ...


7

Currently, I would say the 3 major open cases are: Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution Planar Vertex Deletion (make a graph planar by deleting at most k vertices) Edge Multiway cut (given an undirected graph and a list of terminals, delete at most k edges to ...


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

There are bounded degree (in fact even cubic i.e. 3-regular) expanders on $m$ vertices with treewidth at least $\epsilon \cdot m$, for some constant $\epsilon > 0$. See Section 2 in: Martin Grohe, Dániel Marx: On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99(1): 218-228 (2009) Basically, they prove something much stronger: large ...


6

For a constant $d$ the $(k,d)$-hitting set problem is not harder than the original $d$-hitting set (i.e. $k=1$) in view of both approximation and parametrized complexity. There is a simple reduction from $kd$-HS to $d$-HS. For an instance $(U,\mathcal{F},d,k)$ of the first problem we get an instance of $(U',\mathcal{F'},d)$ of the second one in which every ...


6

The difference between your definitions is that the clause width in $s_\omega$ is allowed to grow with the number of variables, while for $s_\infty$ it is arbitrarily large but constant. It's a similar issue as PH vs PSPACE. If you take an arbitrary constant number of quantifier alterations you get the polynomial hierarchy, but if you allow the formula to ...


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