MDMarkus Sortland Dregi
Markus Sortland Dregi
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Markus Sortland Dregi has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Pål Grønås Drange
University of Bergen
3 shared publications - Daniel Lokshtanov
Department of Informatics University of Bergen Norway
2 shared publications - Blair D. Sullivan
University of Utah, Salt Lake City, Utah, USA
1 shared publication - Blair D. Sullivan
Department of Computer Science North Carolina State University Raleigh NC U.S.A
1 shared publication R. B. Sandeep
IIT Hyderabad
1 shared publication
Latest Publications
- 22 March 2016
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 362-375
Compressing Bounded Degree Graphs
- 22 March 2016
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 362-375
Compressing Bounded Degree Graphs
- Open Access
On the Threshold of Intractability
We study the computational complexity of the graph modification problems Threshold Editing and Chain Editing, 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 NP-complete, resolving a conjecture by Natanzon, Shamir, and Sharan (Discrete Applied Mathematics, 113(1):109--128, 2001). On the positive side, we show the problem admits a quadratic vertex kernel. Furthermore, we give a subexponential time parameterized algorithm solving Threshold Editing in $2^{O(\surd k \log k)} + \text{poly}(n)$ 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 (ISAAC, 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 the related problem of Chain Editing, as well as the completion and deletion variants of both problems.Open AccessOn the Threshold of Intractability
We study the computational complexity of the graph modification problems Threshold Editing and Chain Editing, 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 NP-complete, resolving a conjecture by Natanzon, Shamir, and Sharan (Discrete Applied Mathematics, 113(1):109--128, 2001). On the positive side, we show the problem admits a quadratic vertex kernel. Furthermore, we give a subexponential time parameterized algorithm solving Threshold Editing in $2^{O(\surd k \log k)} + \text{poly}(n)$ 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 (ISAAC, 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 the related problem of Chain Editing, as well as the completion and deletion variants of both problems.