19 votes
Accepted

What is a natural problem in theory of computation?

To be clear, it's not meant to be formalizable. It's not a theorem, it's an observation about the world -- it's okay if "natural" is subjective here. For analogy, if someone says "differentiation is ...
usul's user avatar
  • 7,615
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 ...
Bart Jansen's user avatar
  • 5,255
13 votes
Accepted

Best parameterized algorithm for maximum clique

Maximum clique in graphs with degree $d$ can be reduced to $n$ instances of maximum clique in a graph with at most $d$ vertices: for each vertex, compute maximum clique in the induced subgraph of the ...
Laakeri's user avatar
  • 1,767
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,255
10 votes
Accepted

What is the best known FPT result for 3-hitting set?

According to the Parameterized Complexity Wiki, the currently best known FPT algorithm for 3-Hitting-Set has a complexity of $2.076^k \cdot n^{O(1)}$, the algorithm is from the PhD thesis of Magnus ...
Jan Johannsen's 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 ...
daniello's user avatar
  • 3,266
9 votes

Nonstandard dual parametrization of graph problems

I think this problem is FPT. Suppose that the graph contains a path on $2k+1$ vertices. Then, I claim the answer is YES: we select the second, fourth, sixth, etc. vertices of this path in a solution ...
Michael Lampis's user avatar
7 votes
Accepted

Consequences of faster parameterized integer programming

An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally ...
Bart Jansen's user avatar
  • 5,255
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
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
Accepted

Complexity of SAT parameterized by treewidth

FPT results The complexity of SAT, #SAT and MaxSAT parametrized by primal and incidence treewidth is FPT for all cases and of the form $2^{ck}\|F\|^d$ where $\|F\|=\sum_{C \in F} |var(C)|$ is the ...
holf's user avatar
  • 2,174
6 votes

When we say a parameter is good for a problem?

In my opinion, this is actually one of the main questions in parameterized algorithms. There is a number of articles that discuss the "art" of problem parameterization, I list a few of them below. In ...
Christian Komusiewicz's user avatar
6 votes
Accepted

Fixed parameter tractable Integer Programming and $FPP$

You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are ...
Ronald de Haan'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
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

Nonstandard dual parametrization of graph problems

Let $n:=|V(G)|$ and $m:= |E(G)|$. The dual parameter $m-k$ is always at least as large as $m-n$ which in turn is at least as large as the size of a feedback edge set, a set of edges whose removal ...
Christian Komusiewicz's user avatar
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

On integer programming

It's NP-hard. Given an integer programming problem $P$, add an irrelevant variable $z$ with no constraints; call the resulting problem $P'$. Now if $P$ has no solutions, then $P'$ has no solutions; ...
D.W.'s user avatar
  • 12k
5 votes
Accepted

On integer programming

(1) As finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete (indeed, it is $\mathsf{ASP}$-complete, see Theorem 3.5 of [1]), and we can encode 3SAT as an integer ...
Joshua Grochow's user avatar
5 votes

Best parameterized algorithm for maximum clique

I don't know if you have checked the tractability of the problem when parameterized by the degeneracy of the input graph (since degeneracy $\leq \Delta$ ). However, there is an algorithm for the ...
Amir Nikabadi's user avatar
5 votes

Best parameterized algorithm for maximum clique

In terms of using parameters that are possibly much smaller than degeneracy and never larger, there are two results that improve over degeneracy. First, since the algorithm for degeneracy employs a ...
Christian Komusiewicz'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
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

What is a natural problem in theory of computation?

It roughly boils down to whether the problem definition could be circular: An artificial problem is one constructed to fill its class criteria. A natural problem does not rely on its method of ...
Lem's user avatar
  • 51
4 votes
Accepted

Diameter vs. Tractability

For part (1), if you allow additional restrictions on your graph class, then independent set, Hamiltonian circuit, dominating set, etc., are NP-hard on arbitrary planar graphs but FPT on planar graphs ...
David Eppstein's user avatar
4 votes
Accepted

DFSA and NFSA intersection problem

Regarding question (1): As long as $k$ is $\Omega(n^c)$ for some $c > 0$, then the problem is $PSPACE$-complete. See this paper by Klaus-Jörn Lange and Peter Rossmanith (1992) for some related ...
Michael Wehar's user avatar

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