algorithms for parameterized problems where the run-time is polynomial in the input size, but depends arbitrarily on the parameter

learn more… | top users | synonyms

0
votes
1answer
92 views

Natural maximization problems in FPT

Is there a natural (and hopefully well-known) maximization problem that is known to be in FPT? For instance, Vertex Cover is in FPT, but it's a minimization problem. I'm looking for natural ...
5
votes
1answer
175 views

Easy decision hard counting Parametrized

It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P. Is there a problem, that exhibits the same behavior in ...
8
votes
2answers
419 views

Implications of a problem being in XP when parameterized by diameter

Let $X$ be an NP-complete graph problem. Suppose $X$ is solvable in polynomial time on graphs of bounded diameter. In other words, $X$ parameterized by diameter is in XP. (Recall a problem is in XP if ...
3
votes
0answers
59 views

Multiple knapsack fpt?

It was an open question whether multiple knapsack is fpt wrt standard parameter. Since at SODA 2009 Jansen has presented an EPTAS for multiple knapsack and an EPTAS implies the existense of an fpt ...
7
votes
0answers
115 views

Is 4-colors precoloring extension for planar graphs fixed parameter tractable?

Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable). Assume you are given a set of $k$ constraints of the form "$v_i \text{ is ...
10
votes
2answers
250 views

Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), I was wondering how parameterized problems are affected by these attributes. ...
4
votes
0answers
109 views

FPT algorithm for mixed integer program

It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer ...
1
vote
1answer
77 views

Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm

EDIT: I'm sorry if this question belongs more to cs.SE, I've had a dilemma about where to put it. Please let me know if it's inappropriate. I'm currently implementing the Vertex Cover problem solving ...
7
votes
2answers
132 views

Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?

The $q$-Dimensional $p$-Matching is defined as follows: Given disjoint universes $U_1,\ldots,U_q$, think of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element from ...
1
vote
1answer
105 views

Node-weighted steiner problem with few terminals

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight ...
5
votes
0answers
105 views

Is minimum weight simple cycles through specified vertics fixed parameter tractable?

The problem formulation is as follows: Input: Undirected graph $G=(V,E)$, a set of vertices $S\subseteq |V|$, a weight function $w:E\to \mathbb{R}$ and a threshold $T\in \mathbb{R}$. ...
4
votes
1answer
248 views

Vertex disjoint simple paths of length k

A lot of effort has been invested in finding simple k-paths, as well as in finding vertex disjoint paths. Is there any known parametrized algorithm that given a graph $G=(V,E)$, decides whether there ...
12
votes
1answer
107 views

Clique-width expressions with logarithmic depth

When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree ...
17
votes
4answers
796 views

Open problems related to Graph isomorphism

Presently I am doing literature survey on Graph isomorphism (GI) problem. I would like to know some open questions related to the following What are the graph parameters for which fixed parameter ...
4
votes
1answer
207 views

On Random Self-reducible properties

Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$. 1) Is $k$-sum random self-reducible? That ...
11
votes
3answers
506 views

Exact Algorithms for Dominating set

Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in ...
10
votes
5answers
862 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?
9
votes
1answer
303 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
467 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 ...
2
votes
1answer
175 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 ...
7
votes
2answers
300 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
212 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, ...
17
votes
1answer
366 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
242 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 ...
11
votes
2answers
654 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 ...
13
votes
5answers
577 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
316 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 ...