Questions tagged [parameterized-complexity]

Computational complexity with respect to one or more parameters of the input (apart from its plain length as a string), which capture intrinsically difficult instances

Filter by
Sorted by
Tagged with
11
votes
1answer
1k views

Why are all problems in FPTAS also in FPT?

According to the Wikipedia article on polynomial-time approximation schemes: All problems in FPTAS are fixed-parameter tractable. This result surprises me - these classes seem to be totally ...
6
votes
1answer
195 views

Implementing general vertex folding procedure in an undirected graph

I'm implementing the algorithm presented in "Improved Parameterized Upper Bounds for Vertex Cover" paper (PDF). I'm a bit stumped by the General-Fold procedure. ...
8
votes
1answer
1k views

Find which vertices to delete from graph to get smallest largest component

Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component. I assume for large $n = |V|$ and large $k$ the problem ...
4
votes
1answer
63 views

Is model checking PSpace-hard *in formula size*?

Sistla/Clarke proved [SC82] that the LTL model-checking problem is PSpace-complete. Sometimes people write that this problem is "PSpace-hard in $|\phi|$" (e.g. [LP85]). What does this mean formally? ...
1
vote
1answer
499 views

How is Vertex Cover reducable to Independent Set using parametrized reduction with parameter k?

We have the following Lemma and proof: Lemma 5.5. If $A$ if FPT, then $A\leq_{\mathrm{fpt}}$ Independent Set. Proof. We reduce $A$ to Independent Set parametrised by $k'$, where $k'$ is the size of a ...