Maximální společný indukovaný podgraf - Maximum common induced subgraph

v teorie grafů a teoretická informatika, a maximální společný indukovaný podgraf dvou grafů G a H je graf, který je indukovaný podgraf oba G a H, a to má co nejvíce vrcholů.

Nalezení tohoto grafu je NP-tvrdé.V přidruženém rozhodovací problém, vstupem jsou dva grafy G a H a číslo k. Problém je rozhodnout, zda G a H mít společný indukovaný podgraf s alespoň k vrcholy. Tento problém je NP-kompletní.[1] Jedná se o zobecnění indukovaných problém izomorfismu podgrafu, který vzniká, když k se rovná počtu vrcholů v menším z G a H, takže celý tento graf musí vypadat jako indukovaný podgraf druhého grafu.

Na základě tvrdost aproximace výsledky pro maximální nezávislá sada problému, je také obtížné aproximovat maximální společný problém indukovaného podgrafu.[2] To znamená, že pokud P = NP, tady není žádný aproximační algoritmus že v polynomiální čas na -vertexové grafy, vždy najde řešení v rámci faktoru optimální, pro všechny .[3]

Jedním z možných řešení tohoto problému je vybudování modulární produktový graf z G a HV tomto grafu největší klika odpovídá maximálnímu společnému indukovanému podgrafu G a H. Proto, algoritmy pro nalezení maxima kliků lze použít k nalezení maximálního společného indukovaného podgrafu.[4]

Maximální běžné indukované podgrafové algoritmy mají dlouhou tradici cheminformatika a mapování farmakoforů.[5]

Viz také

Reference

  1. ^ Michael R. Garey a David S. Johnson (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W.H. Freemane, ISBN  0-7167-1045-5 A1.4: GT48, s. 202.
  2. ^ Kann, Viggo (1992), „O přibližnosti maximálního společného problému podgrafu“, STACS 92: 9. výroční sympozium o teoretických aspektech informatiky Cachan, Francie, 13. – 15. Února 1992, sborník, Přednášky v informatice, 577, Springer Science $ mathplus $ Business Media, str. 375–388, doi:10.1007/3-540-55210-3_198.
  3. ^ Zuckerman, D. (2006), „Lineární extraktory stupňů a nepřístupnost maximálního počtu klik a chromatického čísla“, Proc. 38. ACM Symp. Teorie výpočtu, str. 681–690, doi:10.1145/1132516.1132612, ISBN  1-59593-134-1, ECCC  TR05-100.
  4. ^ Barrow, H .; Burstall, R. (1976), „Subgraph isomorphism, matching relační struktury a maximální kliky“, Dopisy o zpracování informací, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1.
  5. ^ Raymond, John W .; Willett, Peter (2002), „Maximální běžné algoritmy izomorfismu podgrafu pro porovnávání chemických struktur“ (PDF), Journal of Computer-Aided Molecular Design, 16 (7): 521–533, doi:10.1023 / A: 1021271615909.