Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
On the Threshold of Intractability
verfasst von : Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov, Blair D. Sullivan
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the computational complexity of the graph modification problems
and
, adding and deleting as few edges as possible to transform the input into a threshold (or chain) graph. In this article, we show that both problems are
-hard, resolving a conjecture by Natanzon, Shamir, and Sharan (2001). On the positive side, we show that these problems admit quadratic vertex kernels. Furthermore, we give a subexponential time parameterized algorithm solving
in
time, making it one of relatively few natural problems in this complexity class on general graphs. These results are of broader interest to the field of social network analysis, where recent work of Brandes (2014) posits that the minimum edit distance to a threshold graph gives a good measure of consistency for node centralities. Finally, we show that all our positive results extend to
, as well as the completion and deletion variants of both problems.