k-결함 결합(clique)은 전통적인 결합 정의를 완화하여 최대 k개의 누락된 간선을 허용하는 개념이다. 이러한 완화는 링크 예측, 커뮤니티 탐지, 소셜 네트워크 분석 등 다양한 실제 응용에서 중요하다. 최대 k-결함 결합을 열거하고 최대 k-결함 결합을 탐색하는 문제들이 광범위하게 연구되어 왔음에도, 기존 알고리즘은 작은 부분해들의 조합적 폭발과 비최적 탐색 공간과 같은 한계를 겪는다. 이러한 한계를 해결하기 위해, 우리는 먼저 결합을 생성한 뒤 누락된 간선을 추가하는 새로운 결합-우선 분기한정(branch-and-bound) 프레임워크를 제안한다. 또한, 입력 그래프에서 정점의 수가 n일 때 탐색 공간 크기가 O(3^{n/3} • n^k)임을 달성하는 새로운 피벗팅(pivoting) 기법을 도입한다. k가 상수일 때 최대 k-결함 결합의 최악의 경우 개수가 Ω(3^{n/3} • n^k)임을 증명함으로써, 우리의 알고리즘의 탐색 공간이 최악의 경우 최적인 것을 확립한다. 결함 결합의 지름-2(diameter-two) 성질을 활용하여, 탐색 공간 크기를 O(n • 3^{δ/3} • (δΔ)^k)로 추가로 감소시킨다. 여기서 δ는 퇴화도(degeneracy)이고 Δ는 입력 그래프의 최대 차수이다. 우리는 또한 제안한 분기한정을 기반으로 최대 k-결함 결합 탐색을 위한 효율적인 프레임워크를 제시하며, 탐색 공간을 줄이기 위한 실용적인 기법들도 함께 제안한다. 100만 개 이상의 간선을 포함하는 실제 세계 벤치마크 데이터셋에 대한 실험 결과, 최대 k-결함 결합 열거와 최대 k-결함 결합 탐색을 위한 각 제안 알고리즘이 처리 시간 측면에서 해당하는 최첨단 알고리즘을 최대 4자릿수(orders of magnitude)까지 능가함을 보여주었다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.