On the Relation of Strong Triadic Closure and Cluster Deletion

Abstract

We study the parameterized and classical complexity of two related problems on undirected graphs $G=(V,E)$. In Strong Triadic Closure we aim to label the edges in $E$ as strong and weak such that at most~$k$ edges are weak and $G$ contains no induced $P_3$ with two strong edges. In Cluster Deletion, we aim to destroy all induced $P_3$s by a minimum number of edge deletions. We first show that Strong Triadic Closure admits a $4k$-vertex kernel. Then, we study parameterization by $\ell :=|E|-k$ and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to $\ell$. Finally, we give a dichotomy of the classical complexity of both problems on $H$-free graphs for all $H$ of order four.

27 pages