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

Filter by
Sorted by
Tagged with
1 vote
0 answers
30 views

Is there an FPT or XP algorithm known for this version of $k$-edge disjoint paths problem?

The shortest $k$-edge disjoint paths problem is defined as follows: Input: An undirected graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Find (if exist) $k$-pairwise ...
user avatar
-4 votes
0 answers
28 views

Solving K-Flip SAT problem in Polynomial time

Given a dataset with N variables, M clauses in CNF form, and a randomly generated truth assignment T. I am trying to find a truth assignment T' that flips at most k variables and satisfies more ...
user avatar
2 votes
1 answer
165 views

Maximize a special monotone submodular function - is it easier?

I am looking for a way to optimize the function $f$, defined below. First, fix some positive integer $k$ and let $c_1$ and $c_2$ be non-negative vectors in $\mathbb{R}^n$. Let $g$ be an increasing ...
user avatar
0 votes
0 answers
51 views

Parameterized Complexity of Vertex Multicut

Let $G$ be an undirected graph, $\{(s_1,t_1),\dots,(s_k,t_k)\}$ a collection of pairs of vertices, and $p$ an integer. The Vertex Multicut problem asks if there is a set $S$ of at most $p$ vertices ...
user avatar
  • 23
2 votes
1 answer
125 views

Parameterized algorithm when the parameter is not known in advance?

In the setting of parameterized algorithms, we are typically given the problem instance as well as the value of the parameter. However, it seems like in applications the value of the parameter should ...
user avatar
0 votes
0 answers
26 views

Profitable Dominating Set is FPT for multiple parameter

In Profitable Dominating Set, we are given a graph $G$, integers $k,W,P \in \mathbb{N}$, a weight function $w : V (G) \rightarrow \mathbb{N}$ and a profit function $p : V (G) \rightarrow N$. The ...
user avatar
  • 1
3 votes
0 answers
76 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$ ...
user avatar
0 votes
0 answers
59 views

Dynamic programming algorithm to find a colorful subset of disjoint sets

Suppose there is a set $F=\{X_1 ,...,X_m\}$, such that $\forall 1\leq i\leq m: |X_i|=3.$ Suppose we color the elements of $\bigcup F$ in $3k$ colors. We wish to know if there is a subset $F'\...
user avatar
2 votes
1 answer
183 views

DFSA and NFSA intersection problem

Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem. For unbounded $k$ it is known the problem is $PSPACE$ ...
user avatar
  • 12.5k
17 votes
0 answers
563 views

Linear-time algorithm to test if clique number equals degeneracy bound?

Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique. A well-known bound on the clique number is $\omega\le d+1$, which is ...
user avatar
7 votes
1 answer
147 views

Reducing Parameterized Problems (whose solution size can be "large") to W[i]-complete problems (for fixed i)

Note: Originally, this question was asked via a comment in this question, but was asked to post a separate question. :) I'm looking for any known reductions of the following: Given a parameterized ...
user avatar
2 votes
1 answer
109 views

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

I'm curious about the following general problem: Suppose that we have a parameterized problem whose input is $x$ and parameter is $k$ (which is NOT the size of a solution but something about the input)...
user avatar
9 votes
1 answer
208 views

What is the best upper bound on the running time of the graph minor algorithm?

A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained ...
user avatar
  • 91
3 votes
3 answers
713 views

Best parameterized algorithm for maximum clique

I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "...
user avatar
2 votes
1 answer
95 views

Diameter vs. Tractability

I would like to find examples of (unweighted) optimization problems $\Pi$ that satisfy 1) or 2): 1) $\Pi$ is NP-hard but polytime solvable in the class of graphs with diameter $\le k$, for all $k\ge ...
user avatar
4 votes
1 answer
364 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 ...
user avatar
  • 1,398
11 votes
2 answers
3k views

What is a natural problem in theory of computation?

In Stephen Cook's paper on the P vs NP problem,[1] he states the following [2]: Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm. My question ...
user avatar
3 votes
1 answer
166 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 ...
user avatar
  • 161
2 votes
0 answers
102 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 ...
user avatar
  • 12.5k
10 votes
0 answers
261 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 ...
user avatar
0 votes
0 answers
138 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 ...
user avatar
  • 12.5k
3 votes
0 answers
145 views

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

$FPT=W[1]$ 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[1]$?
user avatar
  • 12.5k
9 votes
5 answers
936 views

W[1]-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[1]-hard. R2. Admit a (preferably constant) approximation algorithm ...
user avatar
  • 9,358
1 vote
1 answer
150 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 ...
user avatar
  • 121
1 vote
0 answers
107 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$ ...
user avatar
  • 12.5k
1 vote
1 answer
239 views

Fixed parameter tractable Integer Programming and $FPP$

Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $...
user avatar
  • 12.5k
3 votes
1 answer
144 views

Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$...
user avatar
  • 31
3 votes
0 answers
104 views

Fixed parameter Integer Programming circuit depth complexity

It is well known Lenstra's and Kannan's algorithm achieves $n$-variable parameter $L$-bit integer programming solvability in $O(n^nL)$ time and $O(L)$ space. If implemented as an arithmetic circuit ...
user avatar
  • 12.5k
2 votes
0 answers
206 views

Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth

I would like to cite a paper/report/etc that solves the following problem polynomially in $n$: Given a weighted directed graph $G=(V,E)$, $|V|=n$, of bounded treewidth $k \in \mathbb{N}$ and a source-...
user avatar
3 votes
1 answer
136 views

Consequences of faster parameterized integer programming

Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space. Is there any consequence if it can be done in $k^{O(k^\alpha)}$ time and $O(k^c)$ space for some $\alpha\in(0,1)...
user avatar
  • 12.5k
5 votes
2 answers
391 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$ ...
user avatar
  • 12.5k
7 votes
3 answers
648 views

Hard problems for bounded vertex cover

We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?
user avatar
  • 1,984
8 votes
2 answers
244 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 ...
user avatar
4 votes
0 answers
92 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)$ ...
user avatar
16 votes
0 answers
352 views

Complexity of the homomorphism problem parameterized by treewidth

The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows: Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in $...
user avatar
  • 7,350
3 votes
1 answer
476 views

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

My research problem involves solving a special instance of the 3-Hitting Set problem, and I was wondering whether my result is actually significant (i.e. if it is better than the best known result for ...
user avatar
-6 votes
3 answers
175 views

Fixed parameter tractability [closed]

Lets say I have an algorithm with complexity $O(n^k)$ where $n$ is the size of the input and $k$ is a parameter. Clearly this is superpolynomial; but in fixed parameter tractability we restrict $k$ to ...
user avatar
6 votes
2 answers
248 views

Parametrized complexity of the 2-Long Paths Problem

Consider the following problem: Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$...
user avatar
  • 9,358
11 votes
1 answer
389 views

Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas

The k-FLIP SAT parametrized problem is defined as: Input: a 3-CNF formula $\varphi$ with $n$ variables and a truth assignment $\sigma : [n] \to \{0,1\}$ Parameter: $k$ Question: can we transform the ...
user avatar
10 votes
1 answer
607 views

Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic

Berman–Hartmanis conjecture: all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms[1]. I am interested in a more fine-grained ...
user avatar
15 votes
2 answers
1k views

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

The $k$-cycle problem is as follows: Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges. Question: Does there exist a (proper) $k$-cycle in $G$? Background: For any ...
user avatar
10 votes
1 answer
840 views

Complexity of k-clique for hypergraphs

Classic Problem: Let a number $k$ be given. The $k$-clique problem is as follows. Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent? ...
user avatar
-1 votes
1 answer
178 views

FPT algorithm equivalent definitions [closed]

On this page, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover. But how the complexity given for Vertex Cover, $O(kn+1.274^k)$ (...
user avatar
  • 113
1 vote
1 answer
157 views

Natural maximization problems in FPT

Is there a natural (and hopefully well-known) maximization problem that is known to be in FPT? For instance, Vertex Cover is in FPT, but it's a minimization problem. I'm looking for natural ...
user avatar
6 votes
1 answer
232 views

Easy decision hard counting Parametrized

It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P. Is there a problem, that exhibits the same behavior in ...
user avatar
  • 447
8 votes
2 answers
491 views

Implications of a problem being in XP when parameterized by diameter

Let $X$ be an NP-complete graph problem. Suppose $X$ is solvable in polynomial time on graphs of bounded diameter. In other words, $X$ parameterized by diameter is in XP. (Recall a problem is in XP if ...
user avatar
  • 3,160
3 votes
0 answers
126 views

Multiple knapsack fpt?

It was an open question whether multiple knapsack is fpt wrt standard parameter. Since at SODA 2009 Jansen has presented an EPTAS for multiple knapsack and an EPTAS implies the existense of an fpt ...
user avatar
  • 57
7 votes
0 answers
161 views

Is 4-colors precoloring extension for planar graphs fixed parameter tractable?

Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable). Assume you are given a set of $k$ constraints of the form "$v_i \text{ is ...
user avatar
  • 9,358
10 votes
2 answers
424 views

Which graph problems are $W[1]$-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. ...
user avatar
  • 9,358
5 votes
1 answer
465 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 ...
user avatar