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

46 questions
18 views

Determine smallest possible parameter set for FPT

I am reading a book about complexity analysis and cannot find a way to solve a problem in that book. The problem is, that I do not understand how to determine the smallest possible parameters, given ...
56 views

Parametrized reduction from 3-SAT to Independent Set to lower bound running time under ETH assumption

I want to prove that, assuming Exponential Time Hypothesis is true, there is no algorithm that solves Independent Set in $2^{o(|V|+|E|)}$ time. I want to apply the following strong parameterized many-...
41 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? ...
60 views

Why is dominating set in $W$, but independent set in $W$

In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W$-complete, and Dominating set is $W$-complete. Now the prototypical $W$ problem is deciding by a single-tape ...
42 views

Relationship between complexity classes XP and W?

I am reading the introductory chapter in Parameterized Algorithms by Cygan et al. and I am having some problems with the distinction between complexity classes $\mathsf{W}$ and $\mathsf{XP}$. ...
73 views

Topics from theoretical computer science suitable for a bachelor (undergrate) thesis? [closed]

Is the field of theoretical computer science so complex, that it is just "too much" for a bachelor thesis? Unfortunately I haven't found any old thesises because the relevant chair of the university ...
181 views

Exhaustive search algorithm solving vertex cover of size $k$ in time $2^{k}n^{O(1)}$?

In the wiki page of Vertex Cover, it is claimed that an exhaustive search algorithm can solve the problem(the decision version of vertex cover problem) in time $2^{k}n^{O(1)}$. Intuitively, with a ...
67 views

Why does $W = A$ hold?

By definition, a parameterized problem $(Q, \kappa)$ is in $W$ if it can be transformed into a combinatorial circuit $\varphi$ in polynomial time, such that the weft of $\varphi$ is 1. On the ...
53 views

Minimum number of vertices whose removal makes the graph an independent set

It is known that finding an independent set (or a clique) of size at least $k$ in a graph is $W$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent ...
317 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 ...
52 views

119 views

What is the $4k$ kernelization algorithm for Planar Independent Set?

Chen et al. say that The four-color theorem implies a $4k$-kernelization for Planar Independent Det, which is the dual problem of Planar Vertex Cover. I knew that Vertex Cover has a kernelization ...
59 views

In the context of parametrized complexity

For instance, Subset Sum is classified : W-hard, in W[P] (parameter:k, subset cardinality) by the Compendium of Parameterized Problems, how the parameter ...
321 views

Why is there no FPTAS for the maximum independent set problem?

I want to prove that the NP-hardness of Maximum Independent Set implies that there is no FPTAS for the Maximum Independent Set problem unless $P=NP$. I found the following approach after some ...
33 views

Does an FPTAS imply a problem is FPT for a specific parameter?

I don't understand the exact relation between between FPT and FPTAS. Specifically, given an optimization problem P with fptas A does that imply that for any parameter (a computable map from the input ...
396 views

What does the complexity class $\mathsf{XP}$ stand for?

$\mathsf{XP}$ is the class of problems with input length $n$ and parameter $k$ than can be solved in $O(n^{f(k)})$ time, where $f$ is a computable function. It's described on the complexity zoo page ...
197 views

Equivalence between two definitions of Tree width

Treewidth : 1) By chordal graphs : size of the largest clique $(\omega (G))$ - 1 in a chordal completion of the graph $G$. 2) By tree decomposition : A tree decomposition of $G = (V , E)$ ...
95 views

Comparing the complexity of algorithms for listing k-cliques

Chiba and Nishizeki showed that it is possible to list all $k$-cliques (cliques on $k$ nodes) in time $O(m \cdot a^{k-2})$ where a is the arboricity of the graph and $m$ the number of edges in the ...
170 views

FPT: Dominating Set on Planar Graphs (average degree is known)

I'm given an instance of a planar graph and should construct a FPT algorithm for dominating set. The task looks like this: Dominating Set on Planar Graphs Instance: A planar graph G and an integer ...
457 views

An FPT algorithm for Hamiltonian cycle running parameterized by treewidth

I'm looking for an algorithm that solves the Hamiltonian cycle problem parameterized by treewidth. In particular, I'm curious about such an algorithm running in $\text{tw}(G)^{O(\text{tw}(G))} \cdot n$...
52 views

Reduction between parametrized problems

Can we construct reduction from $k$-sum to $l$-clique or vice versa where $k$ and $l$ are some fixed integers? That is given two parametrized problems whose unparametrized version is $NP$-complete ...
46 views

Relation between Parameterized complexity and Approximation Algorithms [duplicate]

I want to know whether there is a relation between parameterized algorithms and approximation algorithms. Like there will exist a fpt problem for problem P iff it have some f-approx algorithm. I ...
279 views

Parameterized Dominating Set

What is the best algorithm to compute p-dominating set? The p-dominating set problem is a parameterized version of minimum dominating set in which the problem takes a parameter $k$ also as an input, ...
93 views

Isomorphic induced subgraph problem using Courcelle's theorem

The isomorphic induced subgraph problem, is the problem of deciding whether, given two graphs $G$ and $H$, $G$ contains an induced subgraph isomorphic to $H$. Is there a proof using ...
157 views

Problems that don't have polykernel when parametrized by vertex cover

Are there any problems apart from chromatic number, which is $FPT$ when parametrized by (the size of a minimum) vertex cover, and that does not admit a polykernel when parametrized by (the size of a ...
528 views

FPT algorithm for point line cover

In the "Covering Things with Things" paper from Langerman and Morin, they mention the BST-Dim-Set-Cover, which is a FPT algorithm for point-line-cover, at page 666. The algorithm chooses each point p ...
154 views

Multiple FPT Parameters

The class $FPT$ (fixed-parameter tractable) is defined here. However, there is only one "parameter" that is studied from the given problem/language. Is there an equivalently defined class that can ...
59 views

Parameterized complexity of Weighted Satisfiability with few variable occurrences

Given an integer $k$ and a Boolean CNF Formula $\phi$, Weighted Satisfiability asks whether $\phi$ is satisfiable by a model of weight $k$, i.e., a model that sets at most $k$ variables to true. This ...
265 views

325 views

Complexity of 4-coloring a map with constraints

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color. In fact, there exists a ...
99 views

How does the Vertex Cover algorithm by Chen et al find its tuples?

I'm still fighting with the aforementioned paper "Improved upper bounds for vertex cover" by Chen, Kanj, Xia (PDF kindly provided by Yuval Filmus). My current problem is that it's specified that the ...
172 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. ...
Does $\#W$-hardness imply approximation hardness?
Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$. Assume that $\Pi$ is $\#W$[...