우리는 문제도 결정 형태, 즉 ‘에서 NP-어려운 것을 증명’입력 그래프 이미는 chordless 홀수 사이클 완료? “”다음 문제에서 감소에 의해 :G

$G$

$G$

문제점 P : 그래프 주어 과 에지 통과하는 3보다 큰 길이의 홀수 사이클 chordless가 ?e ∈ E ( G ) eG

$G$

$G$e∈E(G)

$e\in E(G)$

$e\in E(G)$e

$e$

$e$

이 문제는 과 허용하여 섹션 3 이전의 단락에 언급 된 의견 중 하나에서 주어진 참조 에서“주어진 노드를 통과하는 코드없는 짝수 사이클 감지 ”를 줄임으로써 NP-hard라고 알려져 있습니다. :q = 2p=0

$p=0$

$p=0$q=2

$q=2$

$q=2$

제쳐두고, 과 은 임의의 고정 정수가되게하십시오. 다음과 같은 문제가 NP- 완전합니다. 그래프 에 길이 (mod ) 의 규정 된 정점 통한 유도주기가 포함되어 있습니까? …p ≥ 0 G u p qq>1

$q>1$

$q>1$p≥0

$p\ge 0$

$p\ge 0$G

$G$

$G$u

$u$

$u$p

$p$

$p$q

$q$

$q$

(Karp 감소가있을 수 있지만 Cook 하나를 허용하는 경우 다음 감소를 고려하십시오. 주어진 정도 d 노드를 적절한 나가는 모서리가있는 크기 d의 완전한 하위 그래프로 대체합니다. 그런 다음 완전한 그래프의 각 모서리에 대해 쿼리 할 수 ​​있습니다. 주어진 노드를 통과하는 코드없는 짝수주기는 전체 그래프의 모서리 중 하나를 통과하는 길이가 3보다 큰 코드없는 홀수주기에 해당합니다.)

이제 주요 감소를 위해. 문제 P의 사례가 주어지면 먼저 통과하는 삼각형이 있는지 감지합니다 . 그렇다면 로 삼각형을 형성하는 모든 노드를 삭제하십시오 . 와 삼각형을 형성 삭제 노드 것을 참고 통과하는 모든 chordless 이상한 사이클이 제거되지 않습니다 합니다 (chordless 속성으로).e e ee

$e$

$e$e

$e$

$e$e

$e$

$e$e

$e$

$e$

f

$f$

$f$e=(u,v)

$e=(u,v)$

$e=(u,v)$vf

$v_f$

$v_f$(vf,u)

$(v_f,u)$

$(v_f,u)$(vf,v)

$(v_f,v)$

$(v_f,v)$G′

$G^{\prime }$

$G'$

G

$G$

$G$e

$e$

$e$G′

$G^{\prime }$

$G'$

G′

$G^{\prime }$

$G'$e

$e$

$e$e

$e$

$e$G‘

$G\prime$

$G′$e

$e$

$e$G

$G$

$G$

e

$e$

$e$e

$e$

$e$e

$e$

$e$G′

$G^{\prime }$

$G'$G′

$G^{\prime }$

$G'$G′

$G^{\prime }$

$G'$G

$G$

$G$

---

답변