최근 연구에서 다음과 같은 흥미로운 문제가 발생했습니다.
인스턴스 : 그래프 .
G(V,E)솔루션 : 완성 된 그래프 가 모든 에지 가 코드리스 홀수 사이클에 포함되는 특성을 갖도록 에지 세트 의 수퍼 세트 로 정의 된 코드리스 홀수 사이클 완료 . E G ‘ ( V , E ‘ ) G ‘
E′E
G′(V,E′)
G′
측정 : 완료 크기, 즉.
|E′−E|지금까지, 우리는 이 문제의 수정 된 버전이 NP-complete 임을 증명할 수있었습니다 . 여기서 ” 모든 모서리 가 코드리스 홀수 사이클에 포함 되어야”하는 대신 “모든 모서리 가 포함되어 있습니다” 삼각형 (길이 3의 사이클) “. ( 최소 CHORDAL GRAPH COMPLETION 문제 와 동일하지 않습니다 .)
G′전자는 후자를 일반화 한 것으로 쉽게 보이지만,이를 증명하려는 나의 모든 노력은 실패했다. 누구든지 포인터 / 참조 등을 생각해 낼 수 있습니까?
답변
우리는 문제도 결정 형태, 즉 ‘에서 NP-어려운 것을 증명’입력 그래프 이미는 chordless 홀수 사이클 완료? “”다음 문제에서 감소에 의해 :
G문제점 P : 그래프 주어 과 에지 통과하는 3보다 큰 길이의 홀수 사이클 chordless가 ?e ∈ E ( G ) e
Ge∈E(G)
e
이 문제는 과 허용하여 섹션 3 이전의 단락에 언급 된 의견 중 하나에서 주어진 참조 에서“주어진 노드를 통과하는 코드없는 짝수 사이클 감지 ”를 줄임으로써 NP-hard라고 알려져 있습니다. :q = 2
p=0q=2
제쳐두고, 과 은 임의의 고정 정수가되게하십시오. 다음과 같은 문제가 NP- 완전합니다. 그래프 에 길이 (mod ) 의 규정 된 정점 통한 유도주기가 포함되어 있습니까? …p ≥ 0 G u p q
q>1p≥0
G
u
p
q
(Karp 감소가있을 수 있지만 Cook 하나를 허용하는 경우 다음 감소를 고려하십시오. 주어진 정도 d 노드를 적절한 나가는 모서리가있는 크기 d의 완전한 하위 그래프로 대체합니다. 그런 다음 완전한 그래프의 각 모서리에 대해 쿼리 할 수 있습니다. 주어진 노드를 통과하는 코드없는 짝수주기는 전체 그래프의 모서리 중 하나를 통과하는 길이가 3보다 큰 코드없는 홀수주기에 해당합니다.)
이제 주요 감소를 위해. 문제 P의 사례가 주어지면 먼저 통과하는 삼각형이 있는지 감지합니다 . 그렇다면 로 삼각형을 형성하는 모든 노드를 삭제하십시오 . 와 삼각형을 형성 삭제 노드 것을 참고 통과하는 모든 chordless 이상한 사이클이 제거되지 않습니다 합니다 (chordless 속성으로).e e e
ee
e
e
f
e=(u,v)
vf
(vf,u)
(vf,v)
G′
G
e
G′
G′
e
e
G′
e
G
e
e
e
G′
G′
G′
G