(1,1)-Édition de Cluster est Résoluble en Temps Polynomial

Un graphe $H$ est un graphe de clique si $H$ est une union disjointe de sommets de cliques. Abu-Khzam (2017) a introduit le problème de $(a,d)$-{Édition de Cluster}, où pour des nombres naturels fixés $a,d$, étant donné un graphe $G$ et des poids de sommets $a^ : V(G) \rightarrow {0,1,\dots, a}$ et $d^ : V(G) \rightarrow {0,1,\dots, d}$, il faut décider si $G$ peut être transformé en un graphe de cluster en supprimant au plus $d^(v)$ arêtes incidentes à chaque sommet $v \in V(G)$ et en ajoutant au plus $a^(v)$ arêtes incidentes à chaque sommet $v \in V(G)$. Les résultats de Komusiewicz et Uhlmann (2012) ainsi que ceux d'Abu-Khzam (2017) ont fourni une dichotomie de complexité (en P ou NP-complet) du problème $(a,d)$-{Édition de Cluster} pour toutes les paires $(a,d)$ sauf pour $(a=d=1)$. Abu-Khzam (2017) a conjecturé que le problème $(1,1)$-{Édition de Cluster} est dans P. Nous résolvons la conjecture d'Abu-Khzam par l'affirmative en (i) proposant une série de cinq réductions polynomiales vers des graphes sans cycle $C_3$ ni cycle $C_4$ dont le degré maximal est au plus 3, et (ii) en concevant un algorithme polynomial pour résoudre le problème $(1,1)$-{Édition de Cluster} sur ces graphes sans cycle $C_3$ ni cycle $C_4$ dont le degré maximal est au plus 3.