Florian Adriaens

CKR Partitions and Lower Bounds for Constrained Correlation Clustering and Variants

By using a simple textbook reduction from vertex cover, we show that the following three problems are all UG-hard to approximate with constant-factor smaller than two; minimum weakness strong triadic closure, cluster deletion and constrained correlation clustering. Additionally, we analyze the well-known low-diameter d...