# Questions tagged [fixed-parameter-tractable]

algorithms for parameterized problems where the run-time is polynomial in the input size, but depends arbitrarily on the parameter

64 questions
Filter by
Sorted by
Tagged with
65 views

### Exact FPT Algorithm for Continuous Euclidean $k$-Means

The continuous Euclidean $k$-means problem is defined as follows: Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ ...
57 views

319 views

### Complexity of SAT parameterized by treewidth

Many papers state that Boolean satisfiability is in FPT when parameterized by primal, dual, or incidence treewidth. What are the best known time complexities of these parameterized algorithms? In ...
3k views

### What is a natural problem in theory of computation?

In Stephen Cook's paper on the P vs NP problem, he states the following : Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm. My question ...
157 views

### Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?

I understand that Disjoint Feedback Vertex Set (= looking for a solution $X$ of size $k$ given a solution $W$ of size $k+1$ s.t. $X \subseteq V \setminus W$ ) can be solved in time $4^k poly(n)$, see ...
96 views

### Best algorithms for real linear programming

Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of ...
254 views

### Have people looked for parameterized algorithms for problems that are not in NP?

Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the ...
131 views

### What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?

In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$. $KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey ...
144 views

### What are the consequences if $W[i]=W[i-1]$?

$FPT=W$ does not collapse the $W$ hierarchy however falsifies $ETH$ belief. Is there non-trivial consequence if $W[i]=W[i-1]$ and any other consequence at $W$?
852 views

### W-hard problems with FPT time approximation algorithms

I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are: R1. W-hard. R2. Admit a (preferably constant) approximation algorithm ...
142 views

### When we say a parameter is good for a problem?

I am studying parameterized complexity. I have seen few parameterized algorithm for problems like vertex cover, feedback vertex set etc. I have difficulty in determining when a parameter is said to be ...
106 views

### Fixed dimension Integer programming minus LLL in fixed parameter $NC$?

If you remove LLL part then is remaining part of a. Lenstra algorithm b. Barvinok algorithm in $O(f(n)(\log(mL))^c)$ time on $O(g(n)(mL)^c)$ processors with fixed $c>0$ in fixed $n$ dimension, $m$ ...
233 views

388 views

### On integer programming

Integer programming is NP-hard. What is the status of integer programming problem that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ ...
644 views

### Hard problems for bounded vertex cover

We know that list coloring problem is W-hard when parameterized by vertex cover. Are there any other problems which are also W-hard parameterized by vertex cover?
235 views

### Nonstandard dual parametrization of graph problems

One fundamental result in parameterized complexity of graph problems is that VERTEX COVER parameterized by the solution size $k$ is fixed-parameter-tractable (FPT). On the other hand, when ...
90 views

### Fixed-parameter tractability of string homomorphism

String homomorphism is a function $h: \Sigma \to \Sigma^*$, which naturally defines a homomorphism on strings from $\Sigma^*$ with respect to concatenation. We denote $H(s) = h(s_1)h(s_2)\dots h(s_n)$ ...
340 views

418 views

### Which graph problems are $W$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), I was wondering how parameterized problems are affected by these attributes. ...
433 views

### FPT algorithm for mixed integer program

It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer ...
100 views

### Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm

EDIT: I'm sorry if this question belongs more to cs.SE, I've had a dilemma about where to put it. Please let me know if it's inappropriate. I'm currently implementing the Vertex Cover problem solving ...
216 views

### Is it known whether counting $q$-dimensional $p$-matching is $\#W$-Hard?

The $q$-Dimensional $p$-Matching is defined as follows: Given disjoint universes $U_1,\ldots,U_q$, think of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element from ...
214 views

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight subset $S \... 0answers 130 views ### Is minimum weight simple cycles through specified vertics fixed parameter tractable? The problem formulation is as follows: Input: Undirected graph$G=(V,E)$, a set of vertices$S\subseteq |V|$, a weight function$w:E\to \mathbb{R}$and a threshold$T\in \mathbb{R}$. Parameter:$|S|=...
A lot of effort has been invested in finding simple k-paths, as well as in finding vertex disjoint paths. Is there any known parametrized algorithm that given a graph $G=(V,E)$, decides whether there ...
When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree ...