유도 서브그래프 동형 문제

Induced subgraph isomorphism problem
1 ~ 4의 치수 n에 대한 박스 내 뱀(Ls) 및 코일(Lc)의 최대 길이

복잡도 이론과 그래프 이론에서, 유도 부분 그래프 동형은 더 큰 그래프의 유도 부분 그래프로서 주어진 그래프를 찾는 것을 포함하는 NP-완전 결정 문제이다.

문제문

형식적으로, 그 문제 입력 두 그래프 G1=(V, E1)과 G2=(V2, E2), vertices의 V1에 비해또는 vertices의 V2의 수보다 더 낮은 것으로 가정할 수 있는 만큼이 걸린다.만약이 G2의 vertices는은 vertices의 모든 쌍들을 위하여)G1의 vertices 모둔injective 기능 f, yV1,에 있는 G1G2의 유도 부분 그래프에 동형이다.에지(x, y)가 E인 경우에만2 에지(f(x), f(y))가 E에 있습니다1.결정 문제에 대한 답은 이 함수 f가 존재하는 경우 yes이고, 그렇지 않은 경우 no입니다.

이것은 G에 에지가1 없다는 것은 G에 대응하는2 에지도 반드시 없다는 것을 의미한다는 점에서 서브그래프 동형 문제와는 다르다.서브그래프 동형사상에서는 G에 이러한2 "추가" 에지가 존재할 수 있다.

계산의 복잡성

유도 하위 그래프 동형의 복잡성은 외부 평면 그래프를 일반화 계열-병렬 그래프에서 분리한다. 즉, 2연결 외부 평면 그래프에 대해서는 다항 시간 내에 해결할 수 있지만, 2연결 직렬-병렬 [1][2]그래프에 대해서는 NP-완전이다.

특수한 경우

하이퍼큐브의 유도 하위 그래프로 긴 경로를 찾는 특별한 사례는 특히 잘 연구되어 왔으며, snake-in-the-box 문제로 [3]불린다.최대 독립 집합 문제는 또한 큰 그래프의 유도 하위 그래프로서 큰 독립 집합을 찾는 유도 하위 그래프 동형 문제이고, 최대 집단 문제는 큰 그래프의 유도 하위 그래프로서 큰 집단 그래프를 찾는 유도 하위 그래프 동형 문제이다.

서브그래프 동형 문제와의 차이점

유도 서브그래프 동형 문제는 서브그래프 동형 문제와는 약간 다를 뿐이지만, "유도" 제한은 계산 복잡성의 관점에서 차이를 볼 수 있을 만큼 충분히 큰 변화를 초래한다.

예를 들어, 서브그래프 동형 문제는 연결된 적절한 간격 그래프와 연결된 초당 순열 [4]그래프에서 NP-완전이지만 유도 서브그래프 동형 문제는 이 두 클래스에서 [5]다항식 시간에 해결할 수 있다.

또한 유도 서브트리 동형 문제(즉, G가 트리로 제한되는 유도1 서브그래프 동형 문제)는 구간 그래프에서 다항 시간 내에 해결할 수 있는 반면, 서브트리 동형 문제는 적절한 구간 [6]그래프에서 NP-완전이다.

레퍼런스

  1. ^ 를 클릭합니다Sysło, Maciej M. (1982), "The subgraph isomorphism problem for outerplanar graphs", Theoretical Computer Science, 17 (1): 91–97, doi:10.1016/0304-3975(82)90133-5, MR 0644795.
  2. ^ 를 클릭합니다Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms, 6 (3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733.
  3. ^ 를 클릭합니다Ramanujacharyulu, C.; Menon, V. V. (1964), "A note on the snake-in-the-box problem", Publ. Inst. Statist. Univ. Paris, 13: 131–135, MR 0172736.
  4. ^ Kijima, Shuji; Otachi, Yota; Saitoh, Toshiki; Uno, Takeaki (1 November 2012). "Subgraph isomorphism in graph classes". Discrete Mathematics. 312 (21): 3164–3173. doi:10.1016/j.disc.2012.07.010.
  5. ^ Heggernes, Pinar; van 't Hof, Pim; Meister, Daniel; Villanger, Yngve. "Induced subgraph isomorphism on proper interval and bipartite permutation graphs" (PDF). submitted.
  6. ^ Heggernes, Pinar; van 't Hof, Pim; Milanič, Martin (2013). "Induced Subtrees in Interval Graphs" (PDF). Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA). To appear.