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
68
questions
0
votes
0answers
18 views
K Disjoint Triangles [closed]
Given an undirected graph G and a parameter k, the task is to decide if there exists a collection C of k vertex-disjoint triangles. We need to create a randomized algorithm in O*(n^(3k))-time. The ...
0
votes
1answer
42 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 ...
0
votes
0answers
65 views
K disjoint triangles - randomized parameterized algorithm [closed]
Given an undirected graph G and a parameter k, the task is to decide if there exists a collection C of k vertex-disjoint triangles. We need to create a randomized algorithm in O*(n^(3k))-time.
The ...
0
votes
1answer
97 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
(...
1
vote
1answer
43 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 ...
1
vote
1answer
74 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$ ...
0
votes
0answers
34 views
Finding a kernel for 1-Bounded degree deletion of $O(k^2)$ vertices [duplicate]
In 1-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 maximum vertex degree ...
0
votes
1answer
73 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 ...
4
votes
1answer
240 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
2answers
170 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 ...
0
votes
1answer
23 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(...
1
vote
0answers
29 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 ...
1
vote
1answer
57 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 ...
2
votes
2answers
43 views
Prerequisites for studying parametrized complexity
Which areas of CS/Math should one have mastered before diving into parametrized complexity?
4
votes
1answer
231 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 ...
0
votes
1answer
16 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 ...
1
vote
3answers
732 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 ...
4
votes
1answer
370 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]...
3
votes
0answers
71 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
vote
0answers
20 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 ...
1
vote
1answer
229 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 ...
4
votes
1answer
51 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
1answer
54 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 ...
5
votes
1answer
165 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-...
4
votes
1answer
89 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?
...
3
votes
1answer
137 views
Why is dominating set in $W[2]$, but independent set in $W[1]$
In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W[1]$-complete, and Dominating set is $W[2]$-complete. Now the prototypical $W[1]$ problem is deciding by a single-tape ...
2
votes
1answer
156 views
Relationship between complexity classes XP and W[1]?
I am reading the introductory chapter in Parameterized Algorithms by Cygan et al. and I am having some problems with the distinction between complexity classes $\mathsf{W[1]}$ and $\mathsf{XP}$.
...
0
votes
1answer
177 views
Topics from theoretical computer science suitable for a bachelor (undergrate) thesis? [closed]
Is the field of theoretical computer science so complex, that it is just "too much" for a bachelor thesis? Unfortunately I haven't found any old thesises because the relevant chair of the university ...
2
votes
2answers
593 views
Exhaustive search algorithm solving vertex cover of size $k$ in time $2^{k}n^{O(1)}$?
In the wiki page of Vertex Cover, it is claimed that an exhaustive search algorithm can solve the problem(the decision version of vertex cover problem) in time $2^{k}n^{O(1)}$.
Intuitively, with a ...
3
votes
1answer
87 views
Why does $W[1] = A[1]$ hold?
By definition, a parameterized problem $(Q, \kappa)$ is in $W[1]$ if it can be transformed into a combinatorial circuit $\varphi$ in polynomial time, such that the weft of $\varphi$ is 1.
On the ...
1
vote
2answers
146 views
Minimum number of vertices whose removal makes the graph an independent set
It is known that finding an independent set (or a clique) of size at least $k$ in a graph is $W[1]$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent ...
1
vote
1answer
708 views
How is Vertex Cover reducable to Independent Set using parametrized reduction with parameter k?
We have the following Lemma and proof:
Lemma 5.5. If $A$ if FPT, then $A\leq_{\mathrm{fpt}}$ Independent Set.
Proof. We reduce $A$ to Independent Set parametrised by $k'$, where $k'$ is the size of a ...
2
votes
2answers
78 views
What is a “slice” of a parameterized problem $(Q, \kappa)$?
In the book "Parameterized Complexity Theory" by J. Flum, and M. Grohe, there is a definition on page 7:
Definition 1.10.
Let $(Q, \kappa)$ be a parameterized problem and $\ell \in \mathbb{N}$. The $\...
2
votes
2answers
282 views
Is $k$-CLIQUE W[1]-hard for parameter $n - k$?
It is well-known that the problem of deciding if a graph contains a clique of size $k$ is W[1]-hard with respect to parameter $k$.
Is it also known to W[1]-hard (or perhaps FPT) in parameter $n - k$, ...
3
votes
1answer
99 views
Why are Oracle call instances bounded in the definition of FPT Turing reductions?
Let's take the following definition of a FPT Turing reduction from Flum & Grohe's book.
Let $F$ and $G$ be parameterised problems. For any instance $x$ of $F$, write $k(x)$ for the parameter of $...
1
vote
1answer
262 views
What is the $4k$ kernelization algorithm for Planar Independent Set?
Chen et al. say that
The four-color theorem implies a $4k$-kernelization for Planar Independent Det, which is the dual problem of Planar Vertex Cover.
I knew that Vertex Cover has a kernelization ...
-1
votes
1answer
66 views
In the context of parametrized complexity
For instance, Subset Sum is classified :
W[1]-hard, in W[P] (parameter:k, subset cardinality)
by the Compendium of Parameterized Problems, how the parameter ...
2
votes
0answers
412 views
Why is there no FPTAS for the maximum independent set problem?
I want to prove that the NP-hardness of Maximum Independent Set implies that there is no FPTAS for the Maximum Independent Set problem unless $P=NP$.
I found the following approach after some ...
1
vote
0answers
44 views
Does an FPTAS imply a problem is FPT for a specific parameter?
I don't understand the exact relation between between FPT and FPTAS. Specifically, given an optimization problem P with fptas A does that imply that for any parameter (a computable map from the input ...
3
votes
1answer
742 views
What does the complexity class $\mathsf{XP}$ stand for?
$\mathsf{XP}$ is the class of problems with input length $n$ and parameter $k$ than can be solved in $O(n^{f(k)})$ time, where $f$ is a computable function. It's described on the complexity zoo page ...
7
votes
1answer
252 views
Equivalence between two definitions of Tree width
Treewidth :
1) By chordal graphs : size of the largest clique $(\omega (G))$ - 1 in a chordal completion of the graph $G$.
2) By tree decomposition :
A tree decomposition of $G = (V , E)$ ...
1
vote
2answers
112 views
Comparing the complexity of algorithms for listing k-cliques
Chiba and Nishizeki showed that it is possible to list all $k$-cliques (cliques on $k$ nodes) in time $O(m \cdot a^{k-2})$ where a is the arboricity of the graph and $m$ the number of edges in the ...
2
votes
0answers
281 views
FPT: Dominating Set on Planar Graphs (average degree is known)
I'm given an instance of a planar graph and should construct a FPT algorithm for dominating set. The task looks like this:
Dominating Set on Planar Graphs
Instance: A planar graph G and an
integer ...
4
votes
2answers
645 views
An FPT algorithm for Hamiltonian cycle running parameterized by treewidth
I'm looking for an algorithm that solves the Hamiltonian cycle problem parameterized by treewidth. In particular, I'm curious about such an algorithm running in $\text{tw}(G)^{O(\text{tw}(G))} \cdot n$...
0
votes
1answer
63 views
Reduction between parametrized problems
Can we construct reduction from $k$-sum to $l$-clique or vice versa where $k$ and $l$ are some fixed integers?
That is given two parametrized problems whose unparametrized version is $NP$-complete ...
0
votes
0answers
47 views
Relation between Parameterized complexity and Approximation Algorithms [duplicate]
I want to know whether there is a relation between parameterized algorithms and approximation algorithms.
Like there will exist a fpt problem for problem P iff it have some f-approx algorithm.
I ...
3
votes
1answer
414 views
Parameterized Dominating Set
What is the best algorithm to compute p-dominating set?
The p-dominating set problem is a parameterized version of minimum dominating set in which the problem takes a parameter $k$ also as an input, ...
0
votes
0answers
105 views
Isomorphic induced subgraph problem using Courcelle's theorem
The isomorphic induced subgraph problem, is the problem of deciding whether, given two graphs $G$ and $H$, $G$ contains an induced subgraph isomorphic to $H$.
Is there a proof using ...
2
votes
1answer
211 views
Problems that don't have polykernel when parametrized by vertex cover
Are there any problems apart from chromatic number, which is $FPT$ when parametrized by (the size of a minimum) vertex cover, and that does not admit a polykernel when parametrized by (the size of a ...
5
votes
1answer
852 views
FPT algorithm for point line cover
In the "Covering Things with Things" paper from Langerman and Morin, they mention the BST-Dim-Set-Cover, which is a FPT algorithm for point-line-cover, at page 666.
The algorithm chooses each point p ...
