수정 된 간격 그래프 NP- 완료의 반음계 번호를 찾는 문제가 있습니까?

Question

몇 일 전 다차원 시간에이 문제 (색수)를 해결하고 간격의 각 꼭지점의 색상을 제공하는 탐욕적인 접근법이 있다는 것을 알고 있으므로 간격 그래프를 통해 자원 할당의 알려진 문제를 해결했습니다. 그래프 (일반 그래프에서 색수를 찾는 문제는 NP-Complete (Karp에 의한 3- 적합성 감소))입니다.

나는 간격 그래프가 아닌 그래프를 가지고 있지만 길이가 3보다 큰 단 하나의 코드없는주기를 가지고 있기 때문에 그럴 것이라고 생각했다. (그래프를 제거하면 그래프가 간격 그래프), 이런 종류의 그래프에서 반음계 수를 찾는 문제가 NP-Complete입니까?

Answer 1

손의 종류는, 간격 그래프 채색 알고리즘이 작동하지 않도록하는 단 가장자리가있는 경우 제거하십시오. 간격 그래프 알고리즘을 실행하십시오. 제거 된 모서리의 두 끝점에서 다른 색상을 사용하면 작업이 완료된 것입니다. 그렇지 않으면 알고리즘을 사용하는 색상의 수를 C라고합시다. 두 종점에 대해 모두 고정 색상을 선택하고 간격 그래프 알고리즘을 다시 시도하십시오. C 색상으로 성공하면 작업이 완료됩니다. 그렇지 않으면 C + 1 색상이 필요하므로 끝점 중 하나를 선택하고 고유 한 색상을 지정하십시오.

폴리시에서 제거 가능한 가장자리를 찾을 수 있다고 가정합니다.