13 citations · 33 across the 14 of their papers we have counts for
Showing 2026Show all
2 papers · 1 filter
cs.DS2026
CKR Partitions and Lower Bounds for Constrained Correlation Clustering and Variants
Florian Adriaens
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 weak…
cs.DS2026
Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
Florian Adriaens, Nikolaj tatti
The Bad Triangle Transversal (BTT) problem asks for the smallest set of edges that need to be removed from a given signed graph, so that the resulting graph does not have a bad tri…