클리크 너비로 파라미터화된 연결된 홀 순환 횡단을 위한 긴축 알고리즘

최근 Bojikian과 Kratsch가 2023년에 클리크 너비(cw)로 파라미터화된 연결성 문제를 해결하기 위한 새로운 접근법을 제시했으며, 이는 부분 솔루션의 작은 표현을 세는 것(모듈로 두)에 기반합니다. 이 기술을 사용하여 스테이너 트리 문제에 대한 긴축 경계를 얻어낸 이들은 Hegerfeld와 Kratsch가 2023 ESA에서 제기한 열린 질문에 답했습니다. 우리는 O^*(12^cw) 시간 내에 연결된 홀 순환 횡단 문제를 해결하기 위해 동일한 기법을 사용합니다. 이 문제의 2-색깔 가능성 요구 사항에서 연결성 요구 사항을 분리하여 부분 솔루션의 새로운 표현을 정의합니다. 더불어, 우리는 매개변수가 선형 클리크 너비로 설정된 경우에도 O^*((12-)^lcw) 실행 시간을 가진 알고리즘을 제외하는 SETH 기반 하한을 제공하여 우리의 결과가 긴축 임을 증명합니다. 이것은 같은 논문에서 Hegerfeld와 Kratsch가 제기한 두 번째 질문에 대한 답변입니다.