Skip to main content
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 ...
Christian Komusiewicz's user avatar
20 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 ...
Thomas's user avatar
  • 2,803
17 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 ...
Denis's user avatar
  • 8,903
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 ...
Bart Jansen's user avatar
  • 5,275
11 votes
Accepted

Maximum Treewidth of a Graph 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, ...
PsySp's user avatar
  • 840
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 ...
daniello's user avatar
  • 3,266
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!). ...
Michael Lampis's user avatar
7 votes

Maximum Treewidth of a Graph with $m$ Edges

The best known upper bound of the treewidth in terms of the number of edges of a graph is as follows: the pathwidth (and therefore also the treewidth) of any graph on $n$ vertices and $m$ edges is at ...
Serge Gaspers's user avatar
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 ...
Michael Lampis'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 ...
holf's user avatar
  • 2,174
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 ...
Ronald de Haan's 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 ...
Ronald de Haan's user avatar
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 ...
Michael Lampis's user avatar
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" ...
daniello's user avatar
  • 3,266
6 votes

FPT algorithm for mixed integer program

The complexity of Lenstra's algorithm for mixed-integer programming in his paper runs as $2^{O(n^3)}*poly(d, \phi)$ where there are $n$ integer variables, $d$ continuos variables, and $\phi$ is the ...
Robert Hildebrand's user avatar
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" ...
Ted's user avatar
  • 329
6 votes
Accepted

Complexity of induced Steiner Tree problem

This problem is well-studied under the name "three-in-a-tree" and more generally "k-in-a-tree". A polynomial-time algorithm for three-in-a-tree is given in [1], but the complexity ...
Laakeri's user avatar
  • 1,786
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 ...
daniello's user avatar
  • 3,266
5 votes

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

(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 ...
Amir Nikabadi's user avatar
5 votes

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

The k-cut problem is to remove a minimum number of edges to create at least k components. W[1] hard when parameterized by k but admits a 2-approximation for any k.
Chandra Chekuri's user avatar
5 votes
Accepted

Proving membership in W-hierarchy when problem is not parameterized by its solution size

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 ...
Christian Komusiewicz's user avatar
5 votes

Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

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 ...
daniello's user avatar
  • 3,266
5 votes
Accepted

Treewidth relations between Boolean formulas and Tseitin encodings

There is a relation between the treewidth of a circuit and the primal treewidth of its Tseitin transformation but you will have to take the fan-in of the circuit into account, which is large when ...
holf's user avatar
  • 2,174
4 votes
Accepted

Hardness of Subgraph isomorphism problem for sparse pattern graph

It is $W[1]$-hard even when $G$ has maximum degree $3$, but $FPT$ if $G$ has constant treewidth (all the above examples have constant treewidth). See the paper Everything you always wanted to know ...
daniello's user avatar
  • 3,266
4 votes

Hard problems for bounded vertex cover

I don't know if there is any pure graph theoretic problem which is hard in bounded vertex cover, and if there is any it is very interesting for me to see such problem. However, here is a problem of ...
Saeed's user avatar
  • 3,440
4 votes

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

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 ...
Laakeri's user avatar
  • 1,786
4 votes
Accepted

Parameterized complexity of tree/branch decomposition

This paper https://arxiv.org/abs/2104.07463 gives an overview of treewidth algorithms in Table 1. Similar table also exists in Wikipedia. The situation for parameterized computing of an optimal tree ...
Laakeri's user avatar
  • 1,786
4 votes

Treewidth relations between Boolean formulas and Tseitin encodings

Actually, we can transform any Boolean Circuit $C$ that uses only $\wedge$, $\vee$, and $\neg$ gates of treewidth $k$ into a CNF whose primal treewidth is within a constant factor of $k$, where this ...
raki123's user avatar
  • 41
3 votes
Accepted

OR-weft Hierarchy

First of all: your definition of $WCS[C_{t,d}]$ does not match the usual one. The common definition asks for a satisfying assignment of Hamming weight exactly $k$, rather than at most $k$, and this ...
Bart Jansen's user avatar
  • 5,275

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