HS (히팅 세트 문제)는 다음과 같이 정의됩니다. $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ S의 부분 집합 컬렉션 즉 $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
$ {S} “\ subset S $ 여기서 $ | {S} “| < k $ : $ S_i \ cap S “\ neq \ emptyset $, $ i = 1,2, …, m. $
HS가 Np-Complete임을 증명합니다.
힌트 : $ | S_i | = 2 $, HS는 Vertex Cover가되며 이미 NP-complete임을 알고 있습니다.
댓글
- 무엇을 시도 했습니까? 문제가 있습니까? ' 개념 이해를 도와 드리게되어 기쁩니다.하지만 연습 문제를 해결하는 것만으로는 달성 할 수 없습니다. 이 페이지 는 질문을 개선하는 데 도움이됩니다.
답변
3SAT가 Hitting으로 축소되었습니다. 문제를 설정합니다. $ m $ 절과 $ n $ 변수가있는 3SAT $ \ phi $가 주어지면
$$ S = \ {x_1, \ dots x_n, \ overline {x_1}, \ dots, \ overline {x_n} \} $$ $$ S_i = \ {y_1, y_2, y_3 \}, \ text {if} y_1, y_2, y_3 \ in S \ text {및} (y_1 \ lor y_2 \ lor y_3) \ text {는 절입니다.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {모두 variable} x. $$ $$ k = n $$
$ \ phi $가 만족 스럽다고 가정하면 $ n $ 변수에 대한 참값 할당이 있습니다. 따라서 $ x = true $이면 $ S “$에 $ x $를 추가하고, 그렇지 않으면 $ S”$에 $ \ overline {x} $을 추가합니다.
이제 HS 문제에 해결책이 있다고 가정합니다. S “$. 모든 변수 $ x $, $ S”\ cap S_x \ neq \ emptyset $, $ S “$에 $ x $ 또는 $ \ overline {x} $ 형식의 리터럴이 $ n $ 이상 있으므로 또한 $ x $ 및 $ \ overline {x} $은 $ S “$의 크기가 $ n $ 이하이기 때문에 $ S”$에 동시에 속할 수 없습니다. 또한 각 절 $ C_i $, $ S “\ cap S_i \ neq \ emptyset $ 그래서 각 절에 대해 $ y_i \ in S”\ cap S_i $를 선택하고 $ y_i = x $ 및 $이면 $ x = true $로 설정합니다. x = false $ if $ y_i = \ overline {x} $.
댓글
- 긍정적 및 부정적 인스턴스를 표시 할 수 있습니까?
Answer
히팅 세트가 NP에 있음을 쉽게 보여줍니다. 솔루션은 H 세트 만 표시하면됩니다. – H가 k 크기이고 각 세트 B1,…, Bm과 교차하는지 다항식 시간에 쉽게 확인할 수 있습니다.
정점 커버에서 축소합니다. 정점의 인스턴스를 고려합니다. 커버 문제 – 그래프 G = (V, E) 및 양의 정수 k. 다음과 같이 히트 세트 문제의 인스턴스에 매핑합니다. 집합 A는 꼭지점 V 집합입니다. 모든 모서리 e ∈ E에 대해 e의 두 끝점으로 구성된 집합 Se가 있습니다. 해당 요소가 hitting set 인스턴스에서 hitting 세트를 형성하는 경우 정점 세트 S가 G의 정점 커버임을 쉽게 알 수 있습니다.
Comments
- ComputerScience @ SE에 오신 것을 환영합니다. 특수 기호
∈의 흥미로운 사용-MathJax를 사용하는 것이 일반적이며, 예를 들어 적절한 구독 : $ B_1, \ dots, B_m $를 허용합니다. - Se의 크기가 2보다 큰가요? 작동합니까?
답변
히팅 세트 문제는 정의 된 세트 커버 문제와 동일합니다. 다음과 같이 :
INPUT : 유한 집합 S의 하위 집합 집합 C.
해결 방법 : S에 대한 집합 커버, 즉 $ C “\ subseteq C $와 같은 하위 집합 S의 모든 요소는 $ C “$의 적어도 하나의 구성원에 속합니다.
$ k $가 주어지면 $ \ vert C”\ vert \ leq k와 같은 세트 커버 $ C “$가 존재합니까? $?
이것은 숙제처럼 보이므로 Set Cover의 인스턴스가 주어진 경우 Hitting Set의 동등한 인스턴스로 변환 할 수있는 방법을 알아 보겠습니다.
그렇지 않으면 힌트를 따르고 싶다면 먼저 $ NP $에서 Hitting Set을 보여주고 다항식 시간에서 확인할 수있는 솔루션을 제공합니다.
그런 다음 주어진 그래프 $ G를 보여줍니다. = (V, E) $, $ k $ 크기의 정점 커버를 찾는 것은 $ k $ 크기의 히트 세트를 찾는 것과 같습니다. 즉, $ | E | = m $이면 동일한 세트 수로 히트 세트 인스턴스를 구축 할 수 있습니다.