집합 덮개 문제

틀:위키데이터 속성 추적 집합 덮개 문제(set cover)는 전산학과 복잡도 이론에서 다루는 오랜 문제로, 어떠한 전체집합과 그 집합의 부분집합들이 주어졌을 때, 부분집합들 중에서 가능한 한 적은 집합을 골라서 그 집합들의 합집합이 원래 전체집합이 되도록, 즉 그 집합들이 원래 전제집합을 '덮도록' 집합을 선택하는 문제이다. 이때 집합을 가능한 한 적게 골라내는 것이 목표이다. 이 문제의 결정 문제판은 리처드 카프가 NP-완전임을 증명했던 최초의 21문제 중 하나이다.

엄밀히 정의하면, 전체집합 $𝒰$와 $𝒰$의 부분집합으로 이루어진 집합족 $𝒮$가 있을 때, 어떠한 부분집합족 $𝒞\subseteq 𝒮$에 대해 $𝒞$에 속하는 집합들의 합집합이 $𝒰$가 된다면, $𝒞$를 덮개라고 정의한다. 이때 집합 덮개 문제의 결정 문제판은 $(𝒰,𝒮)$ 쌍과 정수 $k$가 입력될 때, $k$ 이하인 집합 덮개가 있는지 묻는 문제이다. 최적화 문제판의 경우 입력이 $(𝒰,𝒮)$ 쌍뿐이고, 집합 수가 가장 적은 덮개를 찾는 문제가 된다. 이 문제는 결정 문제의 경우 NP-완전, 최적화 문제의 경우 NP-난해에 속한다.

정수 계획법

집합 덮개 문제는 다음과 같은 정수 계획법으로 표현할 수 있다.

목표: $\sum _{S\in 𝒮}c(S)x_S$를 최소화. 즉, 선택된 부분집합의 개수를 최소화한다.

조건:

• 모든 $e\in 𝒰$에 대해서 $\sum _{S:e\in S}{x}_S\ge 1$: 적어도 한 개 이상의 부분집합에서는 원소 $e$를 한 번 이상 포함해야 한다.
• 모든 $S\in 𝒮$에 대해서 $x_S\in \{0,1\}$: 각 부분집합은 선택되었거나 선택되지 않았거나 둘 중 하나이다.