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

Filter by
Sorted by
Tagged with
0 votes
1 answer
22 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 ...
moxx's user avatar
  • 33
0 votes
0 answers
29 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}$ ...
Michal Dvořák's user avatar
3 votes
0 answers
54 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}$) ...
nuss_ecke's user avatar
1 vote
1 answer
41 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 ...
Balchandar Reddy's user avatar
0 votes
0 answers
15 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?
James's user avatar
  • 1
1 vote
1 answer
43 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-...
Balchandar Reddy's user avatar
0 votes
1 answer
41 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 ...
Balchandar Reddy's user avatar
0 votes
0 answers
13 views

Query on kernel existence between related parameters

I am a research scholar working on parameterized complexity. For more information on parameterized complexity please refer to this. I am exploring on the tractability of an NP-complete problem $P$ for ...
Balchandar Reddy's user avatar
2 votes
1 answer
52 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 ...
moxx's user avatar
  • 33
0 votes
2 answers
25 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-...
Balchandar Reddy's user avatar
0 votes
1 answer
26 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 ...
Balchandar Reddy's user avatar
3 votes
2 answers
479 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 ...
Balchandar Reddy's user avatar
1 vote
0 answers
91 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 ...
dawmd's user avatar
  • 65
1 vote
1 answer
37 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)...
Michal Dvořák's user avatar
2 votes
0 answers
53 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, ...
Siolan's user avatar
  • 21
2 votes
1 answer
155 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 ...
tonythestark's user avatar
1 vote
1 answer
93 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 ...
sebas2201's user avatar
0 votes
1 answer
30 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 ...
Gorid's user avatar
  • 145
2 votes
1 answer
32 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!
amhineoni's user avatar
1 vote
1 answer
33 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
amhineoni's user avatar
2 votes
1 answer
87 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 ...
Albert Hendriks's user avatar
2 votes
1 answer
46 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 $...
Fimpellizzeri's user avatar
0 votes
0 answers
25 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{...
zhukui bai's user avatar
3 votes
0 answers
74 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 ...
Yaroslav Bulatov's user avatar
1 vote
1 answer
158 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?
zhukui bai's user avatar
1 vote
1 answer
118 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 ...
Felix's user avatar
  • 161
2 votes
1 answer
228 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 ...
Discrete lizard's user avatar
  • 7,578
1 vote
0 answers
93 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 ...
user avatar
3 votes
2 answers
494 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 ...
JoshHalas's user avatar
  • 203
0 votes
0 answers
123 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$ ...
JoshHalas's user avatar
  • 203
0 votes
1 answer
38 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 ...
GO VEGAN's user avatar
3 votes
1 answer
112 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?
Chi Pong's user avatar
0 votes
0 answers
84 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 ...
GO VEGAN's user avatar
0 votes
0 answers
69 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 ...
sadElephant's user avatar
0 votes
0 answers
114 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 ...
John19's user avatar
  • 63
0 votes
0 answers
64 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 ...
den78's user avatar
  • 9
2 votes
1 answer
430 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 ...
Tami H's user avatar
  • 39
4 votes
0 answers
339 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....
JoshHalas's user avatar
  • 203
0 votes
0 answers
137 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 ...
Tami H's user avatar
  • 39
1 vote
0 answers
30 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? ...
Ofir Gordon's user avatar
0 votes
1 answer
63 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 ...
Sid's user avatar
  • 211
0 votes
1 answer
259 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 (...
KSGG's user avatar
  • 11
1 vote
1 answer
95 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 ...
jsitesting's user avatar
1 vote
1 answer
148 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$ ...
JoshHalas's user avatar
  • 203
0 votes
1 answer
172 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 ...
John19's user avatar
  • 63
4 votes
1 answer
303 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 ...
Jumanji Halastra's user avatar
1 vote
2 answers
446 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 ...
Sid's user avatar
  • 211
0 votes
1 answer
38 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(...
Michal Dvořák's user avatar
2 votes
0 answers
40 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 ...
Mark Regev's user avatar
1 vote
1 answer
92 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 ...
Michal Dvořák's user avatar