14

There is actually a stronger result; A problem is in the class $\mathrm{FPTAS}$ if it has an fptas1: an $\varepsilon$-approximation running in time bounded by $(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$ (i.e. polynomial in both the size and the approximation factor). There's a more general class $\mathrm{EPTAS}$ which relaxes the time bound to $f(\frac{1}{\...


9

The problem you are describing is known as Component Order Connectivity in the field of vulnerability measures of graphs. The decision version of the problem is as follows: Component Order Connectivity: Input: Graph $G = (V,E)$, integers $k$ and $\ell$ Question: Does there exist a set of vertices $X \subseteq V$ of size at most $k$ such that ...


8

If you want an FPT algorithm for the problem (parameterized by treewidth $t$), you want an algorithm working in time $f(t) \cdot n^{O(1)}$, where $f$ is any computable function (depending solely on $t$). Of course, it would be nice to make $f$ as appealing as possible. In addition to the mentioned algorithm running in $O(t^t n)$ time, you can also get a ...


8

Intuitively, a kernelization algorithm is an algorithm which in polynomial time preprocesses a given instance and outputs an instance whose size is bounded in the parameter. The goal of kernelization is (at least) two-fold. We get provable performance guarantees, i.e., we can prove upper bounds on the output instance, which has applications both in the ...


7

The search with the running time of $2^kn^{O(1)}$ is a different one. Personally, I would not have chosen to call it an exhaustive search. Not that it is incorrect, but as the question shows it may be misleading. The classic algorithm goes as follows: If all edges are covered, succeed. If you already have chosen $k$ vertices, fail. Consider the first ...


6

The algorithm should say "choose $p \in S'$", that is, the text is the correct version, rather than the pseudocode. Note how the algorithm works: $S',S_{1},\ldots,S_{k}$ form a partition of $S$ (i.e. every element of $S$ is in exactly one of $S',S_{1},\ldots,S_{k}$). At each step it chooses which $S_{i}$ to put $p$ into. Initially $S' = S$, and $S_{i} = \...


5

There is an outline of the algorithm you want in these slides: http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2. Given a nice-tree decomposition of width $w$ for $G$, the algorithm runs in time $O(w^w \cdot n)$. As it is based on a nice-tree decomposition, you will need to show what happens in the case of a forget node, an introduce node, and a join node ...


5

You are certainly right that the level of rigor found in old papers making such claims can be a bit low at times when viewed from today's perspective. The claim is correct anyway, even if it does not follow from Sistla/Clarke's proof. The reason is that LTL satisfiability checking is also PSPACE-complete. You can see satisfiability checking as a special ...


4

Well, you can always solve it in XP time by trying all possible $k$-sets. In fact, it was shown by Pătraşcu and Williams [1] that there is no $O(n^{k-\varepsilon})$-time algorithm for $k$-dominating set for any $\varepsilon > 0$, assuming SETH. This is almost tight as for $k \geq 7$, the problem can be solved in $n^{k+o(1)}$ time (see [1]). As a special ...


4

No. The typical reduction from Independent Set to Vertex Cover doesn't preserve the parameter ($k$). A graph with a vertex cover of size $k$ has an independent set of size $n-k$, so we no longer have $n$ restricted to the polynomial part. This separation is one of the basic conjectures of Parameterized Complexity. Parameterized Complexity is a bivariate ...


4

Hint: Show that an FPTAS for $Q$ implies a polytime algorithm for $L_Q^*$. This contradicts the assumption $P \neq NP$, which is missing from your question but seems to be tacitly assumed.


4

Courcelle's Theorem is one of the things that is better explained (compared with Niedermeier's book) in the book of Flum and Grohe (see the treewidth chapter), since model checking problems etc. are covered in detail there. By the same authors and Frick there is also a generalization of Courcelle's Theorem: Query evaluation via tree-decompositions. You ...


4

There's a soft introduction in Rolf Niedermeier's book Invitation to Fixed Parameter Algorithms. Daniel Marx also has quite a few slides available on his homepage that contain short examples of modeling a problem in MSOL. One set of relevant slides is here. For more links, see a related question on CSTheory.


4

There is a slightly different description for XP which I personally find less misleading: "Polynomial time for each parameter". I believe the zoo page uses FPT instead of P for some formal reasons (parameterized problems are sometimes defined as subsets of $\Sigma^*\times\Pi^*$, classical problems as subsets of $\Sigma^*$). It can be noted that both ...


4

The way you state it, a slice of an parameterized problem is the problem where we use some fixed constant for our problem parameter, instead of a 'free' variable. In a sense, we are only considering the subfamily of the problem for this particular constant, which is probably the logic behind the name 'slice'. Indeed, if a problem $(Q,\kappa)$ is fixed ...


4

The formal problem is: Input: A planar graph $G = (V, E)$ and an integer $k$ (the parameter) Question: Does $G$ have an independent set of size at least $k$? A kernelization algorithm for Planar IS with $4k$ vertices. Recall that we can obtain a four-coloring of $G$ in polynomial time. That is, we get a partitioning of your vertex set $V$ into $V_1, V_2, ...


4

Consider the Graph Coloring problem. Let $k$-Colorability be the language defined as follows. $\{(G, k)\ | \ \text{$G$ is a $k$-colorable graph}\}$ Given $\ell \in \ \mathbb{N}$, the $\ell$-th slice of $(G, k)$ is the problem: $\{(G, k)_\ell | \ \text{$G$ is a $k$-colorable graph and $k=\ell$}\}$ As you mention, a slice of an FPT problem is solvable in ...


3

Firstly, there is an important part of the quoted statement you are missing - the parameterization. It can only be classified with respect to some parameterization. For example, Dominating Set is $\mathrm{W}[2]$-complete when parameterized by $k$, the size of the dominating set, but it is in $\mathrm{FPT}$ when parameterized by the treewidth of the input ...


3

I believe this is FPT. FInding a $(n - k)$-clique is equivalent to finding an independent set of size $n - k$ on the complement. This is equivalent to finding a vertex cover of size $k$. And the latter is FPT.


3

$\mathrm{W}[1]$-hardness implies that a problem has no eptas unless (at least) $\mathrm{W}[1] = \mathrm{FPT}$ (having an eptas implies parameterized tractability for the standard solution size parameterization), but there are problems with a ptas that are $\mathrm{W}[1]$-hard (i.e. not $\mathrm{APX}$-hard unless $\mathrm{APX} = \mathrm{PTAS}$). Transferring ...


3

I'm not sure there are any really simple solutions. One algorithm is due to Fernau, and uses an enumeration of all vertex covers of size $2k$; within each of these, a simple dynamic programming algorithm attempts to find a small edge dominating set. Another (earlier) approach, due to Prieto, uses kernelization.


3

It is $NP$-complete. Consider a graph $G$ which is modified by duplicating every vertex, and connecting every duplicate vertex to its original. Then if we constrain all the duplicate vertices to a fixed color, then the thus obtained graph is 4-colorable (with constraints) if and only if the original graph is 3-colorable.


3

Yes, it's exactly the same class. You can take any constant size list of parameters and combine them just using addition. This is particularly obvious in Flum and Grohe's formulation of $FPT$ where problems are equipped with a parameterization $\kappa : x \rightarrow \mathbb{N}$. So for example, you can take a problem with two parameters $k$ and $r$, and ...


2

Yes, consider the clique problem (W[1]-hard for the parameter solution size). The problem is FPT when parameterized by the vertex cover number: any clique can contain at most one vertex outside the vertex cover, so it is enough to look at only $2^\tau(n-\tau+1)$ possible solutions, where $\tau$ is the vertex cover number. On the other hand, the clique ...


2

To add to the other answer, the name of the problem you are interested in is precoloring extension: given a graph $G$ with some precolored vertices and a color bound $\ell$, can the precoloring of $G$ be extended to a proper coloring of all vertices of $G$ using not more than $\ell$ colors? This problem is NP-complete for planar bipartite graphs with fixed $\...


2

As Pål GD mentions, the requirement that $l(y)\leq g(k(x))$ is necessary to obtain reductions with the proper result. In particular, the property 'If $X$ is FPT, and there is an FPT-reduction from $Y$ to $X$ then $Y$ is FPT'. An example to see why this requirement is necessary is to consider reductions between $k$-Clique and $k$-Vertex cover. Recall that ...


2

First, let me note that the claim, as stated in the question, is false: Consider the following graph: $\begin{matrix} & & 2& - & 3\\ & \diagup\\ 1 & & | & & |\\ & \diagdown \\ & &4 &-& 5 \end{matrix} $ The complete graph on $5$ vertices is a chordal completion of this graph. However, this graph ...


2

It seems your confusion comes from the fact that Lemma 5.5 is a bit of a strange statement. In fact, we can replace Lemma 5.5 with the statement that for any problem $B$ such that $B_Y$ is a yes-instance of $B$ and $B_N$ is a no-instance of $B$ we have that $A\leq_{\mathrm{fpt}}B$. The proof of this adapted lemma is precisely the same as Lemma 5.5, only now ...


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