일반 그래프에서 NP-hard로 알려진 여러 최적화 문제는 입력 그래프가 트리 일 때 다항식 시간 (일부 선형 시간에서도)으로 쉽게 해결할 수 있습니다. 예로는 최소 정점 커버, 최대 독립 세트, 하위 그래프 동형이 있습니다. 나무에 NP-hard로 남아있는 자연 최적화 문제를 언급하십시오.
답변
표준 참조 에서 나무로 제한되어 있어도 어려운 그래프 문제의 “자연”및 “잘 알려진”예제를 찾을 수 있습니다 . 예 :
(이것들은 트리 문제로 공식화되었지만 임의의 그래프로 일반화 할 수 있습니다. 그런 다음 위의 공식은 입력을 나무로 제한 할 때 특별한 경우로 얻습니다.)
트리에서 어려운 문제를 생성하기위한보다 일반적인 레시피 : supersequences , superstrings , substrings 등과 관련된 NP-hard 문제를 해결 한 다음 문자열을 레이블이 지정된 경로 그래프로 다시 해석하십시오. 그런 다음 일반 그래프 (하위 pose 그래프 부, 하위 문자열 ≈ 하위 그래프)와 유사한 질문을 제시하십시오. 그리고 우리는 나무와 길에서도 문제가 NP-hard라는 것을 알고 있습니다.
부분 집합 합계 문제를 줄임으로써 가중치 별에 어려운 문제도 많이 있습니다. 자연스러운 예는 다음과 같습니다.
- 두 여행객 TSP : 에지 가중 된 그래프 주어진 와 한계 W 우리가 폐쇄 산책 두 찾을 수, C 1 과 C 2 에서 G 각 거리가 최대 총 중량을 갖도록 W를 , 그리고 각 노드 G는 에 의해 덮여 적어도 하나의 산책?
지 여 씨1 씨2 지 여 지
다시 말하지만, 다양한 테마를 쉽게 찾을 수 있습니다.
답변
트리 정점이 개별 그리드 포인트에 배치되고 트리 에지가 그리드 에지에 배치 된 상태에서 트리를 2 차원 정수 그리드에 삽입 할 수 있는지 여부를 결정하는 것은 NP- 완료입니다.
예를 들어 Gregori, IPL 1989를 참조하십시오 .
답변
그룹 스타이너 문제는 좋은 예입니다. 이 문제에 대한 입력은 방향성 에지 가중 된 그래프 과 정점 k 개의 그룹 S 1 , S 2 , … , S K . 목표는 각 그룹에서 하나 이상의 정점이 포함 된 최소 가중치 트리를 찾는 것입니다. G가 별인 경우에도 Set Cover 문제가 특별한 경우임을 쉽게 알 수 있습니다. 따라서, 문제는 내부에 근접하기 어렵다 O ( 로그 N ) P = NP 않는 인자. 또한 Halperin과 Krauthgamer는이 문제가
G=(V,E)S1,S2,…,Sk
O(logn)
NP가 준 다항식 시간 알고리즘을 무작위 화하지 않는 한고정 ϵ > 0에 대한 O ( log 2 − ϵ n ) 계수(정확한 설명은 논문 참조). Garg, Konjevod 및 Ravi의 나무에는 O ( log 2 n ) 근사가 있습니다.
O(log2−ϵn)ϵ>0
O(log2n)
답변
트리에서 가장 어려운 문제 중 하나는 최소 대역폭 문제입니다. 그것은 인 또한 모발 길이 1 원형 애벌레 NP-어렵다 3. 최대치의 나무 -hard.
엔피참고 문헌 :
Michael R. Garey, Ronald L. Graham, David S.Johnson 및 Donald E. Knuth. 대역폭 최소화를위한 복잡성 결과. SIAM J. Appl. 수학, 34 (3) : 477-495, 1978.
버크 하르트 모니 엔. 모발 길이가 3 인 애벌레의 대역폭 최소화 문제는 NP- 완료입니다. SIAM J. Algebraic Discrete Methods, 7 (4) : 505-512, 1986.
W. Unger. 대역폭 문제의 근사치가 복잡합니다. FOCS에서, 페이지 82–91, 1998
답변
비가 중 에지 multicut 문제는 다음과 같다 : 무향 그래프 주어 의 정점의 쌍의 컬렉션 G 및 양의 정수 K 서브 세트가 있다면, 검색 S 최대의 유전율 의 가장자리 G 제거 단절을 모든 쌍 컬렉션의 정점.
GG
k
S
k
G
이 문제는 별 [ 1 ]의 NP-hard (및 MAX SNP-hard)입니다 .
[ 1 ] Garg, Vazirani 및 Yannakakis, 나무의 적분 흐름 및 다중 절단을위한 원시 이중 근사 알고리즘 , Algorithmica, 18 (1), pp 3-20, 1997.
답변
소방관 문제는 최근 상당한 주목을 받았으며, 최대 3 도의 나무에서 (어쩌면 놀랍게도) NP-hard입니다 . 실제로 다음과 같이 상당히 자연스러운 질문입니다.
불은 나무의 뿌리 (또는 더 일반적으로 그래프의 지정된 정점)에서 발생합니다. 모든 단계에서 소방관은 불타 지 않는 하나의 정점을 보호하고 그 후에 불은 보호되지 않은 모든 이웃에게 퍼집니다. 불 옆에 보호되지 않은 정점이 없으면 프로세스가 종료됩니다. 최대 개의 정점이 타는 소방관을위한 전략이 있습니까?
케이또는 변형, NP-hard : 잎이 타지 않는 소방관을위한 전략이 있습니까?
답변
나무에서는 어렵지 않다고 생각할 수있는 문제는 계산 기하학 의 동결 태그 문제입니다 . 간단히 말해서, 단일 깨어있는 ‘봇 (bot)’으로 시작하는 로봇의 깨우기 예약 문제입니다. 여기서 makepan은 비용 측정치입니다.
가중치 별 그래프에서 NP-hard 인 것으로 알려져 있습니다. 그러나 비행기에서 문제가 NP-hard인지 여부는 열려 있습니다. NP-hardness는 ‘tree-ness’가 아니라 ‘임의적 metric’-ness에서 나온다고 주장 할 수 있지만 스타 그래프는 제한된 측정 공간 만 제공합니다.