Next: MAXIMUM COMMON INDUCED SUBGRAPH
Up: Iso- and Other Morphisms
Previous: Iso- and Other Morphisms
A common subgraph, i.e. subsets
such that the two subgraphs
Cardinality of the common subgraph, i.e., .
- Bad News:
Transformation from MAXIMUM CUT.
Not approximable with an absolute error guarantee of
Transformation to MAXIMUM CLIQUE with a quadratic vertex amplification
Variation in which the degree of the graphs
is bounded by
the constant B is not harder to approximate than the bounded degree induced
common subgraph problem and is approximable within B+1 .
- Garey and Johnson: GT49