그래프 색칠 문제(Graph Coloring Problem, GCP)는 컴퓨터 과학에서 가장 풀기 어려운 NP-난해(NP-hard) 문제 중 하나입니다. 이 문제는 주어진 그래프의 인접한 정점들이 서로 다른 색을 갖도록 최소한의 색상으로 칠하는 것을 목표로 합니다. DSATUR는 이 문제를 해결하기 위한 가장 빠른 휴리스틱(heuristic) 알고리즘 중 하나로 널리 알려져 있지만, 최신 알고리즘에 비해 더 많은 색상을 사용하는 경향이 있어 최적의 해를 찾기 어렵다는 단점이 있었습니다.
최근 Adam Nouira와 Lucas Isenmann 연구팀은 DSATUR의 이러한 한계를 극복하기 위한 새로운 접근 방식인 SSLD(Semidefinite Spectral Learning with DSATUR)를 제안했습니다. SSLD는 DSATUR 알고리즘을 시작하기 전에 그래프의 첫 번째 '좋은' 색상 클래스를 미리 결정하는 전처리 과정을 도입합니다. 이 첫 번째 색상 클래스는 러바즈 세타 수(Lovász theta number) 계산에 사용되는 것과 유사한 반정부 계획법(Semidefinite Programming, SDP)을 통해 얻어집니다. 연구팀은 DIMACS 인스턴스, 무작위 그래프(Erdős--Rényi, Watts-Strogatz, Barabási--Albert), 주파수 할당 및 작업 스케줄링 인스턴스 등 1,600개 이상의 다양한 벤치마크 인스턴스에서 SSLD를 평가했습니다. 그 결과 SSLD는 거의 모든 경우에서 DSATUR와 동등하거나 더 나은 성능을 보였으며, 특히 첫 번째 색상 클래스를 SDP 기반으로 선택하는 것이 중요함을 입증했습니다.
SSLD의 도입은 그래프 색칠 문제 해결에 있어 중요한 진전을 의미합니다. 비록 SSLD가 DSATUR보다 약 195배 느리다는 단점이 있지만, 이는 SDP 기반의 전처리 방식이 향후 알고리즘 개선의 유망한 방향임을 시사합니다. 그래프 색칠 문제는 자원 할당, 스케줄링, 통신 네트워크 주파수 할당 등 다양한 실제 문제에 적용될 수 있어, 이 분야의 성능 개선은 산업 전반에 긍정적인 영향을 미칠 수 있습니다. 이번 연구는 기존의 빠르지만 최적화되지 않았던 휴리스틱 알고리즘의 정확도를 높이는 새로운 가능성을 제시하며, 계산 비용과 정확도 사이의 균형점을 찾는 연구의 중요성을 다시 한번 강조합니다.