집합 커버(set cover) 문제를 설명하면서, 신도시를 지을 때 학교를 어디에 배치하는지 정하는 문제를 예로 들었다.
집합 커버는 집합에 관한 문제이고 신도시 학교 배치는 그래프 문제인데, 왜 그래프 문제를 집합 문제로 바꿔서 푸는지 의아했다.
챗GPT에 보여주니 이것은 dominating set problem이고, set cover 문제와 본질적으로 같은 문제는 아니지만 상호 변환 가능하다고 한다.
위키백과에는 이렇게 나와 있다.
최소 지배 집합(minimum dominating set) 문제와 집합 커버 문제는 L-환원(L-reduction)하에서 동등하다. 한 문제의 인스턴스가 주어지면 다른 문제의 동등한 인스턴스를 구성할 수 있다.