최소 정점의 변형은 다음과 같이 내 연구에서

Question

내가 정점 커버 문제의 변형에 직면 포함 크기가 k 인 이 포함되어 있습니다.

나는 모든 문헌을 검색 한 결과 비슷한 문제가 없습니다. 나는이 문제의 복잡성에 관심이있다. (나는 $ P^NP [long] $를 완성했다.

혹시 이런 버텍스 커버 문제를 보았습니까? 이 문제는 어떻게 부릅니까?

Answer 1

그래프 G와 정수 K이 주어지면 G가 크기가 K 인 정점 커버가 있는지를 결정하기 위해 최소 정점 커버 문제의 결정 문제입니다. 그리고 NP 완성입니다.

사실, 설명하신 문제는 그와 별 차이가 없습니다. 왜냐하면 꼭지점 v를 포함하고 있다면 v와 v를 끝점으로 가지는 모든 가장자리를 제거 할 수 있기 때문입니다. 다음으로해야 할 일은 왼쪽 서브 그래프를 k-1 정점으로 덮을 수 있는지 결정하는 것입니다.