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
114
questions
1
vote
1
answer
29
views
Independent Vertex Cover
We know that finding minimum size vertex cover is hard (NP-hard). Same hold for connected vertex cover. But what about finding minimum size independent vertex cover?
- 138
0
votes
0
answers
13
views
Is there a W(1)-hard paremeter for Knapsack?
I am currently working on a parameterized reduction from the Knapsack problem to demonstrate that a particular problem is non-FPT. Specifically, I hope to show that the Knapsack or Resource ...
4
votes
3
answers
241
views
MSOL and Courcelle's theorem for maximum clique
The Clique Problem is known to be NP-complete but is known to be fixed-parameter-tractable (FPT) if the treewidth of the underlying graph is fixed.
The traditional proof is by a dynamic programming ...
- 555
0
votes
0
answers
22
views
Kernelization For Odd Cycle Transversal Problem on Perfect Graphs
This problem appears as exercise 2.33 in https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (page 48). A perfect graph $G$ is bipartite if and only if it contains no triangle graphs. ...
- 101
2
votes
0
answers
31
views
Can a para-NP-Complete problem be $\Sigma^P_2$-Complete in its non-parameterized version?
I have a problem which (I think) have proven to be para-NP-Complete concerning some parameter $k$.
However, I am certainly sure that the non-parameterized version of this problem is $\Sigma^P_2$-...
- 31
0
votes
0
answers
93
views
The parameterized complexity of Weighted-CNF-SAT parameterized by the number of clauses
What is the parameterized complexity of Weighted-CNF-SAT, when parameterized by the number of clauses?
Input: A CNF formula $\phi$ with $m$ clauses and $n$ variables, and an integer $k$.
Parameter: $m$...
- 31
2
votes
1
answer
25
views
Parametrized threshold for LP Approximation in Vertex Cover Problem
I would like to have a formal description on how parametrizing the threshold in the approximation of vertex cover using LP would impact the approximation factor of the problem.
The linear programming ...
- 21
0
votes
1
answer
44
views
Dominating sets and treewidth
As input we are given a graph $G$ and an integer $k$ and are asked to find a dominating set of size exactly $k$ in $G$. This problem is clearly NP-hard, but does it become polynomial time solvable if ...
- 123
1
vote
0
answers
27
views
Why are there no problems parameterized by basic graph properties (e.g. maximum clique and maximum degree)?
While trying to get an overview of parameters used in the parameterized-complexity theory, it seems that there are no problems parameterized by some basic graph properties like maximum clique, maximum ...
0
votes
0
answers
65
views
3 sum conjecture if P=NP
If P=NP then we have W[1]=FPT. Would it just imply $k$-sum conjecture fails for some large $k$ or $k$ can be as small as $3$?
- 2,921
0
votes
1
answer
63
views
But why *is* $FPT$ a subset of $W[1]$?
$FPT$ is the set of parameterized problems that are fixed-parameter tractable. If $L_{w,h}$ is the language associated to boolean circuits of weft $w$ and depth $h$, then $W[t]$ is the set of ...
- 65
0
votes
0
answers
59
views
vertex-deletion and edge-deletion parameters
Let $\mathcal{G}$ be a graph class. For any class $\mathcal{H}$, we know that the minimal number of vertices that has to be removed from $G\in \mathcal{H}$ such that we get a graph from $\mathcal{G}$ ...
- 575
4
votes
1
answer
96
views
Is there such a thing as $coW[1]$-hardness?
I have a problem $\mathsf{A}$ and I would like to analyze its (parameterized) computational complexity.
I found a parameterized reduction from the complement of the independent set ($\mathsf{coIS}$) ...
- 41
1
vote
1
answer
60
views
No parameterised reduction for a problem indicates FPT or not?
I am currently working on parameterized complexity, especially on the hard proofs. There is a problem that I am currently working on, denoted by $P$ and a parameter $x$, I discovered that there is no ...
- 182
0
votes
0
answers
17
views
Can a PTAS be called one if it is parameterized by one of the problem inputs (in addition to ε)?
I.e. is it right to say "a PTAS parameterized by sth"?
Is it unusual, and is it correct?
- 1
1
vote
1
answer
70
views
Constant value NP-complete vs W[1]-hard
I am a research scholar currently working in parameterized algorithms. I am studying the complexity of a problem (say $P$) for $\Delta_{10}$ graphs and was able to provide a reduction from a known NP-...
- 182
0
votes
1
answer
87
views
Computing distance to clique in FPT time
I am a research scholar, and I currently work in parameterized algorithms. My current work involves proving that a problem is FPT for the parameter distance to clique. Although it is known that ...
- 182
2
votes
1
answer
65
views
Fpt algorithm for hypergraph basis problem
While working through the book Parameterized Complexity Theory of Flum and Grohe, I encountered exercise 1.42:
Let $H = (V, E)$ be a hypergraph. A basis of $H$ is a set $S$ of subsets of $V$ with the ...
- 65
0
votes
2
answers
30
views
Query on distance to parameter in parameterized complexity
I am a research scholar working in parameterized algorithms. For more information on parameterized complexity please refer to this. Recently, I have come across a problem which is known to be NP-...
- 182
0
votes
1
answer
35
views
Tractability w.r.t. multiple parameters
I am working on the decision version of an NP-complete problem. The problem is known to be fixed parameter tractable(FPT) with respect to the solution size $k$ as the parameter.
If I consider another ...
- 182
4
votes
2
answers
810
views
Relationship between the parameters tree width and the maximum degree
I am working on parameterized complexity and started exploring on various structural parameters. The problem I am working on is known to be W[1]-hard parameterized by treewidth of the input graph and ...
- 182
1
vote
0
answers
121
views
CNF – satisfy at most a fixed number of clauses
I'm working on this task:
Prove that the following problem can be solved in time $2^{k} \cdot \Vert \varphi \Vert^{\mathcal{O}(1)}$: given a boolean formula $\Vert \varphi \Vert$ in CNF, decide ...
- 65
1
vote
1
answer
63
views
Why do we care about computable functions in parametrized complexity definitions?
In a classical definition of the FPT complexity class, for a parametrized problem $L\subseteq \Sigma^* \times \mathbb{N}$ we require an algorithm, solving an instance $(G,k)$ in time $f(k)\cdot n^{O(1)...
- 575
2
votes
0
answers
56
views
Subgraph Isomorphism with Same Number of Nodes
I am looking at a specific variant of subgraph isomorphism:
Instance A graph $G = (V_G, E_G)$ and a target graph $H = (V_H, E_H)$ such that $|V_G| = |V_H|$.
Question Is there a subgraph $G' = (V'_G, ...
- 21
2
votes
1
answer
348
views
Bounded search tree: k-Vertex cover with $\Delta(G) = 2$
I am studying the book "Parametrized Algorithms" and it suggests a bounded search tree algorithm for k-Vertex Cover. Basically we look at a vertex v and say :
Either v will cover it's ...
- 211
1
vote
1
answer
103
views
How to find parameter sets for a big-O expression to be fixed-parameter tractable?
I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis:
Imagine that the following big-O expressions ...
- 13
0
votes
1
answer
34
views
Does FPT allow for doubling the parameter?
I have recently come across a result that showed that a given problem is in FPT when parameterized by the treewidth of a graph. However, they did this by showing that the problem is in FPT when ...
- 155
2
votes
1
answer
41
views
First-order model checking is not fixed parameter tractable on general graphs
I read that the problem of first-order model checking is believed to be not fixed parameter tractable on general graphs.
Why is this the case? Would be happy about some reference
Thanks in advance!
- 35
1
vote
1
answer
41
views
First-order model checking on general graphs is intractable
I read that the first-order model checking problem is intractable on general graphs.
How is this shown? Would be happy about some reference!
Thanks in advance
- 35
2
votes
1
answer
165
views
most cost-effective route w.r.t. gas in a labelled graph
Consider a car that can hold gas to travel a distance of $c \in N$ kilometers (its capacity) on a full tank that's initially empty. The car starts in node $s \in V$ of a graph. Each vertex $V_i$ of ...
- 2,511
2
votes
1
answer
53
views
Runtime analysis with multiple parameters: case study with heaps in Huffman coding
While studying a book on algorithms, I came across a question that asked about essentially $d$-ary Huffman coding, where the codeword alphabet has $d$ symbols (the usual case has $d=2$, with symbols $...
- 235
1
vote
0
answers
36
views
The length of the formula in Monadic second-order logic
The Courcelle's theorem as following:
Obviously, we need the length of the $\varphi$~(that is $||\varphi||$)~in Theorem. However, how to caculate the length of $\varphi$?
For example, $$\begin{...
- 59
3
votes
0
answers
83
views
Cost of finding optimal elimination order in a planar tensor network?
Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order?
For example, take the following ...
- 201
1
vote
1
answer
391
views
The relation of W[1]-hard and Para-NP-hard
Is it possible that a problem is both W[1]-hard and Para-NP-hard?
- 59
1
vote
1
answer
270
views
Complexity difference of Vertex cover and Vertex coloring regarding parametrized algorithms
I stumbled upon some problem in my understanding of the complexity classes FPT and XP.
According to Wikipedia (and the Book "Parameterized Algorithms") we know the following about the Vertex ...
- 161
2
votes
1
answer
313
views
Proving FPT is strictly contained in XP
In their book Fundamentals of Parameterized Complexity, Downey and Fellows claim (in chapter 27.1) that $\mathrm{FPT}\subsetneq \mathrm{XP}$, and that this is a "basic result" that follows ...
- 8,323
1
vote
0
answers
177
views
Determining if a maximum Independent set is in FPT when parameterized
I'm confused to if there exists an algorithm that can solve the below maximum independent set in polynomial time where it is parameterized by a k value.
maximum independent set
Input: A graph G with ...
user141218
3
votes
2
answers
713
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 ...
- 203
0
votes
0
answers
163
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$ ...
- 203
0
votes
1
answer
40
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 ...
- 59
3
votes
1
answer
147
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?
- 71
0
votes
0
answers
86
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 ...
- 59
0
votes
0
answers
70
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 ...
- 317
0
votes
0
answers
126
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 ...
- 63
0
votes
0
answers
66
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 ...
- 9
2
votes
1
answer
549
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 ...
- 39
4
votes
0
answers
346
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....
- 203
0
votes
0
answers
139
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 ...
- 39
1
vote
0
answers
38
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? ...
- 49
0
votes
1
answer
72
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 ...
- 211