Online Compendium of Parameterized Problems <beta>

order by : name | complexity | categories

# A B C D E F G H I J K L M N O P Q R S T U V W X Y Z#

2-Colored Directed Vertex Separation Number

Instance : A directed acyclic graph $G = (V, A)$ , a coloring $c : V$ $
ightarrow {$ , $1, 2}$ ; positive integers $k_1$ and $k_2$ .
Question : Is there a topological sort $f$ of $G$ such that for all $i, 1$ $\leq i \leq \vert V\vert$ , we have that $width_{1,f(i)}$ $\leq k_1$ and $width_{2,f(i)}$ $\leq k_2$ (For $\epsilon \in$ $\{1, 2\}$ , $width_{\epsilon,f(i)}$ is the number of vertices $v$ such that $c(v) = \epsilon$ , $f(v) \leq i$ and such that there is an arc $(v, v')$ $\in A$ with $i \leq f(v')$ ) ?

Parameter : $k_1$ , $k_2$ .

Complexity : W[t]-hard for all (reduction from a directed variant of Bandwidth) [ BGT98 ]

3-CNF Satisfiability

Instance : A boolean formula in conjunctive normal form (CNF) with variables in and each clause of at most literals.
Question : Is there a satisfying assignment $\alpha : X \rightarrow \{TRUE, FALSE\}$ for ?

Parameter : .

Complexity : [ Fer05 ]
---------------------------------------------------------------------------------------------------------
Parameter : $\vert X\vert$ .

Complexity : $O(1.619^{\vert X\vert}$ [ MS85 ] , $O(1.5045^{\vert X\vert})$ [ Kul99 ]

-Balanced Separator

Instance : A graph ; a positive integer .
Question : Does there exist a set of vertices of cardinality at most such that every connected component of has at most vertices ? ( is a fixed constant) ?

Parameter : .

Complexity : W[1]-hard, in W[P] (membership: reduction to Bounded Nondeterminism Turing Machine Computation; hardness : reduction from Clique) [ Ces03 ]

Above Guarantee Vertex Cover

Instance : A graph ; a positive integer .
Question : Is there a vertex cover in of size at most $\mu(G) + k$ , where $\mu(G)$ denotes the size of a maximum matching in (a vertex cover is a subset $V' \subseteq V$ such that for all $(u,v) \in E$ at least one of or is in ) ?

Parameter : .

Complexity : [ RO08 ]

Remark : Equivalent to Above Guarantee Vertex Cover for graphs with a perfect matching, Almost 2-SAT and Konig Vertex Deletion for graphs with a perfect matching [ MRSSS07, MRSS08 ].

Above Guarantee Vertex Cover for graphs with a perfect matching

Instance : A graph with a perfect matching; a positive integer .
Question : Is there a vertex cover in of size at most $\mu(G) + k$ , where $\mu(G)$ denotes the size of a perfect matching in (a vertex cover is a subset $V' \subseteq V$ such that for all $(u,v) \in E$ at least one of or is in ?

Parameter : .

Complexity : [ RO08 ]

Remark : Equivalent to Above Guarantee Vertex Cover, Almost 2-SAT and Konig Vertex Deletion for graphs with a perfect matching [ MRSSS07, MRSS08 ].

Almost 2-SAT

Instance : A -CNF formula; a positive integer .
Question : Is it possible to remove at most clauses so that the resulting -CNF formula is satisfiable ?

Parameter : .

Complexity : [ RO08 ]

Remark : Equivalent to : Above Guarantee Vertex Cover, Above Guarantee Vertex Cover for graphs with a perfect matching, König Vertex Deletion For Graphs With a Perfect Matching.

Annotated Face Cover

Instance : A plane graph $G = (V, E)$ (that is, an embedding of a planar graph on the plane) with face set $F$ ; a function $mu_V : V ightarrow {active, marked}$ ; a function $mu_F : F ightarrow {active, marked}$ .
Question : Is there a set $C subseteq {f $ $in F vert mu_F $ $(f) = $ $active}$ with $vert Cvert leqslant k$ and such that for each $v in {u$ $ in V $ $vert mu_V(u)$ $= active}$ , there is a face in $C$ whose boundary includes $v$ ?

Parameter : an integer .

Complexity : $O^{?}(4.6056^k)$ [ AL04 ]

Arc Preserving Longest Common Subsequence

Instance : An alphabet $\Sigma$ , sequences over $\Sigma$ such that has elements and , sets of arcs $P_A \subset n \times n$ , $P_B \subset m \times m$ .
Question : Is there an arc-preserving subsequence of and of length at least ?

Parameter : .

Complexity : W[1]-hard [ E ]

Remark : A subsequence is arc-preserving if whenever both endpoints of an arc from either or are found in , the corresponding symbols are joined by an arc in the other sequence.

Bandwidth

Instance : A graph ; a positive integer .
Question : Is there a linear layout , , $vert Vvert$ such that implies $leq k$ $vert f(u)$ ?

Parameter : .

Complexity : W[t]-hard for all t (reduction from Uniform Emulation On A Path; the problem remains W[t]-hard for all t when the given graph is directed and the layout must respect arc direction, or when the given graph is a tree) [ BDFW94, BFH94 ]

Bipartite Colorful Neighborhood

Instance : A bipartite graph .
Question : Is there a -coloring of such that there exists a set $S \subseteq V_0$ with a least vertices such that each element of has a colorful neighborhood, i.e. each element of has at least one neighbor of each color ?

Parameter : .

Complexity : [ LS05 ]

Remark : Equivalent to Set Splitting.

Bipartite Graph Embedding

Instance : Bipartite graphs and .
Question : Is there an embedding of into ?

Parameter : $\vert H\vert$ .

Complexity : W[1]-hard [ DF99 ]

Bipartite Matching Cardinality

Instance : A bipartite graph .
Question : Does have matchings ?

Parameter : .

Complexity : FPT [ IRT78 ]

Bipartization by edge removal

Instance : A graph .
Question : Does there exist a subset $E' \subseteq E$ of cardinality at most whose removal makes bipartite (or equivalently hits every odd cycle of ) ?

Parameter : .

Complexity : [ GGH+06 ]

Bipartization by Edge Replacing With Length-2 Paths

Instance : A graph .
Question : Is there a set $C \subseteq E$ of cardinality at most such that replacing each edge in by a -path produces a bipartite graph ?

Parameter : .

Complexity : [ GGH+06 ]

Remark : Equivalent to Bipartization by Edge Removal.

Bipartization Improvement

Instance : A graph , an odd cycle transversal $C \subseteq V$ .
Question : Is there an odd cycle transversal $C' \subseteq V$ with $\vert C'\vert < \vert C\vert$ ?

Parameter : .

Complexity : $O(3^k \cdot n \cdot m)$ [ RKV04 ]

Remark : An odd cycle transversal is a set of vertices whose removal makes the graph bipartite.

Bounded Degree Red-Blue NonBlocker

Instance : A graph of maximum degree a fixed constant $d \geqslant 2$ , a coloring of the vertices $c : V \rightarrow \{red,blue$ .
Question : Does there exist a set of red vertices of cardinality at most such that every blue vertex has at least one neighbor that does not belong to ?

Parameter : .

Complexity : W[1]-hard [ DF99 ]

Bounded Factor Factorization

Instance : A -bit positive integer .
Question : Is there a prime factor of such that ?

Parameter : .

Complexity : randomized FPT [ FK92 ]

Bounded Nondeterminism Turing Machine Computation

Instance : A single-tape, single-head nondeterministic Turing machine ; an input word ; positive integers and ( encoded in unary).
Question : Does there exist an accepting computation path of having at most steps and at most nondeterministic steps ?

Parameter : .

Complexity : W[P]-complete (hardness: reduction from Chain Reduction Closure) [ Ces03 ]

Remark : This problem reduces to Short Nondeterministic Turing Machine Computation when both and are parameters.

Chain Reduction Closure

Instance : A directed graph ; a positive integer .
Question : Does there exist a set of vertices of whose chain reaction closure is (a chain reaction closure of is the smallest superset of such that if $\in S$ and arcs , $\in A$ , then $x \in S$ ?

Parameter : .

Complexity : W[P]-complete (hardness : reduction from Weighted Monotone Circuit Satisfiability) [ ADF95 ]

Chordal Deletion

Instance : A graph : positive integers and .
Question : Does there exist and such that , and is a hole cover of (for and , we say that is a hole cover of a graph if the deletion of and makes the graph chordal ?

Parameter : , .

Complexity : FPT using iterative compression and bounded tree-width machinery [ Mar06 ]

Clique

Instance : A graph .
Question : Does there exist a subset of cardinality at most such that for all ?

Parameter : .

Complexity : W[1]-hard [ Nie06 ]

Clique Complement Cover

Instance : A graph .
Question : Does there exist $C \subseteq V$ with at most vertices such that $V \minus C$ induces a clique ?

Parameter : .

Complexity : [ Fer05a ]

Remark : Strongly related to Vertex Cover.

Clique for Almost Cluster Graphs

Instance : A graph that is a disjoint union of cliques with extra edges, a positive integer .
Question : Is there a clique of size in ?

Parameter : .

Complexity : [ GHN04 ]

Closest 3-Leaf Power ^K

Instance : A graph ; a positive integer .
Question : Can we transform into a -leaf power by adding and deleting at most edges (a graph is a - leaf power iff it is obtained from a tree by substituing every vertex by a clique of arbitrary size) ?

Parameter : .

Complexity : [ DGHN06 ]
Kernel : [ ]

Closest 3-Leaf Power Completion ^K

Instance : A graph ; a positive integer .
Question : Can we transform into a -leaf power by adding at most edges (a graph is a - leaf power iff it is obtained from a tree by substituing every vertex by a clique of arbitrary size) ?

Parameter : .

Complexity : [ DGHN06 ]
Kernel : [ ]

Closest 3-Leaf Power Deletion ^K

Instance : A graph ; a positive integer .
Question : Is there a subset $E' \subseteq E$ of cardinality at most such that the graph $(V, E \setminus E')$ is a -leaf power (a graph is a - leaf power iff it is obtained from a tree by substituing every vertex by a clique of arbitrary size) ?

Parameter : .

Complexity : [ DGHN06 ]
Kernel : [ ]

Closest 4-Leaf Power

Instance : A graph ; a positive integer .
Question : Is there a subset $E' \subseteq E$ of cardinality at most such that the graph $(V, E \setminus E')$ is a -leaf power (a graph is a -leaf power iff it results from replacing every vertex of a square of tree by a clique of arbitrary size) ?

Parameter : .

Complexity : [ DGHN08 ]

Remark : this result is also true if we just add (resp. delete) edges.

Closest Substring

Instance : A set of strings $s_1, \ldots, s_k$ over a finite alphabet $\Sigma$ , nonnegative integers and .
Question : Is there a string of length , and for $i = 1, \ldots, k$ , a substring of of length such that, for all $i = 1, \ldots, k$ , $d_H(s,s'_i) \leqslant d$ (here, denotes the Hamming distance between and ) ?

Parameter : .

Complexity : W[1]-hard [ Nie06 ]

Cluster Deletion

Instance : A graph G = (V,E); a positive integer k.
Question : Is there a subset E′ ⊆ E of cardinality at most k such that the graph (V, E ∖ E′) is a disjoint union of cliques ?

Parameter : k.

Complexity : O(1.77^k + n³) [ GGHN03 ] , O(1.53^k + n³) [ GGHN04 ]

Cluster Editing

Instance : A graph ; a positive integer .
Question : Can we transform into a disjoint union of cliques by adding and deleting at most edges ?

Parameter : .

Complexity : [ GGHN04 ] , [ GGHN03 ]

Remark : this problem was already known to be in FPT by a result of Cai [ C96 ].

Cluster Vertex Deletion

Instance : A graph ; a positive integer .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that the graph induced by $V \setminus V'$ is a disjoint union of cliques ?

Parameter : .

Complexity : $O(2^kk^9 + n^3)$ using iterative compression [ HKMN08 ]

Cograph Vertex Deletion

Instance : A graph .
Question : Does there exist $C \subseteq V$ with at most vertices and whose removal yields a cograph ?

Parameter : .

Complexity : [ GGHN04 ]

Remark : A graph is a cograph if and only if it has no path with four vertices as an induced subgraphs.

Colored Cutwidth

Instance : A graph $G = (V, E)$ ; an edge-coloring $c : E$ $
ightarrow {1$ , $ldots$ , $r}$ ; a positive integer $k$ .
Question : Is there a $1:1$ linear layout $f : V$ , $ldots$ , $vert Vvert}$ such that for each color $j in {1$ , $ldots$ , $k}$ and for each $i$ $1 leq i$ $leq vert Vvert$ - $1$ , we have $vert{(u, v)$ $in E :$ $c(u, v) =$ $j f(u)$ $leq i wedge$ $f(v) geq i + 1}vert$ $leq r$ ?

Parameter : .

Complexity : W[t]-hard for all $t$ (reduction from Longest Common Subsequence parameterized by $k$ ; the directed version of this problem, where $f(u) < f(v)$ if $(u, v) in E$ is also hard for W[t], for all $t$ ; the variant in which we refer to the size of ${(u, v) in E$ $:$ $c(u, v)$ $=$ $j wedge$ $f(u)$ $< i$ $wedge f(v)$ $geq i$ $+ 1}$ is also W[t]-hard, for all $t$ [ BFH94, BFH+00 ]

Colored Graph Automorphism

Instance : A bipartite graph with a (red- blue) coloring.
Question : Does there exist an automorphism preserving colors moving exactly blue vertices ? ?

Parameter : .

Complexity : W[1]-hard [ DF99 ]

Colored Grid Homomorphism

Instance : A square grid graph whose vertices are colored with colors ( $c \geqslant 2$ a fixed constant), and a colored graph .
Question : Is there an homomorphism from to ?

Parameter : $\vert H\vert$ .

Complexity : W[1]-hard [ GSS01 ]

Colored Proper Interval Graph Completion

Instance : A graph , a vertex coloring $c : V \rightarrow \{1, \ldots, k\}$ .
Question : Does there exist a proper interval supergraph of which respects ?

Parameter : .

Complexity : W[1]-hard [ KS96 ]

Connected Dominating Set

Instance : A graph ; a positive integer .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that the subgraph induced by is connected and, for all $u \in V \setminus V'$ there is a $v \in V'$ for which $(u,v) \in E$ ?

Parameter : .

Complexity : W[2]-hard [ Fer03 ]

Consecutive Block Minimization

Instance : An $m \times n$ binary matrix .
Question : Is it possible to permute the columns of to obtain a matrix that has at most blocks of consecutive 's ?

Parameter : .

Complexity : FPT [ DF99 ]

Remark : A block of consecutive 's is an interval of a row such that all entries in that interval are 's.

Constrained Minimum Vertex Cover in Bipartite Graphs

Instance : A bipartite graph with ; positive integers , .
Question : Is there a minimum vertex cover with at most vertices in and at most vertices in ?

Parameter : , .

Complexity : $O(1.26^{k_u+k_l} + n imes (k_u + k_l)$ [ CK03 ]

Constraint Bipartite Dominating Set

Instance : A bipartite graph with $V = V_1 \cup V_2$ .
Question : Does there exist a dominating set $D \subseteq V_1 \cup V_2$ with $\vert D \cap V_1\vert \leqslant k_u$ and $\vert D \cap V_2\vert \leqslant k_l$ ?

Parameter : , .

Complexity : W[2]-hard [ Fer05a ]

Constraint Bipartite Vertex Cover

Instance : A bipartite graph with $V = U \cup L$ .
Question : Is there a vertex cover with at most vertices and at most vertices in ?

Parameter : , .

Complexity : $O(2^{k_u + k_l}k_uk_l + (k_u + k_l)n)$ [ HDS91 ] , $O(1.3999^{k_u + k_l}$ [ FN01 ]

Crossing Number for Max Degree 3 Graphs

Instance : A graph whose vertices have maximum degree .
Question : Does have an embedding in the plane with at most edges crossing ?

Parameter : .

Complexity : $O(f(k) \times n^3)$ [ DF99 ]

Remark : the complexity follows from the Robertson-Seymour theorem.

Cutwidth

Instance : A graph .
Question : Is there a one-to-one mapping $f : V \rightarrow \{1, \ldots, n\}$ such that for every $1 \leqslant i \leqslant n$ , $\vert\{(u,v) \in E : f(u) \leqslant i \leqslant f(v)\}\vert \leqslant k$ ?

Parameter : .

Complexity : $O(f(k) \times n)$ [ Bod86 ]

Degree Three Subgraph Annihilator

Instance : A graph ; a positive integer .
Question : Is there a set of vertices $V' \subseteq V$ such that $G \setminus V'$ has no subgraph of minimum degree ?

Parameter : .

Complexity : W[P]-complete (hardness: reduction from Weighted Monotone Circuit Satisfiability) [ ADF95 ]

Diameter Improvement for Planar Graphs

Instance : A planar graph .
Question : Can be augmented with additional edges in such a way that the resulting graph remains planar and has diameter at most ?

Parameter : .

Complexity : FPT [ DF95 ]

Remark : The diameter of a graph is the maximum distance between two vertices.
Application of the Robertson-Seymour Theorem..

Digraph Kernel

Instance : A directed graph .
Question : Does there exist a kernel in of cardinality at most ?

Parameter : .

Complexity : W[2]-hard [ GKLY05 ]

Remark : A kernel is a set of nodes such that is independent and for every vertex $x \in V \setminus S$ , there exists $y \in S$ such that $xy \in A$ .

Directed Feedback Vertex Set

Instance : A directed graph ; a positive integer .
Question : Is there, a subset $V' \subseteq V$ of cardinality at most such that contains at least one vertex from every directed cycle in ?

Parameter : .

Complexity : $O(8^kk! imes n^{O(1)})$ [ RO07 ] , $O(4^kk! imes n^{O(1)})$ [ CLL+08 ]

Directed Maximum Leaf Out-Branching

Instance : A directed graph .
Question : Is there a rooted spanning oriented tree in having at least leaves ?

Parameter : .

Complexity : $2^{O(k^3 \log k)} \cdot n^{O(1)}$ [ BD07 ] , $2^{O(k \log k)} \times n^{O(1)}$ [ BD08 ] ] , $O(3^72^k)$ [ DKGY10 ]

Directed Maximum Leaf Out-Tree

Instance : A directed graph .
Question : Is there a rooted oriented tree in having at least leaves ?

Parameter : .

Complexity : $2^{O(k \log^2 k)} \cdot n^{O(1)})$ [ AFG+07 ] , [ BD08 ] ] , $O(3^72^k)$ [ DKGY10 ]

Disjoint -subsets

Instance : A collection $\mathcal{F}$ of subsets of a set .
Question : Can we find disjoint subsets in $\mathcal{F}$ ?

Parameter : .

Complexity : FPT [ DF99 ]

Remark : Uses the hashing method.

Disjoint Paths

Instance : A graph , $s_1, \ldots, s_k$ start vertices and $t_1, \ldots, t_k$ terminal vertices.
Question : Do there exist $P_1, \ldots, P_k$ vertex disjoint paths such that stars at and ends at ?

Parameter : .

Complexity : FPT [ RS95b ]

Dominating Clique

Instance : A graph .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that the subgraph induced by is both a clique and a dominating set ?

Parameter : .

Complexity : W[2]-hard [ needed ]

Remark : Reduction from Dominating Set.

Dominating Rearrangement

Instance : A graph , a subset $S \subseteq V$ .
Question : Is there a dominating rearrangement $r : S \rightarrow N[S]$ , with $r(s) \in N[s]$ for each $s \in S$ , such that is a dominating set for ?

Parameter : $\vert S\vert$ .

Complexity : W[2]-hard [ Fer05a ]

Remark : Membership comes from Short Multi-Tape Nondeterministic Turing Machine Computation.
Hardness comes from Red-Blue Dominating Set.

Dominating Set

Instance : A graph .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that for all $u \in V \setminus V'$ there is a $v \in V'$ for which $(u,v) \in E$ ?

Parameter : .

Complexity : W[2]-hard [ DF99 ]

Dominating Set of Queens

Instance : A $n \times n$ chessboard .
Question : Is it possible to place queens on such that all squares are dominated ?

Parameter : .

Complexity : $O(15^{2K} + n)$ [ Fer05a ]

Dominating Set On Bounded Genus Graphs

Instance : A graph of bounded genus ( constant); a positive integer .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that for all $u \in V \setminus V'$ there is a $v \in V'$ for which $(u,v) \in E$ ?

Parameter : .

Complexity : , being the genus of the graph [ EFF04 ]

Dominating Threshold Set

Instance : A graph , a positive integer .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that for every $u \in V$ , N[u] contains at least elements of ?

Parameter : .

Complexity : W[2]-hard [ DF98 ]

Remark : Given a vertex , designs its closed neighborhood, i.e. all its neighbors plus . Hardness comes from Dominating Set..

Dual of Coloring

Instance : A graph .
Question : Is there a proper coloring of with at most n – k colors ?

Parameter : .

Complexity : FPT [ DF99 ]

Dual of Irredundant Set

Instance : A graph .
Question : Is there a subset $V' \subseteq V$ of size $\vert V\vert - k$ such that each vertex $u \in V'$ has a private neighbor, i.e., a vertex $u' \in N[u]$ such that $\forall v \in V' \setminus \{u\} u' \notin N[v]$ ?

Parameter : .

Complexity : FPT [ DF99 ]

Edge Dominating Set

Instance : A graph .
Question : Does there exist, a subset $E' \subseteq E$ of cardinality at most such that for all $e_1 \in E \setminus E'$ there is an $e_2 \in E'$ such that and are adjacent ?

Parameter : .

Complexity : [ Fer06b ]

Edge Induced Clique

Instance : A graph .
Question : Does there exist a subset of edges $E' \subseteq E$ of cardinality at least such that the subgraph induced by is a clique ?

Parameter : .

Complexity : W[1]-hard [ DF99 ]

Edge-Induced Clique Complement Cover

Instance : A graph .
Question : Does there exist $C \subseteq E$ of cardinality at most such that $G' = (V, E \setminus C)$ is a clique ?

Parameter : .

Complexity : FPT [ Fer05a ]

Exact Cheap Tour

Instance : A graph , a weight function $\omega : E \rightarrow \mathbb{Z}$ , a positive integer .
Question : Does there exist a tour through at least nodes of of cost exactly ?

Parameter : .

Complexity : W[1]-hard [ DF95a ]

Remark : Reduction from Subset Sum.

Exact Even Set

Instance : A bipartite graph .
Question : Is there a subset $V'_1 \subseteq V_1$ of cardinality at most such that each member of has an even number of neighbors in ?

Parameter : .

Complexity : W[1]-hard [ DFVW99 ]

Remark : Reduction from Perfect Code.

Exact Long Cycle

Instance : A graph .
Question : Does have a cycle of length exactly ?

Parameter : .

Complexity : FPT [ DF99 ]

Exact Odd Set

Face Cover

Instance : A planar graph ; a positive integer .
Question : Is there a set of at most faces that cover all vertices of ?

Parameter : .

Complexity : [ unreferenced ] , $O((2^{36sqrt(34)})^{sqrt(k)}n + n^2)$ [ ABF+02 ] ] , [ AL04 ]

Feedback Arc Set in Tournaments

Instance : A tournament ; a positive integer .
Question : Does there exist of cardinality at most whose removal result in acyclic directed graph ?

Parameter : n.

Complexity : [ ]

Remark : A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph.
See also : Feedback Arc Set in Weighted Tournaments, Feedback Arc Set in Weighted Tournaments (Integer) and Feedback Arc Set in Weighted Tournaments (Real).
---------------------------------------------------------------------------------------------------------
Parameter : .

Complexity : [ unreferenced ] , where is the exponent of the best matrix multiplication algorithm [ RS04 ]

Remark : A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph.
See also : Feedback Arc Set in Weighted Tournaments, Feedback Arc Set in Weighted Tournaments (Integer) and Feedback Arc Set in Weighted Tournaments (Real).

Feedback Arc Set in Weighted Tournaments

Instance : A tournament , a weight function $omega : E ightarrow mathbb{R}^+$ such that is at least ; a positive integer .
Question : Does there exist of cardinality at most whose removal result in acyclic directed graph ?

Parameter : .

Complexity : where is the exponent of the best matrix multiplication algorithm. [ RS04 ]

Remark : A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph.
See also : Feedback Arc Set in Tournaments, Feedback Arc Set in Weighted Tournaments (Integer) and Feedback Arc Set in Weighted Tournaments (Real).

Feedback Arc Set in Weighted Tournaments (Integer)

Instance : A tournament , a weight function ; a positive integer .
Question : Does there exist of cardinality at most whose removal result in acyclic directed graph ?

Parameter : .

Complexity : [ RS04 ]

Remark : A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph.
See also : Feedback Arc Set in Tournaments, Feedback Arc Set in Weighted Tournaments and Feedback Arc Set in Weighted Tournaments (Real).

Feedback Arc Set in Weighted Tournaments (Real)

Instance : A tournament , a weight function $omega : V ightarrow mathbb{R}^+$ such that is at least ; a positive integer .
Question : Does there exist of cardinality at most whose removal result in acyclic directed graph ?

Parameter : .

Complexity : where is the exponent of the best matrix multiplication algorithm. [ RS04 ]

Remark : A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph.
See also : Feedback Arc Set in Tournaments, Feedback Arc Set in Weighted Tournaments and Feedback Arc Set in Weighted Tournaments (Integer).

Feedback Vertex Set

Instance : A graph ; a positive integer .
Question : Is there, a subset $V' \subseteq V$ of cardinality at most such that contains at least one vertex from every directed cycle in ?

Parameter : .

Complexity : [ KPS04 ]

Fixed Alphabet Longest Common Subsequence

Instance : An alphabet $\Sigma$ of fixed size, a set of strings $s_1, \ldots, s_k$ over $\Sigma$ , a positive integer $\lambda$ .
Question : Is there a string $s \in \Sigma^*$ of length at least $\lambda$ that is a subsequence of each for $i = 1 \ldots k$ ?

Parameter : .

Complexity : W[1]-hard [ Pie03 ]

Remark : A string is a subsequence of a string if we can delete some characters in such that the remaining string is equal to . Reduction from Partitioned Clique..
---------------------------------------------------------------------------------------------------------
Parameter : , $\lambda$ .

Complexity : FPT [ needed ]

Fixed Alphabet Shortest Common Supersequence

Instance : An alphabet $\Sigma$ of fixed size, a set of strings $s_1, \ldots, s_k$ over $\Sigma$ , a positive integer $\lambda$ .
Question : Is there a string $s \in \Sigma^*$ of length at most $\lambda$ that is a supersequence of each for $i = 1 \ldots k$ ?

Parameter : .

Complexity : W[1]-hard [ Pie03 ]

Remark : A string is a subsequence of a string if we can delete some characters in such that the remaining string is equal to . Reduction from Partitioned Clique..
---------------------------------------------------------------------------------------------------------
Parameter : $\lambda$ .

Complexity : FPT [ needed ]

Generalized Vertex Cover

Instance : A graph , a subset of vertices $V' \subset eq V$ .
Question : Is there a vertex cover $C \subseteq V'$ of cardinality at most ?

Parameter : .

Complexity : FPT [ Fer05a ]

Remark : Equivalent to Vertex Cover .

Graph Genus

Instance : A graph .
Question : Does have genus ?

Parameter : .

Complexity : FPT [ FL88, RS04 ]

Remark : Cubic-time algorithm for fixed $k$ by the Robertson-Seymour theorem.

Graph Modification Problem

Instance : A graph , a class of graphs $\Pi$ that is hereditary and characterized by a finite set of forbidden induced subgraphs.
Question : Can we delete at most vertices, edges and add at most edges to obtain a graph that belongs to $\Pi$ ?

Parameter : , , .

Complexity : FPT [ Cai96 ]

Hitting Set

Instance : A collection $\mathcal{C}$ of subsets of a finite set .
Question : Is there a subset $S' \subseteq S$ of cardinality at most such that contains at least one element from each subset in $\mathcal{C}$ ?

Parameter : .

Complexity : W[2]-hard [ Nie06 ]

Independent Set

Instance : A graph .
Question : Does there exist a subset $V' \subseteq V$ of cardinality at most such that for all $u,v \in V'$ $(u,v) \notin E$ ?

Parameter : .

Complexity : W[1]-hard [ Nie06 ]

Interval Completion

Instance : A graph .
Question : Does there exist a subset $E' \subseteq \overline{E}$ of cardinality at most such that the addition of all non-edges of to results in an interval graph ?

Parameter : .

Complexity : [ HPTV07 ]

k-Based Tiling

Instance : A tiling systems with distinguished tiles.
Question : Is there a tiling of the $n \times n$ plane using the tiling system and starting with exactly distinguished tiles in a line ?

Parameter : .

Complexity : WP [ DF99 ]

König Vertex Deletion

Instance : A graph ; a positive integer .
Question : Does there exists $V' \subseteq V$ of cardinality at most such that the graph induced by is K ?

Parameter : .

Complexity : [ MRSS08 ]

Remark : See also : Above Guarantee Vertex Cover, Above Guarantee Vertex Cover for graphs with a perfect matching, König Vertex Deletion For Graphs With a Perfect Matching.

König Vertex Deletion For Graphs With a Perfect Matching

Instance : A graph with a perfect matching; a positive integer .
Question : Does there exists $V' \subseteq V$ of cardinality at most such that the graph induced by is K ?

Parameter : .

Complexity : [ MRS+07, RO08 ]

Remark : Equivalent to : Above Guarantee Vertex Cover, Above Guarantee Vertex Cover for graphs with a perfect matching, Almost 2-SAT.
See also : König Vertex Deletion.

Max-r-SAT-Above-Average

Instance : An exact r-CNF formula with m clauses
.
Question : Does there exist a truth assignment satisfying at least (2^r−1)m/2^r +k clauses ? ?

Parameter : k.

Complexity : 2^O(k²) [ AGKSY09 ] , 2^{O(k log k)} [ CGJ+10 ]

Maximum Agreement Subtree

Instance : A collection $mathcal{T} = {T_1, ldots, T_p}$ of trees (all rooted or all unrooted) with identical leaf set of cardinality ; a positive integer .
Question : Can we remove at most elements in so that there exists a Maximum Agreement Subtree of ( has its leaves in and is such that $forall T_i in mathcal{T}, T = T_i vert L(T)$ ) ?

Parameter : .

Complexity : [ BN06 ]

Maximum Cut

Instance : A graph .
Question : Is there a set of size at least such that is a bipartite graph ?

Parameter : .

Complexity : [ RS07 ]

Maximum Leaf Spanning Tree

Instance : A graph .
Question : Is there a spanning tree of with at least leaves ?

Parameter : .

Complexity : [ BBW03 ] , [ BZ08 ]

Minimum Fill-In

Instance : A graph ; a positive integer .
Question : Can we add at most edges to to obtain a chordal graph ?

Parameter : .

Complexity : $O(k^2nm + k^62^{4k})$ [ KST94 ] , , but requires space [ BHV08 ]

Minimum Inner Node Spanning Tree

Instance : A graph .
Question : Is there a spanning tree of with at most inner nodes ?

Parameter : .

Complexity : [ ]

Multicut in Trees

Instance : A tree , a set of requests (i.e. a set of pair of vertices); a positive integer .
Question : Does there exist a multicut of size at most (i.e. such that for each and lie in different connected components in ) ?

Parameter : .

Complexity : [ GN05 ]

Remark : The Multicut in Graphs problem is open.

Odd Cycle Transversal

Instance : A graph .
Question : Does there exist a subset $V' \subseteq V$ of cardinality at most whose removal makes bipartite (or equivalently hits every odd cycle of ) ?

Parameter : .

Complexity : [ RSV04 ] , $O(3^kkmn)$ [ LSS09 ]

Partial Vertex Cover

Instance : A graph .
Question : Does there exist a subset $C \subseteq V$ of cardinality at most such that covers at least edges ?

Parameter : .

Complexity : W[1]-hard [ Nie06 ]

Planar Capacitated Dominating Set

Instance : A graph , a capacity function $c : V \rightarrow \mathbb{N}$ .
Question : Is there a capacitated dominating set of with at most vertices (i.e. for all $u \in V \setminus S$ there is a $v \in S$ for which $(u,v) \in E$ ?

Parameter : .

Complexity : W[1]-hard [ BLP09 ]

Planar Clique

Instance : A planar graph .
Question : Does there exist a subset $V' \subseteq V$ of cardinality at most such that for all $u,v \in V'$ $(u,v) \in E$ ?

Parameter : .

Complexity : FPT [ needed ]

Planar Connected Dominating Set

Instance : A planar graph .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that the subgraph induced by is connected and, for all $u \in V \setminus V'$ there is a $v \in V'$ for which $(u,v) \in E$ ?

Parameter : .

Complexity : FPT [ Fer05a ]

Planar Dominating Set

Instance : A graph ; a positive integer .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that for all $u \in V \setminus V'$ there is a $v \in V'$ for which $(u,v) \in E$ ?

Parameter : .

Complexity : $O((3^{6sqrt{34}})^{sqrt{k}}n)$ [ ABF+02 ] , , [ AFF+05 ]

Planar Independent Dominating Set

Instance : A planar graph ; a positive integer .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that the subgraph induced by is an independent set and, for all $u \in V \setminus V'$ there is a $v \in V'$ for which $(u,v) \in E$ ?

Parameter : .

Complexity : [ AF06 ]

Remark : Equivalent to Planar Minimum Maximal Independent Set.

Planar Independent Set

Instance : A planar graph ; a positive integer .
Question : Does there exist an independent set $V' \subseteq V$ of cardinality at most (an independent set is a set of vertices pairwise non adjacents) ?

Parameter : .

Complexity : $O(2^{4 sqrt{6k}} n)$ [ AFN01 ]

Planar Minimum Maximal Independent Set

Instance : A planar graph ; a positive integer .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that the subgraph induced by is a maximal independent set (an independent set is a set whose vertices are pairwise non adjacents) ?

Parameter : .

Complexity : [ AF06 ]

Remark : Equivalent to Planar Independent Dominating Set.

Planar Red-Blue Dominating Set

Instance : A planar bipartite graph $G = (V_{red} cup V_{blue},E)$ ; a positive integer .
Question : Does there exist $V' \subseteq V_{red}$ of cardinality at most such that every vertex of $V_{blue}$ is adjacent to at least one vertex of ?

Parameter : .

Complexity : [ DF99 ]

Planar Vertex Cover

Instance : A planar graph .; positive integer .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that, for each edge $(u,v) \in E$ , at least one of and belongs to ?

Parameter : .

Complexity : $O(2^{4 sqrt{3k}} n)$ [ AFN01 ]

Power Dominating Set

Instance : A graph ; a positive integer .
Question : Does there exists $P \subseteq V$ of cardinality at most such that is power dominated by (a vertex $v \in V$ is power dominated if $v \in S$ , v is a neighbor of a vertex $u \in S$ or has a neighbor such that and all of its neighbors except are power dominated) ?

Parameter : .

Complexity : -hard [ GNR08 ]

Proper Interval Completion

Instance : A graph .
Question : Does there exist a subset $E' \subseteq \overline{E}$ of cardinality at most such that the addition of all non-edges of to results in a proper interval graph ?

Parameter : .

Complexity : $O(2^{4k}m)$ [ KST94 ]

Red-Blue Split Vertex Deletion

Instance : A red-blue graph ; a positive integer .
Question : Does there exist $V' \subseteq V$ of cardinality at most whose deletion makes red-blue split ?

Parameter : .

Complexity : [ MRSS08 ]

Set Cover

Instance : A base set $S = \{s_1, \ldots, s_n\}$ , a collection $\mathcal{C} = \{c_1, \ldots, c_m\}$ of subsets of such that $\cup_1$ $_\leqslant$ $_\leqslant$ .
Question : Is there a subset $\mathcal{C'}$ of $\mathcal{C}$ of cardinality at most which covers all elements in ?

Parameter : .

Complexity : W[2]-hard [ Nie06 ]

Set Packing

Instance : A collection $\mathcal{C}$ of subsets of a finite set .
Question : Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ which consists of at least mutually disjoint subsets ?

Parameter : .

Complexity : W[1]-hard [ Nie06 ]

Set Splitting

Instance : A collection of subsets of a finite set ; a positive integer .
Question : Is there a partition of into two disjoint subsets and such that there are at least sets in that have non-empty intersection with both and ) ?

Parameter : .

Complexity : [ DFR03 ] , $O^star(8^{k-1})$ [ DFRS04 ] ] , $O(2.6499^k \cdot n^{O(1)}$ [ LS05 ] ] , [ CL07 ] ] , [ LS09 ]

Short Turing Machine Acceptance

Instance : A nondeterministic Turing machine with its transition table, an input word for .
Question : Does on input have an accepting computation path of length at most ?

Parameter : .

Complexity : W[1]-hard [ Nie06 ]

Strongly Chordal Completion

Instance : A graph .
Question : Does there exist a subset $E' \subseteq \overline{E}$ of cardinality at most such that the addition of all non-edges of to results in a strongly chordal graph ?

Parameter : .

Complexity : $O(8^{2k}m \log n)$ [ KST94 ]

Vertex Cover

Instance : A graph ; positive integer .
Question : Is there a subset $V' \subseteq V$ of cardinality at most such that, for each edge $(u,v) \in E$ , at least one of and belongs to ?

Parameter : .

Complexity : $O(kn + max{(1.25542)^kk^2, (1.2906)^k2.5k)$ [ BFR98, DF99 ]

Weighted 3-Hitting Set

Instance : A collection of finite subsets of a set , of size bounded by , a weight function ; a positive integer .
Question : Does there exist $C' \subseteq V$ of weight at most such that $\forall c \in C$ we have $C' \cap c$ $\neq \varnothing$ ?

Parameter : .

Complexity : [ Fer06 ]

Remark : See also Weighted d-Hitting Set.

Weighted d-Hitting Set

Instance : A collection of finite subsets of a set , of size bounded by , a weight function ; a positive integer .
Question : Does there exist $C' \subseteq V$ of weight at most such that $\forall c \in C$ we have $C' \cap c$ $\neq \varnothing$ ?

Parameter : .

Complexity : , where is the largest positive root of the characteristic polynomial [ Fer06 ]

Weighted Fuzzy Cluster Editing

Instance : A graph , a weight function $\omega : V \rightarrow \mathbb{N}$ such that $\omega(uv) = 0$ if $uv \in F$ and $\omega(uv) > 0$ if $uv \notin F$ ; a positive integer .
Question : Is there a set $M \subseteq V \times V$ such that $G' = (V, E \triangle M)$ is a disjoint union of cliques and $\sum_{uv \in M} \omega(uv) \leqslant k$ ?

Parameter : .

Complexity : Open [ BFHMPR08 ]
---------------------------------------------------------------------------------------------------------
Parameter : , where is the size of a minimum vertex cover in the graph .

Complexity : [ ]

Online Compendium of Parameterized Problems <beta> (113)

Open Problems (soon)