집합 덮개 문제

집합 덮개 문제(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\}$: 각 부분집합은 선택되었거나 선택되지 않았거나 둘 중 하나이다.