cstheory 에서이 질문에 대답하면서 나는 (비공식적으로) 다음 정리를 즉석에서 증명했습니다.
정리 : 고정 경우 해밀턴 사이클 프로브는 길이 ≤ l 사이클을 포함하지 않는 최대 3 도의 평면 2 분자 무 방향 그래프로 제한 되더라도 NP- 완료 상태를 유지합니다 .
l≥3≤l
아직 어딘가에 나타나지 않은 것 같습니다.
그러나 “SGS에 알 수 없음”으로 표시된 graphclasses.org에서 많은 Hamiltonian주기 / 경로 문제를 해결할 수 있습니다 (예 : 이 항목 참조 ). 실제로 직접 추론는 해밀 토니안 사이클 경로 문제는 여전히 제한 경우 NP 완전하다는 것이다 그래프, 여기서 각각 H 저는 적어도 하나의주기를 포함한다.
Hi
종이 / 책이 어디에서 참조되었는지 알려주시겠습니까?
(그래서 graphclasses.org에서 사람들에게 연락 할 것입니다)
답변
결과는 Arkin, Mitchell 및 Polinshchuk 의 해밀턴 그래프의 두 가지 새로운 클래스에 나와 있습니다.
답변
1997 년 Hougardy, Emden-Weinert 및 Kreuter의 미공개 원고
는 Kristoffer Arnsfelt Hansen의 답변에서 지적한 결과보다 훨씬 강력한 다음 결과에 대한 간단한 증거를 제공했습니다.
0≤r<1/2
n
≥nr
원고에는 도미 네이션 세트, 최대 컷, VFS 등과 같은 다른 문제에 대한 유사한 결과도 포함되어 있습니다.