그래프 $H$가 클리크 그래프(clique graph)인 경우, $H$는 클리크들의 정점 분리 합집합(vertex-disjoint union of cliques)으로 표현될 수 있습니다. Abu-Khzam (2017)은 $(a,d)$-{클러스터 편집(Cluster Editing)} 문제를 소개하였는데, 이는 고정된 자연수 $a,d$에 대해 그래프 $G$와 정점 가중치 $a^:\ V(G)\rightarrow {0,1,\dots, a}$ 및 $d^:\ V(G)\rightarrow {0,1,\dots, d}$가 주어졌을 때, 모든 $v\in V(G)$에 대해 최대 $d^(v)$개의 변을 삭제하고 최대 $a^(v)$개의 변을 추가하여 $G$를 클러스터 그래프(cluster graph)로 만들 수 있는지를 결정하는 문제입니다. Komusiewicz와 Uhlmann (2012) 및 Abu-Khzam (2017)의 결과는 $(a,d)$-{클러스터 편집(Cluster Editing)} 문제의 복잡도(P 또는 NP-완전(NP-complete))를 모든 쌍 $(a,d)$에서 $(a=d=1)$을 제외하고 이분법적으로 구분하였습니다. Abu-Khzam (2017)은 $(1,1)$-{클러스터 편집(Cluster Editing)}이 P에 속한다고 추측하였습니다. 우리는 이 추측을 긍정적으로 해결하기 위해 (i) 최대 차수가 3인 $C_3$-자유($C_3$-free) 및 $C_4$-자유($C_4$-free) 그래프로 다섯 가지 다항 시간 축소법(reductions)을 제공하고, (ii) 최대 차수가 3인 $C_3$-자유 및 $C_4$-자유 그래프에서 $(1,1)$-{클러스터 편집(Cluster Editing)} 문제를 해결하기 위한 다항 시간 알고리즘(algorithm)을 설계하였습니다.