근선형 시간 내에 다항 대수적 크기의 가장 파괴적인 최소 정점 절단 찾기

우리는 그래프를 최소한 세 개의 연결된 컴포넌트로 분리하는 다항 대수적 크기의 모든 최소 정점 절단을 나열하기 위한 최초의 근선형 시간 랜덤 알고리즘과, 즉 연결된 컴포넌트의 수를 최대화하는 가장 파괴적인 절단을 찾기 위한 알고리즘을 제시합니다. 우리의 알고리즘은 20년 이상 개선되지 않은 Cheriyan과 Thurimella (STOC'96)의 두 문제에 대한 이차 시간 경계를 돌파합니다. 또한, 우리의 연구는 정점 연결성 보강 문제(Jordan '95)와 방향 그래프에서 짝수 길이 사이클 찾기 문제에 대한 근선형 시간 알고리즘을 위한 중요한 병목 현상을 제거합니다. 이 문제는 다른 많은 기본 문제와 동등한 것으로 나타났습니다(Vazirani와 Yannakakis '90, Robertson 외 '99). 일반적으로 최소한 세 개의 컴포넌트로 그래프를 분리하는 최소 정점 절단만 나열해야 하는 이유는 최소 정점 절단의 수가 지수적으로 많을 수 있기 때문입니다. 근선형 시간 알고리즘을 얻기 위해 우리는 Forster 외 (SODA'20)가 개발한 지역 유동 알고리즘의 기술을 확장하여 지역 규모에서 절단기를 나열합니다. 우리는 또한 정점 실패에 따라 쌍 정점 연결성 오라클에 대한 빠른 쿼리를 활용합니다(Long과 Saranurak FOCS'22, Kosinas ESA'23). 이는 정점 실패에 따라 연결성 오라클을 사용하여 정적 그래프 알고리즘의 속도를 높인 최초의 사례입니다.