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
1
vote
2answers
143 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
21 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
27 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 ...
-3
votes
0answers
31 views

parameterized complexity

Given a SAT formula $φ$ where no variable appears negated, decide if there exists a satisfying assignment which sets at most $k$ variables to value 1. Show that this problem can be solved in roughly $...
1
vote
1answer
50 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
40 views

Prerequisites for studying parametrized complexity

Which areas of CS/Math should one have mastered before diving into parametrized complexity?
4
votes
1answer
127 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
15 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
705 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
364 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
70 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
181 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
49 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
45 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
144 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
82 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
123 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
139 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
165 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 ...
3
votes
2answers
552 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
85 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
128 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
642 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
74 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
262 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
96 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
246 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
404 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
696 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
248 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
111 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
273 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
629 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
403 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
104 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
210 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
808 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 ...
3
votes
1answer
196 views

Multiple FPT Parameters

The class $FPT$ (fixed-parameter tractable) is defined here. However, there is only one "parameter" that is studied from the given problem/language. Is there an equivalently defined class that can ...
3
votes
0answers
71 views

Parameterized complexity of Weighted Satisfiability with few variable occurrences

Given an integer $k$ and a Boolean CNF Formula $\phi$, Weighted Satisfiability asks whether $\phi$ is satisfiable by a model of weight $k$, i.e., a model that sets at most $k$ variables to true. This ...
6
votes
0answers
291 views

Sokoban with only $k$ boxes

Note: I have posted a hugely expanded version of this question on cstheory. Since a Sokoban instance with only $k$ boxes has at most $n^{O(k)}$ possible states, the problem lies in $\operatorname{...
7
votes
1answer
279 views

Kernels in parameterized complexity

Can anyone explain me what (problem-)kernels are and what's the use of them? My slides say: The kernel of a parameterized problem $L$ is a transformation $(x,k) \mapsto (x',k')$ such that: $(x,k) \...
1
vote
2answers
511 views

Complexity of 4-coloring a map with constraints

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color. In fact, there exists a ...
1
vote
1answer
105 views

How does the Vertex Cover algorithm by Chen et al find its tuples?

I'm still fighting with the aforementioned paper "Improved upper bounds for vertex cover" by Chen, Kanj, Xia (PDF kindly provided by Yuval Filmus). My current problem is that it's specified that the ...
6
votes
1answer
200 views

Implementing general vertex folding procedure in an undirected graph

I'm implementing the algorithm presented in "Improved Parameterized Upper Bounds for Vertex Cover" paper (PDF). I'm a bit stumped by the General-Fold procedure. ...
7
votes
1answer
280 views

Does $\#W$[1]-hardness imply approximation hardness?

Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$. Assume that $\Pi$ is $\#W$[...