단색 삼각형

Monochromatic triangle
완전한 그래프5 K의 모서리를 두 개의 삼각형이 없는 부분 집합으로 분할합니다.

그래프 이론과 이론 컴퓨터 과학에서, 단색 삼각형 문제는 그래프의 알고리즘 문제이며, 여기서 목표는 주어진 그래프의 가장자리를 삼각형이 없는 두 개의 하위 그래프로 나누는 것입니다.NP-완전하지만 제한 트리 폭의 그래프에서 추적 가능한 고정 매개 변수입니다.

문제문

단색 삼각형 문제는 노드 집합 V와 에지 집합 E를 가진 n-노드 무방향 그래프 G(V,E)를 입력으로 받아들인다.출력은 부울 값입니다.G의 엣지 세트E를 2개의 분리된 세트E1과 E2로 분할할 수 있는 경우 true이며, 2개의 서브그래프 G1(V, E1)과 G2(V, E2)가 모두 삼각형이 없는 그래프입니다.이 결정 문제는 NP-완전입니다.[1]

여러 색상으로 일반화

이 문제는 삼각형이 없는 모서리 색상으로 일반화될 수 있으며, 그래프의 모서리에 색을 할당하여 동일한 색상이 주어진 세 모서리를 모두 갖는 삼각형이 없도록 할 수 있습니다.단색 삼각형의 문제는 정확히 두 가지 색상을 사용할 수 있는 경우 삼각형이 없는 엣지 컬러링의 특수한 경우입니다.2색 삼각형의 프리 엣지 컬러가 존재하는 경우, 각 색상의 엣지는 단색 삼각형의 문제의 2세트 E1과 E2를 형성합니다.반대로 단색 삼각형 문제에 해답이 있으면 E1에 1색, E2에 2색을 사용하여 삼각형이 없는 엣지 컬러링을 얻을 수 있다.

램지의 정리와의 연관성

램지의 정리에 따르면, 유한한 수의 k색에 대해 n개 이상의 정점의 완전한 그래프가 k색상의 삼각형 프리 엣지 컬러링을 가지지 않는 수 n이 존재한다.k = 2의 경우 n의 해당 값은 6입니다.즉, 완전한 그래프6 K의 단색 삼각형 문제에 대한 답은 "아니오"입니다.

파라미터화된복잡도

단색 삼각형의 문제를 그래프의 단색 2차 논리(MSO)로2 표현하는 것은 매우 간단합니다.단색 삼각형의 문제는 에지의 분할이 2개의 서브셋에 존재함을 주장하고 에지가 모두 분할의 같은 쪽에 속하는 서로 인접한 3개의 정점이 존재하지 않도록 합니다.Courcelle의 정리에 따르면 단색 삼각형 문제는 유계수 폭의 그래프에서 다루기 쉬운 고정 매개 변수이다.보다 정확하게는 실행 시간이 입력 그래프의 정점 수에 빠르게 성장하지만 나무 [2]폭의 계산 가능한 함수를 곱한 문제를 해결하기 위한 알고리즘이 있다.

레퍼런스

  1. ^ A1.1: GT6, 페이지 191Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0-7167-1045-5.
  2. ^ 를 클릭합니다Arnborg, Stefan; Lagergren, Jens; Seese, Detlef (1988), "Problems easy for tree-decomposable graphs (extended abstract)", Automata, languages and programming (Tampere, 1988), Lecture Notes in Computer Science, vol. 317, Berlin: Springer, pp. 38–51, doi:10.1007/3-540-19488-6_105, MR 1023625.