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,803
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 ...
• 8,843
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,265
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, ...
• 840
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 ...
• 3,266

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!). ...
• 3,698

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 ...
• 5,116

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 ...
• 3,698

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 ...
• 2,174
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 ...
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 ...
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 ...
• 3,698

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" ...
• 3,266

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" ...
• 329
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 ...
• 1,766

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 ...
• 3,266

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

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.
• 6,999
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 ...

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 ...
• 3,266
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 ...
• 2,174
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 ...
• 3,266

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 ...
• 3,440

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 ...
• 1,766
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 ...
• 1,766

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 ...
• 41
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 ...
• 5,265
Theorem 15.3 of the recent "Parameterized Algorithms" textbook by Cygan et al. states the following: "Let $L, R ⊆ \Sigma^*$ be two languages. If there exists an OR-distillation of L into R, then \$L\...