# 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

75 questions
Filter by
Sorted by
Tagged with
72 views

### Parameterized intractability for Twin cover

I am currently working on Parameterized algorithms, especially on the complexity of the given problem when parameterized by twin cover as the parameter. I have read the following papers on formulating ...
100 views

### Need more explaination on this 'generality'

I am trying to understand how this proof works I don't understand, why this f' is nondecreasing? What kind of generality makes us come up with such kind of assumption? Please, I am weak.
• 101
77 views

### Parameters: Twin cover and Vertex cover

I am a research scholar, currently working on parameterized algorithms. I am working on a problem and have been exploring various parameters for which the problem remains unsolved. I have read the ...
67 views

### Tractability with respect to multiple parameters

I am working on the decision version of an NP-complete problem. The problem is known to be fixed parameter tractable(FPT) with respect to the solution size $k$ as the parameter. If I consider another ...
1 vote
51 views

### The "branch-depth" parameter and its use in FPT algorithms

Let $P=(v_1,\dots,v_q)$ be an induced path in the undirected graph $G(V,E)$. In , the authors define the branch depth of $P$ to be $b(P)=|N_G[\{v_1,\dots,v_{q-1}\}]|-1$. Further, in  it is shown ...
• 75
78 views

### Is there FPT or XP algorithms known for Shortest Steiner cycle and $(a,b)$-Steiner path problem

Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems. The Shortest Steiner cycle problem is defined ...
1 vote
51 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 ...
181 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 ...
• 577
62 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 ...
• 75
141 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 ...
• 577
35 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 ...
81 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,399
59 views

• 455
385 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,432
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 ...
182 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
105 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
264 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 ...
139 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
147 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$?
• 12.5k
1k 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 ...
• 9,378
1 vote
167 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
109 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
241 views

• 12.5k
398 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
661 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?
• 1,984
248 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,113
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
359 views

• 113
1 vote