γ-클러스터링 문제: 고전적 및 매개변수화된 복잡성

우리는 잘 알려진 클러스터 편집/삭제/완성 문제의 변형인 γ-클러스터링 문제를 소개하며, 이는 다음과 같이 정의됩니다: 그래프 G가 주어졌을 때, G에서 얼마나 많은 엣지를 편집, 삭제 또는 추가해야 γ-준클릭의 불리한 합집합을 만들 수 있는지. 우리는 여기에서 이러한 문제들의 완전한 복잡성 분류와 NP-완전 문제를 위한 수정 횟수로 매개변수화된 FPT 알고리즘을 제공합니다. 또한 최종 클러스터의 수가 고정된 상수인 이러한 문제의 변형을 연구하여 고전적 및 매개변수화된 복잡성과 관련하여 대부분 동일한 결과를 얻었습니다.