단위 원판 그래프에서의 사이클 패킹을 위한 ETH-타이트 알고리즘

이 논문에서는 다음과 같이 정의된 단위 원판 그래프에서 사이클 패킹 문제를 고려합니다. n개의 정점을 가진 단위 원판 그래프 G와 정수 k가 주어졌을 때, 존재한다면 G의 k 개 정점 분리 사이클 집합을 찾는 것이 목표입니다. 우리의 알고리즘은 시간 2^O (k) n^O (1)에서 실행됩니다. 이는 Fomin et al.이 제안한 2^O (k k) n^O (1) 시간 알고리즘을 개선한 것입니다. 또한, 우리의 알고리즘은 지수 시간 가설을 가정할 때 최적입니다.