Portal de Periódicos da CAPES

On the Threshold of Intractability

2015; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-662-48350-3_35

1611-3349

Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov, Blair D. Sullivan,

Advanced Graph Theory Research

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.