NP 최적화입니까?

Question

n - 파티클 무향 그래프에서 각 부분 집합의 크기는 n입니다. 내 문제는 그래프에서 최소 n- 순을 찾는 것입니다. 나는 폴리에서 문제가 해결 될 수 있는지 알고 싶다. n 시간. 용어

더 상세 :

전체 K-partite 그래프 : 정점에 인접하는 그래프 만약 그들이 다른 partite 세트 (wikipedia)에 속하는 경우에만. 그래프에는 k 개의 부분 집합이 있습니다. 내 문제는 k = n.

클레크 : 그래프 G의 클록은 G의 완전한 하위 그래프입니다. 즉, S의 모든 두 정점이 G (wikipedia)의 모서리로 연결되도록 정점의 부분 집합 S입니다.

최소 무게 크릭 : 그래프의 모든 가장자리에는 무게가 있습니다. 파벌의 무게는 파벌의 모든 모서리의 무게의 합입니다. 목표는 최소한의 무게를 가진 파벌을 찾는 것입니다.

필요한 도둑의 크기는 완전한 n-partite 그래프에서 가장 큰 클록 크기 인 n이며 항상 도달 할 수 있습니다.

몇 시간 동안 검색 한 결과 정확한 문제를 해결할 연구가없는 것으로 보입니다. 어떤 제안?

Answer 1

예, CLIQUE의 감소를 통해 NP 하드입니다.

(G, k)를 CLIQUE의 인스턴스로 둡니다 (최소 k 이상의 카디널리티가 존재하는지 확인). G에있는 각 꼭지점의 k 개의 사본과 두 개의 꼭지점 v와 w 사이의 가장자리를 가진 k- 부분 그래프 H를 준비하십시오. 이들이 서로 다른 부분에 있고 G의 인접 꼭지점의 사본 인 경우에만 작성하십시오. G에 k- 클릭이 존재합니다 (무게가있는 경우 : 기존 가장자리의 무게를 1로 만들고 누락 된 무게의 무게를 0으로 유도하십시오.)

(분명히 이것은 문학이지만, 일요일이며, 나는보고 싶지 않다.)

Answer 2

이차 할당은 각 bipartite 세트와 각 bipartite 세트의 각 꼭지점을 가진 위치를 연관시킴으로써이 문제로 쉽게 줄일 수있다. 같은 설비에 관련 지을 수 있고있는 2 개의 정점 사이의 모서리의 무게는 무한대로 설정됩니다. 이차 할당은 NP 하드이기 때문에이 문제는 NP 하드입니다.