26 votes
Accepted

Has parameterized complexity led to better algorithms?

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 ...
user avatar
19 votes

Is parameterized complexity going to be the future of complexity theory?

Predicting the future is nigh impossible, especially so for cutting-edge research. I don't think anyone predicted how much impact deep learning is now having or that cryptography would be taken over ...
user avatar
  • 2,743
14 votes
Accepted

FPT vs W[P] - Parameterized Complexity

This question is tricky as the answer (as far as I know) is still "don't know". To add some weight to this, Flum & Grohe [1] give as open problems (p. 164): Is the $\mathrm{W}$-hierarchy ...
user avatar
14 votes

Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

I believe the title of this paper is self-explanatory and answers your question: On product covering in 3-tier supply chain models: Natural complete problems for W[3] and W[4]
user avatar
  • 2,530
14 votes
Accepted

Parameterized complexity of inclusion of regular languages

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even ...
user avatar
  • 7,653
13 votes
Accepted

Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

From the comment above: $p$-HYPERGRAPH-(NON)-DOMINATING-SET is W[3]-complete under fpt-reductions: A hypergraph $H = (V,E)$ consists of a set $V$ of vertices and a set $E$ of hyperedges. Each ...
user avatar
13 votes
Accepted

Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas

The problem does not have a polynomial kernel unless NP is in coNP/poly. The cross-composition technique from our paper applies in a nontrivial way. Let me show how the classic Vertex Cover problem ...
user avatar
  • 5,225
11 votes
Accepted

Major open problems on polynomial kernel (non) existence

Currently, I would say the 3 major open cases are: Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution Planar Vertex ...
user avatar
  • 5,225
11 votes
Accepted

Parametrized complexity of the 2-Long Paths Problem

Your problem is fixed-parameter tractable, which follows from the heavy machinery of Robertson & Seymour. Your problem can be stated in terms of rooted minors. A graph $H$ with designated root ...
user avatar
  • 5,225
10 votes
Accepted

Gentle introduction to the algorithmic aspects of tree-depth

My favorite resource for this subject is the book Sparsity by Jaroslav Nešetřil and Patrice Ossona de Mendez. It has quite a bit of material specifically about tree-depth, including algorithmic ...
user avatar
10 votes
Accepted

Easy decision hard counting Parametrized

Finding $k$-path (simple paths of length $k$) in a graph is in $FPT$ and can be done in $O^*(2^k)$ with a randomized algorithm or $O^*(2.62^k)$ deterministically. This is while Counting $k$-paths is $...
user avatar
  • 9,378
10 votes
Accepted

Implications of a problem being in XP when parameterized by diameter

I think Figure 1 (page 4) of the paper "New Races in Parameterized Algorithmics" of Komusiewicz and Niedermeier is what you are looking for. In particular, being in XP for the parameter diameter ...
user avatar
  • 190
9 votes

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

The disjoint paths problem: given $G$ and $k$ pairs of nodes, are there node disjoint paths connecting the given pairs. Parameterized by $k$, in FPT when $G$ is undirected from the seminal work of ...
user avatar
9 votes
Accepted

W[1]-hard problems with FPT time approximation algorithms

In the Directed Odd Cycle Transversal problem the input is a graph $G$ and the task is to find a smallest set $S$ of vertices such that $G-S$ has no (directed) cycles of odd length. In the ...
user avatar
  • 3,236
8 votes
Accepted

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

Our recent paper shows that counting k-matchings is #W[1]-hard even in bipartite graphs. This answers your question. Radu Curticapean, Dániel Marx: Complexity of counting subgraphs: only the ...
user avatar
  • 1,968
7 votes

ETH: k-SAT vs. SAT?

The difference between your definitions is that the clause width in $s_\omega$ is allowed to grow with the number of variables, while for $s_\infty$ it is arbitrarily large but constant. It's a ...
user avatar
7 votes
Accepted

Parameterized complexity of Exact Cover

Correction: I have claimed (see below) that "Independent Dominating Set" is a special case of ExactCover. This claim was wrong, as two vertices in the ind-dom set may have overlapping neighborhoods. ...
user avatar
  • 5,712
7 votes

Hard problems for bounded vertex cover

$(k,r)$-center is another (arguably natural) problem that is $W[1]$-hard parameterized by vertex cover. (See a recent preprint by Katsikarelis, me, and Paschos here - sorry about the self-promotion!). ...
user avatar
7 votes
Accepted

Maximum Treewidth of a Graphs with $m$ Edges

There are bounded degree (in fact even cubic i.e. 3-regular) expanders on $m$ vertices with treewidth at least $\epsilon \cdot m$, for some constant $\epsilon > 0$. See Section 2 in: Martin Grohe, ...
user avatar
  • 780
6 votes

Is there a sensible notion of an approximation algorithm for an undecidable problem?

This is answering the title of the question more than its content, but you can also consider "approximations" of the halting problem as algorithms which will give you a correct answer on "almost all" ...
user avatar
  • 329
6 votes

Hard problems for bounded vertex cover

Here is a problem (with lists!) which is known to be W[1]-hard parameterized by Vertex Cover (indeed, even by the number of vertices in the input graph). The problem is known as the "Arc Supply" ...
user avatar
  • 3,236
6 votes
Accepted

Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?

How about Planar Capacitated Dominating Set? It is W[1]-hard (see the paper by Bodlaender, Lokshtanov, Penninkx in IWPEC 2009), but should be solvable in $2^{O(\sqrt{n}\log n)}$ by using the fact that ...
user avatar
6 votes
Accepted

Name for "uniformly polynomial" subclass of XP?

I don't think this subclass of $\textsf{XP}$ has been studied in the literature (and given a name). One reason why researchers might shy away from studying this subclass, is that it is not closed ...
user avatar
6 votes
Accepted

Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?

In Downey and Fellows' 2013 book (Fundamentals of Parameterized Complexity; Section 2.2), they mention an example of a problem in non-uniform FPT (Graph Linking Number) and briefly discuss that it's ...
user avatar
6 votes

W[1]-hard problems with FPT time approximation algorithms

In [1], the authors prove that MaxSAT parametrized by the clique-width (resp. neighbor diversity) of the incidence graph of the CNF formula has an FPT-AS (Fixed Parameter Tractable Approximation ...
user avatar
  • 1,855
6 votes

W[1]-hard problems with FPT time approximation algorithms

In Defective Coloring we are given a graph $G$ and an integer $\Delta^*$ and are asked to partition the vertices of $G$ into the minimum possible number of color classes so that each class induces a ...
user avatar
5 votes
Accepted

Natural maximization problems in FPT

Here are a few: Max Cut: Can one color the vertices of an input graph $G$ black and white so that at least $k$ edges go from black to white? Max Sat: Is there an assignment that satisfies at least $k$...
user avatar
  • 3,236
5 votes

ETH: k-SAT vs. SAT?

A better way to define these exponents is if you ask about the running time in the form $c^n\cdot poly(|F|)$, where $poly(|F|)$ is an arbitrary polynomial of the input size. Then artifacts like the $3^...
user avatar
  • 250
5 votes

Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

There is a recent paper by Glencora Borradaile, Hung Le: Optimal Dynamic Program for r-Domination Problems over Tree Decompositions (IPEC 2016). Here they show that there is an algorithm that given as ...
user avatar
  • 3,236

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