Next: MAXIMUM COMMON EMBEDDED SUB-TREE
Up: Iso- and Other Morphisms
Previous: MAXIMUM COMMON SUBGRAPH
  Index
- INSTANCE:
Graphs
and
.
- SOLUTION:
A common induced subgraph, i.e. subsets
and
such that
|V1'|=|V2'|, and the subgraph of
G1 induced by V1' and the subgraph of G2 induced by V2'
are isomorphic.
- MEASURE:
Cardinality of the common induced subgraph, i.e., |V1'|.
- Bad News:
Not approximable within
for some
[266].
- Comment:
Transformations to and from MAXIMUM CLIQUE.
Variation in which the degree of the graphs G1 and G2 is bounded by
the constant B is APX-hard and is approximable within B+1.
If the induced subgraph is restricted to be connected the problem is
NPO PB-complete and not approximable within
for any
[266].
Viggo Kann
1999-04-22