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
70
questions
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 ...
- 139
-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 ...
- 1
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 ...
- 547
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 ...
- 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 ...
- 547
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 ...
- 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$ ...
- 1,389
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'\...
user62160
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$ ...
- 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 ...
- 1,156
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 ...
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)...
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 ...
- 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 "...
- 600
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 ...
- 455
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 ...
- 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 ...
- 113
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 ...
- 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 ...
- 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 ...
- 101
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 ...
- 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]$?
- 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 ...
- 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 ...
- 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$ ...
- 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 $...
- 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$...
- 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 ...
- 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-...
- 103
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)...
- 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$ ...
- 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?
- 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 ...
- 2,101
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)$ ...
- 191
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 $...
- 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 ...
- 53
-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 ...
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$...
- 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 ...
- 22.3k
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 ...
user17918
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 ...
- 4,900
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?
...
- 4,900
-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)$ (...
- 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 ...
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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.
...
- 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 ...
- 203