# On the Relation of Strong Triadic Closure and Cluster Deletion

arXiv: https://arxiv.org/abs/1803.00807 · HTML: https://mlsanity.com/paper/1803.00807/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2018.

## Built on by (most cited first, 4 of 4)

- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)
- [Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling](https://mlsanity.com/paper/2306.04884/) (2023)
- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)

## Abstract (arXiv)

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 P3 with two strong edges. In Cluster Deletion, we aim to destroy all induced P3s by a minimum number of edge deletions. We first show that Strong Triadic Closure admits a 4k-vertex kernel. Then, we study parameterization by ℓ:=|E|-k and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to ℓ. Finally, we give a dichotomy of the classical complexity of both problems on H-free graphs for all H of order four.