[논문] 이분 그래프 정점 색칠 로컬 탐색

출처: arXiv - 2606.09509v1

개요

지역 탐색은 최적화에 널리 사용되는 휴리스틱 방법이다. 본 논문에서는 이 방법을 정점 색칠 문제에 적용해 그 능력을 탐구한다. 정점 색칠 문제는 이론적 분석과 실용적 응용 모두에서 중요한 $NP$-난제이다. 정점 색칠 문제에 대한 지역 탐색 적용의 한계를 파악하기 위해, 구조가 다른 이분 그래프들의 지역 탐색 풍경을 분석한다. 전역 최적해만 존재하도록 보장하는 구조와 비전역 지역 최적해가 존재할 수 있는 구조를 구분하고, 일반 이분 그래프에서는 지역 탐색이 임의로 나쁜 결과를 반환할 수 있음을 보여준다. 또한, 지역 최적해를 찾을 수 있는 그래프에서 지역 탐색의 능력을 추가로 분석한다. 이를 위해 덜 자주 등장하는 색을 더 높은 확률로 제거하는 그레이박스 지역 탐색 변이 연산자를 도입하고, 이 연산자가 완전 이분 그래프에서 기대 실행 시간 $Θ(n \log n)$ 안에 최적 색칠을 찾는 것을 증명한다. 이는 블랙박스 랜덤 지역 탐색의 지수적 실행 시간에 비해 획기적인 개선이며, 그레이박스 변이 연산자가 지역 탐색의 실행 시간을 향상시킬 수 있음을 보여준다.

주요 기여

본 논문은 다음 분야의 연구를 제시한다:

• cs.NE

방법론

자세한 방법론은 전체 논문을 참고하시기 바란다.

실용적 함의

이 연구는 cs.NE 분야의 발전에 기여한다.

저자

• Johanna Gasse

논문 정보

• arXiv ID: 2606.09509v1
• 분류: cs.NE
• 발표일: 2026년 6월 8일
• PDF: PDF 다운로드