# Tag Info

## Hot answers tagged parameterized-complexity

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 ...

### 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 ...
• 2,743
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 ...
• 1,158

### 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]
• 2,530
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 ...
• 7,653
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 ...
• 22.3k
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 ...
• 5,225
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 ...
• 5,225
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 ...
• 5,225
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 ...
• 50.2k
Accepted

• 250