방향성 하이퍼그래프 스펙트럼 희소화

스펙트럼 그래프 희소화 기법을 하이퍼그래프에 확장하려는 시도가 최근 몇 년간 활발히 연구되어 왔습니다. 특히 무방향성 하이퍼그래프의 경우, 최적의 희소화 크기인 O*(n)을 달성하는 ε-스펙트럼 희소화기가 이미 증명되었습니다. 그러나 방향성 하이퍼그래프의 최적 희소화기 크기는 아직 알려지지 않은 상태였습니다. 본 연구는 가중치 방향성 하이퍼그래프에 대해 O*(n^2) 크기의 ε-스펙트럼 희소화기를 구성하는 최초의 알고리즘을 제안합니다. 이 알고리즘은 일반 그래프의 스패너 기반 희소화 기법에서 영감을 받은 반복 샘플링 접근 방식을 활용합니다. 우리의 결과는 ε^(-1) 및 log n 인자를 제외하면 최적입니다. 이는 방향성 그래프에서도 Ω(n^2)의 하한이 존재하기 때문입니다. 또한, 일반 방향성 하이퍼그래프에 대한 Ω(n^2/ε)의 비자명한 하한을 최초로 제시합니다. 이 반복 샘플링 기법의 유용성을 입증하기 위해, 무방향성 하이퍼그래프에 대해서도 유사한 알고리즘을 제시합니다. 이 알고리즘은 최상의 크기 경계를 달성하며, 병렬 구현이 가능하고, 내결함성을 갖도록 변환될 수 있습니다.