
Instance : A directed acyclic graph
, a coloring
,
; positive integers
and
.
Question : Is there a topological sort
of
such that for all
, we
have that
and
(For
,
is the number of vertices
such that
,
and such that there
is an arc
with
) ?
Parameter :
,
.
Complexity : W[t]-hard for all
(reduction from a directed variant of Bandwidth) [ BGT98 ]
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
for
?
Parameter :
.
Complexity :
[ Fer05 ]
---------------------------------------------------------------------------------------------------------
Parameter :
.
Complexity :
[ MS85 ] ,
[ Kul99 ]
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 ]
Instance : A graph
; a positive integer
.
Question : Is there a vertex cover in
of size at most
, where
denotes the size of a maximum matching in
(a vertex cover is a subset
such that for all
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 ].
Instance : A graph
with a perfect matching; a positive integer
.
Question : Is there a vertex cover in
of size at most
, where
denotes the size of a perfect matching in
(a vertex cover is a subset
such that for all
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 ].
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.
Instance : A plane graph
(that is, an embedding of a planar
graph on the plane) with face set
; a function
;
a function
.
Question : Is there a set



with
and
such that for each 


, there is a face in
whose
boundary includes
?
Parameter : an integer
.
Complexity :
[ AL04 ]
Instance : An alphabet
, sequences
over
such that
has
elements and
, sets of arcs
,
.
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.
Instance : A graph
; a positive integer
.
Question : Is there a
linear layout
![]()
,
,
such that
implies
?
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 ]
Instance : A bipartite graph
.
Question : Is there a
-coloring of
such that there exists a set
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.
Instance : Bipartite graphs
and
.
Question : Is there an embedding of
into
?
Parameter :
.
Complexity : W[1]-hard [ DF99 ]
Instance : A bipartite graph
.
Question : Does
have
matchings ?
Parameter :
.
Complexity : FPT [ IRT78 ]
Instance : A graph
.
Question : Does there exist a subset
of
cardinality at most
whose removal makes
bipartite
(or equivalently hits every odd cycle of
) ?
Parameter :
.
Complexity :
[ GGH+06 ]
Instance : A graph
.
Question : Is there a set
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.
Instance : A graph
, an odd cycle transversal
.
Question : Is there an odd cycle transversal
with
?
Parameter :
.
Complexity :
[ RKV04 ]
Remark : An odd cycle transversal is a set of vertices whose removal makes the graph bipartite.
Instance : A graph
of maximum degree a fixed
constant
, a coloring of the vertices
.
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 ]
Instance : A
-bit positive integer
.
Question : Is there a prime factor
of
such that
?
Parameter :
.
Complexity : randomized FPT [ FK92 ]
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.
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
and arcs
,
, then
?
Parameter :
.
Complexity : W[P]-complete (hardness : reduction from Weighted Monotone Circuit Satisfiability) [ ADF95 ]
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 ]
Instance : A graph
.
Question : Does there exist a subset
of cardinality at most
such that for all
?
Parameter :
.
Complexity : W[1]-hard [ Nie06 ]
Instance : A graph
.
Question : Does there exist
with at most
vertices such that
induces a clique ?
Parameter :
.
Complexity :
[ Fer05a ]
Remark : Strongly related to Vertex Cover.
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 ]
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 :
[ ]
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 :
[ ]
Instance : A graph
; a positive integer
.
Question : Is there a subset
of cardinality at most
such that the graph
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 :
[ ]
Instance : A graph
; a positive integer
.
Question : Is there a subset
of cardinality at most
such that the graph
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.
Instance : A set of
strings
over a finite alphabet
, nonnegative integers
and
.
Question : Is there a string
of length
, and for
, a substring
of
of length
such that, for all
,
(here,
denotes the Hamming distance between
and
) ?
Parameter :
.
Complexity : W[1]-hard [ Nie06 ]
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.77k + n3) [ GGHN03 ] , O(1.53k + n3) [ GGHN04 ]
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 ].
Instance : A graph
; a positive integer
.
Question : Is there a subset
of cardinality at most
such that the graph induced by
is a disjoint union of cliques ?
Parameter :
.
Complexity :
using iterative compression [ HKMN08 ]
Instance : A graph
.
Question : Does there exist
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.
Instance : A graph
; an edge-coloring
,
,
; a positive integer
.
Question : Is there a
linear layout
,
,
such that
for each color
,
,
and for each 
-
, we have
?
Parameter :
.
Complexity : W[t]-hard for all
(reduction from Longest Common
Subsequence parameterized by
; the directed version of this problem, where
if
is also
hard for W[t], for all
; the variant in which we refer to the
size of
is also
W[t]-hard, for all
[ BFH94, BFH+00 ]
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 ]
Instance : A square grid graph
whose vertices are colored with
colors (
a fixed constant), and a colored graph
.
Question : Is there an homomorphism from
to
?
Parameter :
.
Complexity : W[1]-hard [ GSS01 ]
Instance : A graph
, a vertex coloring
.
Question : Does there exist a proper interval supergraph of
which respects
?
Parameter :
.
Complexity : W[1]-hard [ KS96 ]
Instance : A graph
; a positive integer
.
Question : Is there a subset
of cardinality at most
such that the subgraph induced by
is connected and, for all
there is a
for which
?
Parameter :
.
Complexity : W[2]-hard [ Fer03 ]
Instance : An
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.
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 :
[ CK03 ]
Instance : A bipartite graph
with
.
Question : Does there exist a dominating set
with
and
?
Parameter :
,
.
Complexity : W[2]-hard [ Fer05a ]
Instance : A bipartite graph
with
.
Question : Is there a vertex cover with at most
vertices
and at most
vertices in
?
Parameter :
,
.
Complexity :
[ HDS91 ] ,
[ FN01 ]
Instance : A graph
whose vertices have maximum degree
.
Question : Does
have an embedding in the plane with at most
edges crossing ?
Parameter :
.
Complexity :
[ DF99 ]
Remark : the complexity follows from the Robertson-Seymour theorem.
Instance : A graph
.
Question : Is there a one-to-one mapping
such that for every
,
?
Parameter :
.
Complexity :
[ Bod86 ]
Instance : A graph
; a positive integer
.
Question : Is there a set of
vertices
such that
has no
subgraph of minimum degree
?
Parameter :
.
Complexity : W[P]-complete (hardness: reduction from Weighted Monotone Circuit Satisfiability) [ ADF95 ]
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..
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
, there exists
such that
.
Instance : A directed graph
; a positive integer
.
Question : Is there, a subset
of cardinality at most
such that
contains at least one vertex from every directed cycle in
?
Parameter :
.
Complexity :
[ RO07 ] ,
[ CLL+08 ]
Instance : A directed graph
.
Question : Is there a rooted spanning oriented tree in
having at least
leaves ?
Parameter :
.
Complexity :
[ BD07 ] ,
[ BD08 ] ] ,
[ DKGY10 ]
Instance : A directed graph
.
Question : Is there a rooted oriented tree in
having at least
leaves ?
Parameter :
.
Complexity :
[ AFG+07 ] ,
[ DKGY10 ]
Instance : A collection
of
subsets of a set
.
Question : Can we find
disjoint subsets in
?
Parameter :
.
Complexity : FPT [ DF99 ]
Remark : Uses the hashing method.
Instance : A graph
,
start vertices and
terminal vertices.
Question : Do there exist
vertex disjoint paths such that
stars at
and ends at
?
Parameter :
.
Complexity : FPT [ RS95b ]
Instance : A graph
.
Question : Is there a subset
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.
Instance : A graph
, a subset
.
Question : Is there a dominating rearrangement
, with
for each
, such that
is a dominating set for
?
Parameter :
.
Complexity : W[2]-hard [ Fer05a ]
Remark : Membership comes from Short Multi-Tape Nondeterministic Turing Machine Computation.
Hardness comes from Red-Blue Dominating Set.
Instance : A graph
.
Question : Is there a subset
of cardinality at most
such that for all
there is a
for which
?
Parameter :
.
Complexity : W[2]-hard [ DF99 ]
Instance : A
chessboard
.
Question : Is it possible to place
queens on
such that all squares are dominated ?
Parameter :
.
Complexity :
[ Fer05a ]
Instance : A graph
of bounded genus
(
constant); a positive integer
.
Question : Is there a subset
of cardinality at most
such that for all
there is a
for which
?
Parameter :
.
Complexity :
,
being the genus of the graph [ EFF04 ]
Instance : A graph
, a positive integer
.
Question : Is there a subset
of cardinality
at most
such that for every
, 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..
Instance : A graph
.
Question : Is there a proper coloring of
with at most n k colors ?
Parameter :
.
Complexity : FPT [ DF99 ]
Instance : A graph
.
Question : Is there a subset
of size
such that each vertex
has a private neighbor, i.e., a vertex
such that
?
Parameter :
.
Complexity : FPT [ DF99 ]
Instance : A graph
Question : Does there exist, a subset
of cardinality at most
such that for all
there is an
such that
and
are adjacent ?
Parameter :
.
Complexity :
[ Fer06b ]
Instance : A graph
.
Question : Does there exist a subset of edges
of cardinality at least
such that the subgraph induced by
is a clique ?
Parameter :
.
Complexity : W[1]-hard [ DF99 ]
Instance : A graph
.
Question : Does there exist
of cardinality at most
such that
is a clique ?
Parameter :
.
Complexity : FPT [ Fer05a ]
Instance : A graph
, a weight function
, 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.
Instance : A bipartite graph
.
Question : Is there a subset
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.
Instance : A graph
.
Question : Does
have a cycle of length exactly
?
Parameter :
.
Complexity : FPT [ DF99 ]
Instance : A bipartite graph
.
Question : Is there a subset
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.
Instance : A planar graph
; a positive integer
.
Question : Is there a set of at most
faces that cover all vertices of
?
Parameter :
.
Complexity :
[ unreferenced ] ,
[ ABF+02 ] ] ,
[ AL04 ]
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).
Instance : A tournament
, a weight function
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).
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).
Instance : A tournament
, a weight function
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).
Instance : A graph
; a positive integer
.
Question : Is there, a subset
of cardinality at most
such that
contains at least one vertex from every directed cycle in
?
Parameter :
.
Complexity :
[ KPS04 ]
Instance : An alphabet
of fixed size, a set of
strings
over
, a positive integer
.
Question : Is there a string
of length at least
that is a subsequence of each
for
?
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 :
,
.
Complexity : FPT [ needed ]
Instance : An alphabet
of fixed size, a set of
strings
over
, a positive integer
.
Question : Is there a string
of length at most
that is a supersequence of each
for
?
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 :
.
Complexity : FPT [ needed ]
Instance : A graph
, a subset of vertices
.
Question : Is there a vertex cover
of cardinality at most
?
Parameter :
.
Complexity : FPT [ Fer05a ]
Remark : Equivalent to Vertex Cover .
Instance : A graph
.
Question : Does
have genus
?
Parameter :
.
Complexity : FPT [ FL88, RS04 ]
Remark : Cubic-time algorithm for fixed $k$ by the Robertson-Seymour theorem.
Instance : A graph
, a class of graphs
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
?
Parameter :
,
,
.
Complexity : FPT [ Cai96 ]
Instance : A collection
of subsets of a finite set
.
Question : Is there a subset
of cardinality at most
such that
contains at least one element from each subset in
?
Parameter :
.
Complexity : W[2]-hard [ Nie06 ]
Instance : A graph
.
Question : Does there exist a subset
of cardinality at most
such that for all
?
Parameter :
.
Complexity : W[1]-hard [ Nie06 ]
Instance : A graph
.
Question : Does there exist a subset
of cardinality at most
such that the addition of all non-edges of
to
results in an interval graph ?
Parameter :
.
Complexity :
[ HPTV07 ]
Instance : A tiling systems with distinguished tiles.
Question : Is there a tiling of the
plane using
the tiling system and starting with exactly
distinguished
tiles in a line ?
Parameter :
.
Complexity : WP [ DF99 ]
Instance : A graph
; a positive integer
.
Question : Does there exists
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.
Instance : A graph
with a perfect matching; a positive integer
.
Question : Does there exists
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.
Instance : An exact r-CNF formula with m clauses
.
Question : Does there exist a truth assignment satisfying at least (2r−1)m/2r +k clauses ? ?
Parameter : k.
Complexity : 2O(k2) [ AGKSY09 ] , 2O(k log k) [ CGJ+10 ]
Instance : A collection
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
) ?
Parameter :
.
Complexity :
[ BN06 ]
Instance : A graph
.
Question : Is there a set
of size at least
such that
is a bipartite graph ?
Parameter :
.
Complexity :
[ RS07 ]
Instance : A graph
.
Question : Is there a spanning tree of
with at least
leaves ?
Parameter :
.
Complexity :
[ BBW03 ] ,
[ BZ08 ]
Instance : A graph
; a positive integer
.
Question : Can we add at most
edges to
to obtain a chordal graph ?
Parameter :
.
Complexity :
[ KST94 ] ,
,
but requires
space [ BHV08 ]
Instance : A graph
.
Question : Is there a spanning tree of
with at most
inner nodes ?
Parameter :
.
Complexity : [ ]
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.
Instance : A graph
.
Question : Does there exist a subset
of
cardinality at most
whose removal makes
bipartite
(or equivalently hits every odd cycle of
) ?
Parameter :
.
Complexity :
[ RSV04 ] ,
[ LSS09 ]
Instance : A graph
.
Question : Does there exist a subset
of cardinality at most
such that
covers at least
edges ?
Parameter :
.
Complexity : W[1]-hard [ Nie06 ]
Instance : A graph
, a capacity function
.
Question : Is there a capacitated dominating set
of
with at most
vertices (i.e. for all
there
is a
for which
?
Parameter :
.
Complexity : W[1]-hard [ BLP09 ]
Instance : A planar graph
.
Question : Does there exist a subset
of cardinality at most
such that for all
?
Parameter :
.
Complexity : FPT [ needed ]
Instance : A planar graph
.
Question : Is there a subset
of cardinality at most
such that the subgraph induced by
is connected and, for all
there is a
for which
?
Parameter :
.
Complexity : FPT [ Fer05a ]
Instance : A graph
; a positive integer
.
Question : Is there a subset
of cardinality at most
such that for all
there is a
for which
?
Parameter :
.
Complexity :
[ ABF+02 ] ,
,
[ AFF+05 ]
Instance : A planar graph
; a positive integer
.
Question : Is there a subset
of cardinality at most
such that the subgraph induced by
is an independent set and, for all
there is a
for which
?
Parameter :
.
Complexity :
[ AF06 ]
Remark : Equivalent to Planar Minimum Maximal Independent Set.
Instance : A planar graph
; a positive integer
.
Question : Does there exist an independent set
of cardinality at most
(an independent set is a set of vertices pairwise non adjacents) ?
Parameter :
.
Complexity :
[ AFN01 ]
Instance : A planar graph
; a positive integer
.
Question : Is there a subset
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.
Instance : A planar bipartite graph
; a positive integer
.
Question : Does there exist
of cardinality at most
such that every vertex of
is adjacent to at least one vertex of
?
Parameter :
.
Complexity :
[ DF99 ]
Instance : A planar graph .
; positive integer
.
Question : Is there a subset
of cardinality at most
such that, for each edge
, at least one of
and
belongs to
?
Parameter :
.
Complexity :
[ AFN01 ]
Instance : A graph
; a positive integer
.
Question : Does there exists
of cardinality at most
such that
is power dominated by
(a vertex
is power dominated if
, v is a neighbor of a vertex
or
has a neighbor
such that
and all of its neighbors except
are power dominated) ?
Parameter :
.
Complexity :
-hard [ GNR08 ]
Instance : A graph
.
Question : Does there exist a subset
of cardinality at most
such that the addition of all non-edges of
to
results in a proper interval graph ?
Parameter :
.
Complexity :
[ KST94 ]
Instance : A red-blue graph
; a positive integer
.
Question : Does there exist
of cardinality at most
whose deletion makes
red-blue split ?
Parameter :
.
Complexity :
[ MRSS08 ]
Instance : A base set
, a collection
of subsets of
such that
.
Question : Is there a subset
of
of cardinality at most
which covers all elements in
?
Parameter :
.
Complexity : W[2]-hard [ Nie06 ]
Instance : A collection
of subsets of a finite set
.
Question : Is there a subcollection
which consists of at least
mutually disjoint subsets ?
Parameter :
.
Complexity : W[1]-hard [ Nie06 ]
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 ] ,
[ DFRS04 ] ] ,
[ LS05 ] ] ,
[ CL07 ] ] ,
[ LS09 ]
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 ]
Instance : A graph
.
Question : Does there exist a subset
of cardinality at most
such that the addition of all non-edges of
to
results in a strongly chordal graph ?
Parameter :
.
Complexity :
[ KST94 ]
Instance : A graph
; positive integer
.
Question : Is there a subset
of cardinality at most
such that, for each edge
, at least one of
and
belongs to
?
Parameter :
.
Complexity :
[ BFR98, DF99 ]
Instance : A collection
of finite subsets of a set
, of size bounded by
, a weight function
; a positive integer
.
Question : Does there exist
of weight at most
such that
we have
?
Parameter :
.
Complexity :
[ Fer06 ]
Remark : See also 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
of weight at most
such that
we have
?
Parameter :
.
Complexity :
, where
is the largest positive root of the characteristic polynomial
[ Fer06 ]
Instance : A graph
, a weight function
such that
if
and
if
; a positive integer
.
Question : Is there a set
such that
is a disjoint union of cliques and
?
Parameter :
.
Complexity : Open [ BFHMPR08 ]
---------------------------------------------------------------------------------------------------------
Parameter :
,
where
is the size of a minimum vertex cover in the graph
.
Complexity : [ ]