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} = \...


6

There are a few examples in the answer to Natural complete problems in higher levels of the W-hierarchy. In particular, the W[3]-complete problem $p$-HYPERGRAPH-(NON)-DOMINATING-SET may be useful for your proof. Given that the linked question is now almost 6 years old, you'd perhaps expect some more examples to pop up by now. However, I couldn't find ...


6

You have to be a bit careful with your question here. Note that an NP-hard problem is a decision problem, while FPT algorithms solve parametrized decision or search problems. So the question is a bit poorly formed. However, I think the question you probably intended to ask is: Is there an NP-hard problem for which we can add a parameter1 to create a "...


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

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


5

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.


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

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

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

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.


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

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


4

Reduction Rule 1. Let $V$ be the set of vertices which are isolated. Convert the instance from $I = (G,k,d)$ to $I^{'} = (G -V, k,d)$. If $I^{'}$ is a yes instance, then so is $I$, because adding back the isolated vertices do not add on to the degree of other vertices. And isolated vertices have already have degree 0 ($\le d$ as $d \ge 0$). And if $I$ is a ...


4

This shouldn't come as a surprise, but you should definitely be familiar with algorithms and datastructures as well as complexity theory. Two fundamental text books are downloadable for free, and you can probably find the answer to your question there: Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal ...


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

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


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

I would say yes, but you need to accept the condition that P $\neq$ NP. Take $k$-Coloring, where we want to determine whether a graph can be colored with $k$ colors such that any two connected vertices do not have the same color. Clearly, we can reduce 3-Coloring to $k$-coloring. Suppose $k$-Coloring is in FPT, then there exists an algorithm that solves this ...


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