26

There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems. In the $k$-Path problem where we are looking for a simple path of length $k$. Alon, Yuster and Zwick [1] showed that this problem can be solved in $2^{O(k)}\cdot n$ time on $n$-vertex graphs. A weighted version of $k$-Path has ...


5

The answer to your updated Question (1) "When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then [is it] W[t]-hard for all t, at least?" is no. Independent Set for example is FPT with respect to the treewidth $\omega$ of the input ...


5

(This question was asked two years ago, but I'll post the answer for other people who may see this question.) In the Capacitated $k$-median problem we are given a set $F$ of facilities, each facility $f$ with a capacity $u_f \in \mathbb{Z}_{\geq0}$, a set $C$ of clients, a metric $d$ over $F\cup C$ and an upper bound $k$ on the number of facilities we can ...


5

Clearly there are similarities - both kernelization algorithms and Karp reductions need to work in polynomial time and produce an output instances that is equivalent to the input instance (in the sense that both are “yes”-instances or both are “no”-instances). But they are not the same concept, nor is one a special case of the other. First, they operate on ...


4

This is an answer to the updated question (the original question seems harder). Let $\mu'_k$ be the smallest constant such that $k$-SAT that has clauses of length exactly $k$ and no trivial clauses has a $O(2^{\mu'_k m})$ time algorithm. Let $\mu_k$ be the smallest constant such that $k$-SAT with any clauses of length at most $k$ has an $O(2^{\mu_k m})$ time ...


3

The answer to this question depends very much on the definition of what a solution is. Take for example the Vertex Cover problem where we ask whether a graph $G$ has a vertex set $S$ of size at most $k$ such that every edge has an endpoint in $S$. The natural definition of solution size is $k$, the size of the vertex cover. If you consider the dual parameter ...


2

A more recent open list of problems can be seen in the open problem session videos of the 2019 Workshop on Kernelization (WorKer 2019) (Session 1, Session 2). Several of the problems mentioned already remain open: Directed Feedback Vertex Set and Planar Vertex Deletion parameterized by the number $k$ of vertex deletions as mentioned by Bart remain open. The ...


Only top voted, non community-wiki answers of a minimum length are eligible