The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [parameterized-complexity]

The study of the computational complexity of problems with respect to more than one parameter.

84 questions
Filter by
Sorted by
Tagged with
59 views

$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?

Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following: $FPT = XPuniform\implies EPTAS = PTAS$. Fundamentals of Parametrized complexity on page $534$ has ...
235 views

Difficulty of graph coloring and independent set?

Given a graph on $n$ vertices it is strongly $NP$-complete to decide it is $3$-colorable while it is easy to decide it is $n$-colorable. Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-...
76 views

What is the motivation behind W[P]?

I've been researching Parameterized Complexity Theory, and I've been puzzled by the definition of W[P]. Why is the number of non-deterministic steps bounded by $log|n|$? What is the intuition I should ...
278 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 ...
182 views

Find a pair of nodes with maximum sum of distances in k given trees

For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
1k views

Is parameterized complexity going to be the future of complexity theory?

I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. To me it appears that researchers in parameterized complexity are very active (I ...
277 views

Parameterized complexity of inclusion of regular languages

I am interested in the classic problem REGULAR LANGUAGE INCLUSION. Given a regular expression $E$, we denote by $L(E)$ the regular language associated to it. (Regular expressions are on a fixed ...
149 views

227 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$...
137 views

“k-Swap SAT” problem

I would like to know if the following NP-complete problem has a name and has been studied: Input: Given a CNF formula $\varphi$ on $n$ variables, a truth assignment $\sigma:[n] \to \{T,F\}$ and an ...
292 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 ...
261 views

Major open problems on polynomial kernel (non) existence

We are not able to settle the (non) existence of a polynomial kernel for a parametrized combinatorial NP-complete problem (we also tried to apply some recent lower bound techniques to prove the non ...
271 views

complexity of graph 2.5-coloring

My question is inspired by this one. ​ I define 2.5-coloring to be the parameterized problem Instance: an integer j and an n-vertex non-empty simple graph G Parameter: integer k Output: if there is ...
129 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)$ (...
325 views

Gentle introduction to the algorithmic aspects of tree-depth

Treewidth and pathwidth are popular parameters, measuring the closeness of a graph to a tree or a path, respectively. Indeed, it seems treewidth is so popular it is featured in many papers, books, and ...
143 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 ...
396 views

ETH: k-SAT vs. SAT?

Let SAT$_v$ be the language of those instances of SAT that contain variables $[v] = \{0,1,\dots,v-1\}$, let $k$-SAT be the language of those instances of SAT in which every clause has at most $k$ ...
220 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 ...
415 views

complexity of Sokoban with a small number of boxes

(I asked a very concise version of this one month ago on cs.stackexchange, and although it got edited, it was not (otherwise) responded to.) In this post, for positive integer values $k$, "$k$-...
103 views

Problem with a group as complexity parameter?

I am currently studying a complexity problem related to symmetries, and am considering a study of the parameterized complexity of the problem. In theory, any part of the input can be fixed as a ...
465 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 ...
56 views

Parameterized Complexity of Minimum Type Selection

Consider the following problem that I call »Minimum Type Selection«: Input: $k$ sets of bit vectors, each of length $n$ and a number $l$. Question: Is it possible to pick exactly one bit vector from ...
145 views

312 views

Algorithmic advantages of pathwidth over treewidth

Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth ...
196 views

Graph theory: definiton of the crown of a graph

I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand: A crown of a ...
373 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 ...
326 views

Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the Complexity Zoo for definitions. An alternative definition defines $\mathsf{W}[t]$ ...
200 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 ...
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 ...
An FPT-reduction between parameterized problems $P$ and $Q$ is a pair of functions $f$ and $p$, such that every instance $x$ of $P$ with parameter $k$ is mapped to an instance $f(x,k)$ of $Q$ with ...