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
93
questions
1
vote
1
answer
80
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
26
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 ...
- 145
2
votes
1
answer
21
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
30
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
77
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,296
2
votes
1
answer
43
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
0
votes
0
answers
21
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{...
- 53
0
votes
0
answers
32
views
Parameterized complexity of 3-SAT
Is the 3-SAT problem with $s$ variables and $t$ clauses FPT, parameterized by $s+t$,
or W[1]-hard, or para-NP-hard?
- 53
3
votes
0
answers
58
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 ...
- 149
1
vote
1
answer
47
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?
- 53
1
vote
1
answer
76
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 ...
- 149
2
votes
1
answer
165
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 ...
- 6,978
1
vote
0
answers
41
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 ...
- 31
3
votes
2
answers
302
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 ...
- 103
0
votes
0
answers
93
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$ ...
- 103
0
votes
1
answer
32
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
80
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
82
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
61
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 ...
- 25
0
votes
0
answers
61
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 ...
- 39
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 ...
- 317
0
votes
0
answers
93
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 ...
- 73
0
votes
0
answers
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$ ...
- 73
0
votes
0
answers
61
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
306
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
316
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....
- 103
0
votes
0
answers
136
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
18
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
54
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 ...
- 201
0
votes
1
answer
167
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
(...
- 11
1
vote
1
answer
72
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 ...
- 25
1
vote
1
answer
121
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$ ...
- 103
0
votes
1
answer
134
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 ...
- 73
4
votes
1
answer
269
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
2
answers
313
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 ...
- 201
0
votes
1
answer
32
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(...
- 157
2
votes
0
answers
37
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 ...
- 117
1
vote
1
answer
77
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 ...
- 157
2
votes
2
answers
50
views
Prerequisites for studying parametrized complexity
Which areas of CS/Math should one have mastered before diving into parametrized complexity?
- 23
4
votes
1
answer
391
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 ...
- 2,851
0
votes
1
answer
19
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 ...
- 83
1
vote
3
answers
875
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 ...
- 123
4
votes
1
answer
403
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]...
- 51
3
votes
0
answers
94
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,369
1
vote
0
answers
21
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 ...
- 799
2
votes
1
answer
487
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 ...
- 123
4
votes
1
answer
57
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
1
answer
89
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 ...
- 48
5
votes
1
answer
280
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-...
- 107
4
votes
1
answer
110
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?
...
- 1,016