집합 덮개 문제

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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