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., |V'|.

- Good News: Approximable within [211].

- 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) [345].

- Comment: Approximable within if P is false for some clique or independent set [211], and approximable within where is the degree of the graph [205]. All these good news are valid also for the vertex weighted version [211]. 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) [345]. 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 [365]. Admits a PTAS for K3,3-free or K5-free graphs if P is hereditary [100].

- Garey and Johnson: GT21

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