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
4
votes
1answer
46 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-...
4
votes
1answer
40 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?
...
3
votes
1answer
57 views
Why is dominating set in $W[2]$, but independent set in $W[1]$
In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W[1]$-complete, and Dominating set is $W[2]$-complete. Now the prototypical $W[1]$ problem is deciding by a single-tape ...
2
votes
1answer
38 views
Relationship between complexity classes XP and W[1]?
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[1]}$ and $\mathsf{XP}$.
...
0
votes
1answer
66 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 ...
2
votes
2answers
156 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 ...
3
votes
1answer
65 views
Why does $W[1] = A[1]$ hold?
By definition, a parameterized problem $(Q, \kappa)$ is in $W[1]$ if it can be transformed into a combinatorial circuit $\varphi$ in polynomial time, such that the weft of $\varphi$ is 1.
On the ...
1
vote
2answers
52 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[1]$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent ...
1
vote
1answer
285 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 ...
2
votes
2answers
50 views
What is a “slice” of a parameterized problem $(Q, \kappa)$?
In the book "Parameterized Complexity Theory" by J. Flum, and M. Grohe, there is a definition on page 7:
Definition 1.10.
Let $(Q, \kappa)$ be a parameterized problem and $\ell \in \mathbb{N}$. The $\...
2
votes
2answers
135 views
Is $k$-CLIQUE W[1]-hard for parameter $n - k$?
It is well-known that the problem of deciding if a graph contains a clique of size $k$ is W[1]-hard with respect to parameter $k$.
Is it also known to W[1]-hard (or perhaps FPT) in parameter $n - k$, ...
3
votes
1answer
67 views
Why are Oracle call instances bounded in the definition of FPT Turing reductions?
Let's take the following definition of a FPT Turing reduction from Flum & Grohe's book.
Let $F$ and $G$ be parameterised problems. For any instance $x$ of $F$, write $k(x)$ for the parameter of $...
1
vote
1answer
117 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 ...
-1
votes
1answer
59 views
In the context of parametrized complexity
For instance, Subset Sum is classified :
W[1]-hard, in W[P] (parameter:k, subset cardinality)
by the Compendium of Parameterized Problems, how the parameter ...
2
votes
0answers
308 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 ...
1
vote
0answers
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 ...
2
votes
1answer
368 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 ...
7
votes
1answer
195 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)$ ...
1
vote
2answers
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 ...
3
votes
0answers
167 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 ...
4
votes
2answers
437 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$...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
3
votes
1answer
261 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, ...
0
votes
0answers
91 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 ...
2
votes
1answer
151 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 ...
4
votes
1answer
512 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 ...
3
votes
1answer
149 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 ...
2
votes
0answers
57 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 ...
6
votes
0answers
265 views
Sokoban with only $k$ boxes
Note: I have posted a hugely expanded version of this question on cstheory.
Since a Sokoban instance with only $k$ boxes has at most $n^{O(k)}$ possible states, the problem lies in $\operatorname{...
7
votes
1answer
218 views
Kernels in parameterized complexity
Can anyone explain me what (problem-)kernels are and what's the use of them? My slides say:
The kernel of a parameterized problem $L$ is a transformation $(x,k) \mapsto (x',k')$ such that:
$(x,k) \...
1
vote
2answers
303 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 ...
1
vote
1answer
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 ...
6
votes
1answer
168 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.
...
7
votes
1answer
239 views
Does $\#W$[1]-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$[...
5
votes
0answers
108 views
Reduction from clique to bag automata
I am trying to figure out a reduction to prove $W[1]$-hardness for this, but I am having significant trouble. Here is the problem:
Bag Automaton:
A non deterministic finite state automaton $M=(Q,I,s,...
3
votes
1answer
172 views
FPT algorithm for edge dominating set
I have been attempting to learn parameterized complexity on my own, and decided to go through all of the FPT race problems, and defining easy FPT algorithms for them, using concepts such as bounded ...
4
votes
2answers
277 views
NP-hardness and FPTAS
I have a problem in understanding how to prove the following question.
Let $Q = \langle\max,f,L\rangle$ be an NPO-Problem, where $f$ only supports integers.
Define $$L_Q^* =\{(x_0,1^k) : \exists x . ...
7
votes
2answers
228 views
Courcelle's Theorem: Looking for papers
I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth.
I am only a beginner ...
11
votes
1answer
879 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 ...
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 ...
3
votes
1answer
3k views
Reduction from Vertex Cover to an Independent Set problem
Assume there exists some algorithm that solves vertex cover problem in time polynomial in terms of $n$ and exponential for $k$ with the run time that looks like this $O(k^2 55^k n^3)$. Can we claim ...
6
votes
1answer
1k views
NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?
I have seen some problems that are NP-hard but polynomially solvable in fixed dimension.
Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
6
votes
0answers
83 views
Decomposition of graphs that uses centers
Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason (...
6
votes
1answer
677 views
$1+\epsilon$ approximation for inapproximable problems
I am currently confused by the following situation:
1) The metric $k$-center problem is inapproximable in polynomial time within $2-\epsilon$ unless $P=NP$.
2) The metric $k$-center problem can ...
