Problém isomorfismu vyvolaného podgrafu - Induced subgraph isomorphism problem - Wikipedia

v teorie složitosti a teorie grafů, indukovaný podgraf izomorfismus je NP-kompletní rozhodovací problém to zahrnuje nalezení daného grafu jako indukovaný podgraf většího grafu.

Problémové prohlášení

Formálně problém bere jako vstup dva grafy G1=(PROTI1, E1) a G2=(PROTI2, E2), kde je počet vrcholů v PROTI1 lze předpokládat, že je menší nebo roven počtu vrcholů v PROTI2. G1 je izomorfní na indukovaný podgraf G2 pokud existuje injekční funkce F který mapuje vrcholy G1 na vrcholy G2 takové, že pro všechny páry vrcholů X, y v PROTI1, hrana (X, y) je v E1 právě když hrana (F(X), F(y)) je v E2. Odpověď na rozhodovací problém je ano, pokud tato funkce F existuje, a ne jinak.

To se liší od problém izomorfismu podgrafu v tom absence hrany v G1 znamená, že odpovídající hrana v G2 musí také chybět. V izomorfismu podgrafu tyto „extra“ hrany G2 může být přítomen.

Výpočetní složitost

Složitost izomorfismu indukovaného podgrafu se odděluje vnější rovinné grafy z jejich zobecnění sériově paralelní grafy: lze to vyřešit v polynomiální čas pro 2 připojené outerplanar graphs, but is NP-complete for 2-connected series-parallel graphs.[1][2]

Speciální případy

Zvláštní případ nalezení dlouhého cesta jako indukovaný podgraf a hyperkrychle byl obzvláště dobře studován a nazývá se had-in-the-box problém.[3] The problém maximálně nezávislé množiny je také problém isomorfismu indukovaného podgrafu, ve kterém se člověk snaží najít velký nezávislá sada jako indukovaný podgraf většího grafu a maximální problém s klikou je problém isomorfismu indukovaného podgrafu, ve kterém se člověk snaží najít velký klikový graf jako indukovaný podgraf většího grafu.

Rozdíly s problémem izomorfismu podgrafu

Ačkoli se problém isomorfismu indukovaného podgrafu zdá jen mírně odlišný od problému izomorfismu podgrafu, „indukované“ omezení zavádí změny dostatečně velké, abychom mohli být svědky rozdílů z hlediska výpočetní složitosti.

Například problém izomorfismu podgrafu je NP-úplný na připojených správných intervalových grafech a na připojených bipartitních permutačních grafech,[4] ale indukovaný problém izomorfismu podgrafu lze vyřešit v polynomiálním čase na těchto dvou třídách.[5]

Navíc problém isomorfismu indukovaného podstromu (tj. Problém isomorfismu indukovaného podgrafu, kde G1 lze omezit na strom) lze vyřešit v polynomiálním čase na intervalových grafech, zatímco problém isomorfismu podstromu je NP-úplný na správných intervalových grafech.[6]

Reference

  1. ^ Sysło, Maciej M. (1982), „Problém izomorfismu podgrafu pro vnější rovinné grafy“, Teoretická informatika, 17 (1): 91–97, doi:10.1016/0304-3975(82)90133-5, PAN  0644795.
  2. ^ Johnson, David S. (1985), „Sloupec NP-úplnost: průběžný průvodce“, Journal of Algorithms, 6 (3): 434–451, doi:10.1016/0196-6774(85)90012-4, PAN  0800733.
  3. ^ Ramanujacharyulu, C .; Menon, V. V. (1964), „Poznámka k problému hada v krabici“, Publ. Inst. Statist. Univ. Paříž, 13: 131–135, PAN  0172736.
  4. ^ Kijima, Shuji; Otachi, Yota; Saitoh, Toshiki; Uno, Takeaki (1. listopadu 2012). "Podgraf izomorfismus ve třídách grafů". Diskrétní matematika. 312 (21): 3164–3173. doi:10.1016 / j.disc.2012.07.010.
  5. ^ Heggernes, Pinar; van 't Hof, Pim; Meister, Daniel; Villanger, Yngve. „Indukovaný izomorfismus podgrafu na správných intervalových a bipartitních permutačních grafech“ (PDF). předloženo.
  6. ^ Heggernes, Pinar; van 't Hof, Pim; Milanič, Martin (2013). "Indukované podstromy v intervalových grafech" (PDF). Sborník 24. mezinárodního semináře o kombinatorických algoritmech (IWOCA). Objevit se.