The fixed-parameter-tractable tag has no wiki summary.
7
votes
4answers
138 views
Books/Lecture Notes on Parametrized Complexity
I would like to learn about Parametrized Complexity (both on the algorithmic side and on the hardness side). What books/lecture notes can I read on this subject?
8
votes
1answer
258 views
What is the motivation behind the definition of fixed parameter tractability?
Wikipedia writes:
FPT contains the fixed parameter tractable problems, which are those
that can be solved in time $f(k)\cdot|x|^{O(1)}$ for some computable function $f$. Typically,
this ...
7
votes
3answers
419 views
Algebraic formulation for packing problem
My question is regarding the algebraic formulation for packing problems in graphs.
Taking an example, suppose I am interested in the problem of finding if there is a packing of k edge disjoint ...
1
vote
1answer
152 views
Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$
By "complement problems", I mean the two problems' objective functions are complement. For example, the vertex cover and its complement independent set in this sense. For a graph $G(V,E)$, their ...
6
votes
2answers
202 views
Variants of Cluster-Vertex-Deletion problem
The Unweighted Cluster-Vertex-Deletion problem is the following:
Input: An undirected graph G = (V, E) and a nonnegative number k
Output: Is there a subset X ⊆ V with |X| ≤ k such that deleting all ...
13
votes
1answer
193 views
Elementary bounds on parameter in fixed-parameter tractability?
In the definition of (strong) fixed-parameter tractability, the time bound is an expression of the form $$f(k).p(|x|),$$ where the input instance is $(x,k)$ with parameter $k$, $p$ is a polynomial, ...
11
votes
0answers
222 views
FPT vs W[P] - Parameterized Complexity
In parametrized complexity, $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$. It is conjectured that each of the containments is proper.
If ...
12
votes
1answer
197 views
Any results on binary boolean CSP beyond the fixed-parameter tractability of almost 2SAT problem?
Let $\varphi$ be a 2CNF formula and $k$ a nonnegative integer. It is proved in this paper that the problem of deciding whether one can delete at most $k$ clauses to make $\varphi$ satisfable, is ...
8
votes
2answers
482 views
Relation between fixed parameter and approximation algorithm
Fixed parameter and approximation are totally different approaches to solve hard problems. They have different motivation. Approximation looks for faster result with approximate solution. Fixed ...
11
votes
5answers
460 views
Hardness of FPT problems
Vertex Cover can be easily reduced to Independent Set and vice versa.
However, in the context of parameterized complexity, Independent set is harder than Vertex Cover. A kernel with $2k$ vertices ...
7
votes
3answers
280 views
Is parametrized maximum independent clauses problem in FPT?
Parametrized maximum independent clauses problem:
Input : A r-CNFSAT formula F having n variables and m clauses, k
Ques : Does there exists at least k clauses such that they are mutually independent ...
