Next: MINIMUM VERTEX DELETION TO Up: Subgraphs and Supergraphs Previous: MAXIMUM INDEPENDENT SEQUENCE   Index

### MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P

• INSTANCE: Graph . 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.
• SOLUTION: A subset such that the subgraph induced by V' has the property P.
• MEASURE: Cardinality of the induced subgraph, i.e., .

• Good News: Approximable within [224].
• Bad News: Not approximable within 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 NPQP, if P is a non-trivial hereditary graph property (for example comparability, permutation, perfect, circular-arc, circle, line graph) [364].
• Comment: Approximable within if P is false for some clique or independent set [224], and approximable within where is the maximum degree [218]. All these good news are valid also for the vertex weighted version [224]. The same problem on directed graphs is not approximable within for any unless NPQP, if P is a non-trivial hereditary digraph property (for example acyclic, transitive, symmetric, antisymmetric, tournament, degree-constrained, line digraph) [364]. 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 [386]. Admits a PTAS for -free or -free graphs if P is hereditary [108].
• Garey and Johnson: GT21

Next: MINIMUM VERTEX DELETION TO Up: Subgraphs and Supergraphs Previous: MAXIMUM INDEPENDENT SEQUENCE   Index
Viggo Kann
2000-03-20