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
85
questions
3
votes
2answers
200 views
Relationship between complexity classes W[1] and NP?
I am trying to understand the connection between The W-hierarchy as presented in chapter 13 of this book by Cygan et al. and the notion of the NP problems.
Is the existence of an FPT algorithm for a ...
0
votes
0answers
79 views
Proving that a problem is not FPT using reduction
In the Inclusive Vertex Cover problem, For a given graph $G=(V,E)$, each vertex $u\in V(G)$ has weight $u_{w} \in \mathbb{N}$ and value $u_{v}\in \mathbb{N}$. The value and weight of a set cover $S$ ...
0
votes
1answer
17 views
What is T-star packing
What is a T-star packing and what is Proper Maximal 3-Star Packing?
I read some definitions and can't understand
"By a T-star we mean a complete bipartite graph K1,t for some t ≤ T. For an ...
3
votes
1answer
46 views
FPT algorithm for Knapsack
I tried to search whether Knapsack (the decision version) has a FPT algorithm, but didn't find anything on the topic.
Can someone help with a reference?
0
votes
0answers
78 views
Petal-Deletion problem on O(k)
In Petal-Deletion, we are given an undirected graph G and k ∈ N, and the objective is to decide whether there exists a subset S ⊆ V (G) of size at most k such that G − S does not contain any 3-petal ...
0
votes
0answers
52 views
Approximate FPT and Approximate kernel for a decidable problem
I'm trying to prove the following:
For every decidable parameterized problem Π, Π admits a fixed parameter tractable α-approximation algorithm if and only if Π has an α-approximate kernel.
I'm trying ...
0
votes
0answers
57 views
Finding a kernel for 2-Bounded Degree Deletion problem of $O(k)$ vertices
In $2$ Bounded degree deletion problem, we're 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 maximum vertex ...
0
votes
0answers
64 views
Reduction rules to lower bound minimum degree of a graph
I'm trying to come up with a list of rules that return an equivalent instance to the following problem, while eliminating all vertices of degree 2 or less from the graph:
Given a graph $G=(V,E)$, the ...
-3
votes
0answers
39 views
Lite Feedback Vertex Set [duplicate]
In Lite Feedback Vertex Set, given an undirected graph G and k ∈ N, and the objective is to decide whether there exists a subset S ⊆ V (G) of size at most k such that every connected component in G − ...
-5
votes
0answers
56 views
VS Problem algorithm
In CLOSED VERTEX COVER, we are given a graph G In CLOSED VERTEX COVER, we are given a graph 𝐺 where each vertex 𝑣∈𝑉(𝐺) has self-utility 𝑢𝑣∈ℕ and self-pollution 𝑝𝑣∈ℕ, and 𝑘,𝑈⋆,𝑃⋆∈ℕ.
For each ...
0
votes
0answers
79 views
Algorithm for Variant of 0-1 Knapsack Problem
Variant of 0-1 Knapsack Problem is when you can choose exactly $k$ items from $n$ items, and $k$ is positive integer parameter that came in the input.
Is there an algorithm with running time ...
0
votes
0answers
61 views
Feedback Vertex Set restricted to planar graphs
In Feedback Vertex Set, we are given an undirected graph $G$ and $k \in \mathbb{N}$, and the objective is to decide whether there exists a subset $S \subseteq V(G)$ of size at most $k$ such that $G-S$ ...
-2
votes
0answers
140 views
Is there exist FPT algorithm for a variant of VC problem?
In CLOSED VERTEX COVER, we are given a graph $G$ where each vertex $v \in V(G)$ has self-utility $u_{v} \in \mathbb{N}$ and self-pollution $p_{v} \in \mathbb{N}$, and $k, U^{\star}, P^{\star} \in \...
-2
votes
0answers
40 views
Parameterized Algorithms - vertex kernel for STAR DELETION
can someone gives some help here? some idea how to start?
this is a question from a course called Parameterized Algorithms (not an homework. just a practise we got for the exam)
(and here as a text ...
0
votes
0answers
58 views
Disjoint Lite Feedback Vertex Set
Disjoint Lite Feedback Vertex Set. given an undirected graph G and k ∈ N, and a Lite Feedback Vertex Set(LFVS) X of G of size ≤k+1 the objective is to decide whether there exists a subset S ⊆ V (G) of ...
2
votes
1answer
255 views
Dynamic Programming for Feedback Vertex Set - bounded treewidth
Saw it on another post that there is a way of solving FVS in polynomial time if the treewidth is constant, using dynamic programming?...
If I'm given the treewidth of a graph, how do I solve it in ...
4
votes
0answers
297 views
FPT algorithm for a variant of Feedback Vertex Set
I am interested in a variant of the Feedback Vertex Set (FVS) problem.
For an undirected graph $G$ and $k\in \mathbb{N}$ we need to decide if there is a subset $S \subseteq V(G)$ of size at most $k$ s....
0
votes
0answers
132 views
Claw-free graph - linear kernel
I'm having a hard time solving the problem below:
In Claw-free problem, we are given a graph $G$ and $k$, and the objective is to decide whether there exists a subset $S \subseteq V (G)$ of size at ...
1
vote
0answers
13 views
$W$-hierarchy and parameterized search problems
I have two related questions:
What are the ways to prove that a certain problem is in $W[t]$ in the W-hierarchy for parametrized complexity, except using the straight definition of boolean circuits? ...
0
votes
1answer
46 views
Constructing a crown graph given an independent set
A crown in a graph $G$ is a pair $(H, C)$, where $H \subseteq V(G)$ and $C \subseteq V(G)$ with $H ∩ C = ∅$ such that the following conditions hold:
(a) The set of neighbors of vertices in $C$ is ...
0
votes
1answer
110 views
Color coding to get an FPT algoirthm for k disjoint triangles
The k-disjoint triangles problem is as follows:
Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
Output: Are there $k$ vertex-disjoint triangles in $G$?
An FPT algorithm is presented here
(...
1
vote
1answer
54 views
Time complexity for FPT algorithm
I'm studying the issue of FPT algorithms and came to the k-disjoint triangles problem as can be seen
here on slide 60.
The problem summary is given a graph G and variable k, are there k disjoint ...
1
vote
1answer
98 views
k disjoint triangles with graph splitting to two distinct groups
Please note that this question is different than this question.
The $k$-disjoint triangles problem is as follows:
Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
Output: Are there $k$ ...
0
votes
0answers
48 views
Finding a kernel for 1-Bounded degree deletion of $O(k^2)$ vertices [duplicate]
In 1-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 maximum vertex degree ...
0
votes
1answer
104 views
Kernelization algorithm for the following problem
We are given an undirected graph $ G $ and a positive parameter
$ k \geq 0 $. The problem is to decide if there exists a set $ S \subseteq V(G) $ of size at most $ k $ such that $ G − S $ does not ...
4
votes
1answer
258 views
FPT algorithm for 1-BDD
Given a graph $G = (V,E)$ and an integer $k$, the 1-BDD problem asks if there exists a subset $D$ of at
most $k$ vertices such that the degree of any vertex in $G[V \setminus D]$ is at most one.
Is ...
1
vote
2answers
183 views
Can someone tell a formal definition for this problem: k-disjoint triangle?
k-disjoint triangle
"We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. "
The above definition is the best ...
0
votes
1answer
28 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(...
2
votes
0answers
36 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 ...
1
vote
1answer
66 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
45 views
Prerequisites for studying parametrized complexity
Which areas of CS/Math should one have mastered before diving into parametrized complexity?
4
votes
1answer
315 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
16 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
775 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
375 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
76 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
20 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
266 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
51 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
65 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
184 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
92 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
149 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
179 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
182 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
622 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
96 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
161 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
742 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
80 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 $\...
