# 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
Filter by
Sorted by
Tagged with
1 vote
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
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 ...
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
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. ...
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$-...
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$...
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 ...
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
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 ...
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
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
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}$ ...
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}$) ...
1 vote
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 ...
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 vote
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-...
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 ...
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
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-...
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 ...
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 ...
1 vote
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
63 views

• 21
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
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 ...
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
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!
1 vote
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
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