# Tag Info

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 ...
• 7,615
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 ...
• 1,786
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,275
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 ...
• 4,630
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

### 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 ...
• 3,712
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 ...
• 5,275

### 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,712

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

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

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

### 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,712

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

### 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; ...
• 12.2k
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 ...
• 37.4k

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

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

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

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

### 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
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 ...
• 51.1k

### 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 ...
• 51
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 ...
• 5,127
### Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?
I found the solution, it is also mentioned in the book in chapter 4.1. We start by taking a subgraph with $k+1$ arbitrary vertices instead of the whole graph, so the whole vertex set is a $k+1$-...