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 COMMON INDUCED SUBGRAPH

• INSTANCE: Graphs $G_1=\left(V_1,E_1\right)$ and $G_2=\left(V_2,E_2\right)$.

• SOLUTION: A common induced subgraph, i.e. subsets ${V_1}'\subseteq V_1$ and ${V_2}'\subseteq V_2$ such that $\vert{V_1}'\vert=\vert{V_2}'\vert$, and the subgraph of $G_1$ induced by ${V_1}'$ and the subgraph of $G_2$ induced by ${V_2}'$ are isomorphic.

• MEASURE: Cardinality of the common induced subgraph, i.e., $\vert{V_1}'\vert$.

  
  

• Bad News: Not approximable within $\vert V\vert^{\varepsilon }$ for some $\varepsilon >0$ [281].

• Comment: Transformations to and from MAXIMUM CLIQUE. Variation in which the degree of the graphs $G_1$ and $G_2$ 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 $(\vert V_1\vert+\vert V_2\vert)^{1-\varepsilon }$ for any $\varepsilon >0$ [281].