그래프 샌드위치 문제

Graph sandwich problem

그래프 이론과 컴퓨터 과학에서 그래프 샌드위치 문제는 특정한 그래프 계열에 속하는 그래프를 찾는 문제로서 다른 두 개의 그래프 사이에 "샌드위칭"되는데, 하나는 서브그래프여야 하고 다른 하나는 원하는 그래프의 수퍼그래프여야 한다.

그래프 샌드위치 문제는 주어진 그래프가 그래프 계열에 속하는지 여부를 테스트하는 문제를 일반화하며, 그래프 적용과 인식 문제의 자연적인 일반화 때문에 관심을 끌었다.[1]

문제명세서

더 정확히 말하면, 정점 집합 V, 필수 에지 집합1 E, 그리고 더 큰 에지 집합2 E를 고려할 때, 그래프 G = (V, E), E1 if E일2 경우 G = (V, E1), G2 = (V2, E) 쌍에1 대한 샌드위치 그래프라고 불린다.속성 π에 대한 그래프 샌드위치 문제는 다음과 같이 정의된다.[2][3]

속성 π의 그래프 샌드위치 문제:
인스턴스:정점 집합 V 및 에지 집합1 E ⊆ E2 ⊆ V × V.
질문:E1 ⊆ E ⊆ E와2 G가 속성 π을 만족하는 그래프 G = (V, E)가 있는가?

그래프 클래스(속성 π)에 대한 인식 문제는 E1 = E2, 즉 선택적 에지 집합이 비어 있는 특정 그래프 샌드위치 문제와 동일하다.

계산 복잡성

그래프 샌드위치 문제는 Ⅱ가 화음 그래프, 비교가능성 그래프, 순열 그래프, 화음 양분 그래프 또는 체인 그래프의 속성일 때 NP-완전하다.[2][4]5개의 꼭지점마다 최대 1개의 4Vertex 유도 경로를 포함하는 분할 그래프,[2][5] 분계점 그래프 [2][5]및 그래프의 경우 다항식으로 해결할 수 있다.[6]또한 4V 그래프 H의 각 H-프리 그래프 샌드위치 문제에 대한 복잡도 상태가 해결되었다.[7]

참조

  1. ^ Golumbic, Martin Charles; Trenk, Ann N. (2004), "Chapter 4. Interval probe graphs and sandwich problems", Tolerance Graphs, Cambridge, pp. 63–83.
  2. ^ a b c d Golumbic, Martin Charles; Kaplan, Haim; Shamir, Ron (1995), "Graph sandwich problems", J. Algorithms, 19: 449–473, doi:10.1006/jagm.1995.1047.
  3. ^ Golumbic, Martin Charles (2004), Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57 (2nd ed.), Elsevier, p. 279.
  4. ^ de Figueiredo, C. M. H.; Faria, L.; Klein, S.; Sritharan, R. (2007), "On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs", Theoretical Computer Science, 381 (1–3): 57–67, doi:10.1016/j.tcs.2007.04.007, MR 2347393.
  5. ^ a b Mahadev, N.V.R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, Annals of Discrete Mathematics, vol. 57, North-Holland, pp. 19–22.
  6. ^ Dantas, S.; Klein, S.; Mello, C.P.; Morgana, A. (2009), "The graph sandwich problem for P4-sparse graphs", Discrete Mathematics, 309: 3664–3673, doi:10.1016/j.disc.2008.01.014.
  7. ^ Dantas, Simone; de Figueiredo, Celina M.H.; Maffray, Frédéric; Teixeira, Rafael B. (2013), "The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem", Discrete Applied Mathematics: Available online 11 October 2013, doi:10.1016/j.dam.2013.09.004.

추가 읽기

  • Dantas, Simone; de Figueiredo, Celina M.H.; da Silva, Murilo V.G.; Teixeira, Rafael B. (2011), "On the forbidden induced subgraph sandwich problem", Discrete Applied Mathematics, 159: 1717–1725, doi:10.1016/j.dam.2010.11.010.