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
59
questions
0
votes
1answer
7 views
Structural parametrization for weighted vertex cover
Let $G$ be a graph which is a tree with $\ell$ added edges. I wish to show that VWVC ((Vertex-)Weighted Vertex cover) is FPT with respect to $\ell$. In particular, I'd like an algorithm running in $O(...
1
vote
0answers
26 views
Tree Decomposition Construction with Balanced Separations: Why 2/3?
I am working through the book "Parameterized Algorithms" https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf and at the chapter about tree decomposition I am trying to ...
-3
votes
0answers
31 views
parameterized complexity
Given a SAT formula $φ$ where no variable appears negated, decide if there exists a satisfying assignment which sets at most $k$ variables to value 1.
Show that this problem can be solved in roughly $...
1
vote
1answer
46 views
Polynomial kernelization for Set Splitting
In a set system $(U, F)$, $F\subseteq \mathcal{P}(U))$, we say that a function $f: U \to \{0, 1\}$ is a coloring of $(U, F)$. A set in $F$ is split by $f$ if $F$ receives both colors.
The Set ...
2
votes
2answers
40 views
Prerequisites for studying parametrized complexity
Which areas of CS/Math should one have mastered before diving into parametrized complexity?
4
votes
1answer
126 views
Finding a kernel for d-Bounded degree deletion
In $d$ Bounded degree deletion problem, we are given an undirected graph $G$ and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the the maximum ...
0
votes
1answer
15 views
What does a kernel of size n,n^2 ,… mean?
So according to Wikipedia,
In the Notation of [Flum and Grohe (2006)], a ''parameterized problem'' consists of a decision problem $L\subseteq\Sigma^*$ and a function $\kappa:\Sigma^*\to N$, the ...
1
vote
3answers
705 views
Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists?
Question
Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists?
The adding a parameter is needed ...
4
votes
1answer
364 views
Are there any known W[3] or W[3]-hard problems?
We are currently working on a variant of domination parameter and we have shown that it is in W[3] with regard to parameterized complexity. To show it is W[3]-complete, we must show the problem is W[3]...
3
votes
0answers
70 views
What about problems that are fixed parameter tractable with an algorithm that does not inspect the parameter?
A parameterized problem is a subset $L \subseteq \Sigma^* \times \mathbb N$, where $\Sigma$ is a finite alphabet. A parameterized problem is fixed parameter tractable, if it could be decided in time $...
1
vote
0answers
19 views
Sorting with high-latency compare
My basic setup is very simple: I'm trying to sort N items now, and later on I'll need to incrementally sort more items. The unique part of the problem is that my item comparison is not a computational ...
1
vote
1answer
179 views
Estimating P in Amdahl's Law theoretically and in practice
In parallel computing, Amdahl's law is mainly used to predict the theoretical maximum speedup for program processing using multiple processors. If we denote the speed up by S then Amdahl’s law is ...
4
votes
1answer
49 views
Can the W hierarchy by defined by circuits having a satisfying assignment of weight at most k?
Traditionally, the $W$ hierarchy is defined around the problem of weighted circuit satisfiability. More precisely, the class $W[t]$ is defined as the closure under $\mathrm{fpt}$-reductions of the ...
3
votes
1answer
45 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 ...
5
votes
1answer
142 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
82 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
123 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
136 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
159 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 ...
3
votes
2answers
538 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
84 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
128 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
641 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 ...
2
votes
2answers
74 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
262 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
95 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
246 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
66 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
403 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
44 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 ...
3
votes
1answer
691 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
248 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
111 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 ...
2
votes
0answers
273 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
627 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$...
0
votes
1answer
63 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
47 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
403 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
104 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
207 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 ...
5
votes
1answer
808 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
194 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 ...
3
votes
0answers
71 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
291 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
279 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
509 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
105 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
200 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
280 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
123 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,...
