# 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

61 questions
Filter by
Sorted by
Tagged with
78 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 ...
121 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 ...
86 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)...
199 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 ...
475 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 "...
95 views

139 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$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$...
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 ...
168 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-...
132 views

397 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 ...
155 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 ...
240 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$...
327 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 ...
567 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. I am interested in a more fine-grained ...
949 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 ...
530 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? ...
146 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)$ (...
149 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 ...
227 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 ...
476 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 ...
119 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 ...