Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P

• INSTANCE: Graph $G=\left(V,E\right)$. 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 $V' \subseteq V$ such that the subgraph induced by V' has the property P.
• MEASURE: Cardinality of the induced subgraph, i.e., $\vert V'\vert$.

  
  

• Good News: Approximable within $O(\vert V\vert/ \log \vert V\vert)$ [224].
• Bad News: Not approximable within $\vert V\vert^{\varepsilon }$ for some $\varepsilon >0$ 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 $2^{\log^{0.5-\varepsilon } \vert V\vert}$ for any $\varepsilon >0$ unless NP$\subset$QP, if P is a non-trivial hereditary graph property (for example comparability, permutation, perfect, circular-arc, circle, line graph) [364].
• Comment: Approximable within $O(\vert V\vert (\log\log \vert V\vert/\log \vert V\vert)^2)$ if P is false for some clique or independent set [224], and approximable within $\lceil (\Delta+1)/3 \rceil$ where $\Delta$ 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 $2^{\log^{0.5-\varepsilon } \vert V\vert}$ for any $\varepsilon >0$ unless NP$\subset$QP, 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 $K_{3,3}$-free or $K_{5}$-free graphs if P is hereditary [108].
• Garey and Johnson: GT21