Jung / Shah의 알고리즘 을 사용하는 작은 제외 그래프에서는 대략적인 착색 수가 쉬운 것으로 보입니다 . 일반 그래프에서는 어렵지만 작은 제외 된 그래프에서는 쉬운 문제의 다른 예는 무엇입니까?
업데이트 10/24
그로 헤의 결과에 따르면 경계-트리 폭 그래프에서 테스트하기 위해 FPT 인 공식은 작은 제외 된 그래프에서 테스트하기 위해 FPT입니다. 이제 문제는-그러한 공식의 만족스러운 할당을 계산하는 다루기 쉬움과 어떻게 관련이 있습니까?
위의 진술은 허위입니다. MSOL은 경계 트리 폭 그래프에서 FPT이지만, 약간 제외 된 평면 그래프에서는 3 색성이 NP- 완전합니다.
답변
알려진 가장 일반적인 결과는 Grohe입니다. 요약은 2010 년 7 월에 발표되었습니다.
- Martin Grohe, 미성년자 를 제외한 그래프 에서의 고정 소수점 정의 및 다항식 시간 , LICS 2010. ( PDF )
간단히 말해, 계산을 통해 고정 소수점 논리로 표현할 수있는 명령문은 하나 이상의 제외 된 마이너가있는 그래프 클래스에 다항식 시간 알고리즘이 있습니다. FP + C는 고정 소수점 연산자와 정의 가능한 정점 세트의 카디널리티를 제공하는 술어로 보강 된 1 차 논리입니다. 주요 아이디어는 마이너를 제외하면 클래스의 그래프가 고정 소수점 논리 (카운팅없이)에서 정의 할 수있는 트리 형 분해를 정렬 할 수 있다는 것입니다.
따라서 FP + C에서 정의 할 수 있지만 계산하기 어려운 속성을 고려하면 질문에 대한 많은 답변을 얻을 수 있습니다.
편집 : 이것이 실제로 귀하의 질문에 대답하는지 확실하지 않습니다. Grohe의 결과에 대한 포인터와 진술은 정확하지만 잘린 텍스트가 귀하의 질문과 관련이 있다고 생각하지 않습니다. (이 점을 지적 해준 Stephan Kreutzer에게 감사드립니다.) 명확하게 설명 할 가치가 있습니다. 일반적으로 어렵지만 사소한 배제 수업이나 결정 문제에서 쉬운 계산 문제를 원하십니까?
답변
마이너 클로즈드 그래프 패밀리의 흥미로운 특성은 퇴행성 을 경계한다는 것 입니다. 이는 경계 퇴행성 그래프에서 쉬운 모든 문제가 부-가족의 그래프에서 쉽다는 것을 의미합니다.
예를 들어, 그래프에 k 크기의 도수가 포함되어 있는지 확인하는 것은 일반적으로 어려운 문제이며 최상의 알고리즘은 입니다. 그러나, 퇴행성이 일정하다는 것을 알고 있다면, 선형 시간, 즉 O (n) 시간에서 k- 크릭을 찾을 수있다. clique 문제에 관한 Wikipedia의 기사에서도 이에 관한 정보를 제공합니다. (정확한 실행 시간은 .)이 알고리즘은 Chiba 및 Nishizeki의 것 입니다.O ( k 값 D ( G ) (K)의 N )
영형(엔케이) 영형(케이디(지)케이엔)다른 예는 MathOverflow에 대한 David Eppstein의 답변 에서 경계 퇴행이있는 그래프에 대한 비슷한 질문에 있습니다.
답변
보충으로, 마이너 제외 그래프에서 알고리즘의 또 다른 유용한 속성은 이러한 그래프에 작은 구분 기호 가 있다는 것 입니다. 보다 정확하게
미성년자를 제외하고 그래프에서 분리자를 찾는 선형 시간 알고리즘 , Bruce Reed와 David R. Wood, ACM Transactions on Algorithms, 2009,
영형(엔2/삼)
영형(엔삼/2+엠)
영형(엔1/2)
분리기는 동적 프로그래밍 기술에 적합하며, 많은 NP- 완료 문제에는 근사 비율이 좋은 빠른 알고리즘이있는 것으로 나타났습니다. 솔루션이 최적의 알고리즘 또는 PTAS의 일정한 요소 내에 있다고합니다.
평면 그래프 및 일반적으로 경계 속 그래프는 마이너 제외 그래프의 문제를 해결하려고 할 때 좋은 출발점입니다.
답변
제외 된 부차적 인 그래프에서 일반 그래프보다 다양한 NP-hard 문제를 상당히 더 잘 ( 또는 PTAS로) 추정 할 수있는 논문이 많이 있습니다. 예를 들어 :
O(1)알고리즘 그래프 사소한 이론 : Demaine, Hajiaghayi 및 Kawarabayashi의 분해, 근사 및 채색
이 논문은 Robertson & Seymour 정리에 의해 보장 된 배제 된 마이너 그래프에 대한 특정 (설명 적으로 복잡한) 분해의 알고리즘 버전을 제공하며, 이러한 개선 된 근사 결과를 제공합니다. 또한 그 안의 참조를 확인하십시오.