# Tagged Questions

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

176 views

### Complexity of the homomorphism problem parameterized by treewidth

The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows: Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in ...
134 views

### What is the best known FPT result for 3-hitting set?

My research problem involves solving a special instance of the 3-Hitting Set problem, and I was wondering whether my result is actually significant (i.e. if it is better than the best known result for ...
95 views

### Fixed parameter tractability [closed]

Lets say I have an algorithm with complexity $O(n^k)$ where $n$ is the size of the input and $k$ is a parameter. Clearly this is superpolynomial; but in fixed parameter tractability we restrict $k$ to ...
173 views

267 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. ...
149 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 ...
79 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 ...
155 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 ...
178 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 ...
111 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}$. ...
256 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 ...
132 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 ...
892 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 ...
285 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 ...
570 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 $S$...
915 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?
311 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 ...
471 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 ...
182 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 ...
318 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 ...
221 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, ...