.
The property
P
must be hereditary, i.e., every subgraph of
G'
satisfies
P
whenever
G'
satisfies
P
, and non-trivial, i.e., it is satisfied
for infinitely many graphs and false for infinitely many graphs.
such that the subgraph induced by
V'
has the
property
P
.
if
P
is checkable in time
for some constant
c
[
152
].
for some
unless P=NP, if
P
is false for some clique or independent set (for
example planar, outerplanar, bipartite, complete bipartite, acyclic,
degree-constrained, chordal, interval).
Not approximable within
for any
unless NP
QP, if
P
is a non-trivial
hereditary graph property (for example comparability, permutation, perfect,
circular-arc, circle, line graph) [
263
].
if
P
is false
for some clique or independent set, and approximable within
(B+1)/3
where
B
is the degree of the graph
The positive results above are valid even for the vertex weighted problem
[
152
].
The same problem on directed graphs is not approximable within
for any
unless
NP
QP, if
P
is a non-trivial hereditary digraph property
(for example acyclic, transitive, symmetric, antisymmetric, tournament,
degree-constrained, line digraph)
[
263
].
Admits a PTAS for planar graphs if
P
is hereditary and determined
by the connected components, i.e.,
G'
satisfies
P
whenever every
connected component of
G'
satisfies
P
[
278
].
The good news is valid also for the vertex weighted version
[
152
].
Viggo Kann