평면 서브큐빅 그래프의 다중 절단 난이도
가중치 에지 다중 절단(Edge Multiway Cut) 문제는 최대 차수 3의 평면 그래프에서 NP-완전임이 알려져 있습니다. 반면, 비가중치 버전은 최대 차수 11의 평면 그래프에서만 NP-완전성이 증명되었으며, 최대 차수 3 그래프에서의 복잡성은 20년 이상 미해결 과제로 남아 있었습니다. 본 연구는 비가중치 에지 다중 절단 문제가 최대 차수 3의 평면 그래프에서도 NP-완전임을 증명하여, 기존의 복잡성 간극을 해소했습니다. 가중치 에지 다중 절단이 최대 차수 2 이하 그래프에서 다항 시간 내에 해결 가능함을 고려할 때, 이는 중요한 진전입니다. 또한, 비가중치 노드 다중 절단(Node Multiway Cut) 문제(삭제 가능한 터미널 포함 및 미포함 모두) 역시 최대 차수 3의 평면 그래프에서 NP-완전임을 입증했습니다. 이러한 결과들을 기존 연구와 결합하여, 그래프 포함(graph containment)에 대한 두 가지 메타 분류를 적용할 수 있었습니다. 이를 통해 $\mathcal{H}$-위상 마이너 자유 그래프와, $\mathcal{H}$가 유한할 경우 $\mathcal{H}$-부분 그래프 자유 그래프에 대한 세 가지 문제의 완전한 이분법을 도출했습니다. 이는 기존에 $\mathcal{H}$-마이너 자유 그래프에 대해서만 가능했던 이분법을 확장한 것입니다.