집합 덮개 문제

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

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

정수 계획법

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

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

조건:

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