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
116 questions
0
votes
0
answers
19
views
Looking for a model of parametrized rendez-vous communication
I'm looking for papers on some model close enough to the one I'm studying right now.
The model is defined as follow:
We have an alphabet of actions $\Sigma$ with two rendez-vous communication actions $...
- 11
1
vote
0
answers
77
views
How can we solve Hitting set instance in runtime $O(2^k)$ using Dynamic Programming, where $k$ is the number of sets?
Suppose we have a hitting set instance $(U, F)$ where $U$ is the universal set and $F$ is the family of subsets of $U$. $F$ has $k$ many sets $=\{f_1, f_2,...,f_k\}$ and $U$ has n many elements. Using ...
- 11
0
votes
0
answers
37
views
What is the cliquewidth of a hypercube graph?
Definition.
The hypercube graph (Q_h) is the graph whose
vertex set is
$$
V(Q_h)=\{0,1\}^h,
$$
all binary strings of length (h).
edge set is
$$
E(Q_h)
=\bigl\{\{x,y\}\subseteq V(Q_h)\;\...
- 121
2
votes
1
answer
65
views
Alternative FPT running times
According to Lemma 29.4.1. in Downey & Fellows ' Fundamentals of Parameterized Complexity the running times
a) $(\log n)^k$, and
b) $2^{o(k\log n)}$
should be FPT running times, when $n$ is the ...
- 777
1
vote
1
answer
55
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
4
votes
3
answers
321
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
2
votes
0
answers
58
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
155
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
70
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
96
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
49
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
95
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,947
0
votes
1
answer
179
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
118
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}$ ...
- 777
4
votes
1
answer
141
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