Abstract
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.
The research leading to these results has received funding from the Research Council of Norway, Bergen Research Foundation under the project Beating Hardness by Preprocessing and the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 267959.
Blair D. Sullivan supported in part by the Gordon & Betty Moore Foundation as a DDD Investigator and the DARPA GRAPHS program under SPAWAR Grant N66001-14-1-4063. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of DARPA, SSC Pacific, or the Moore Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brandes, U.: Social network algorithmics. ISAAC, Invited talk (2014)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes. A Survey. SIAM, Philadelphia (1999)
Burzyn, P., Bonomo, F., Durán, G.: NP-completeness results for edge modification problems. Discrete Applied Mathematics 154(13), 1824–1844 (2006)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters 58(4), 171–176 (1996)
Cao, Y., Marx, D.: Chordal editing is fixed-parameter tractable. In: STACS. LIPIcs, vol. 25, pp. 214–225 (2014)
Dehne, F., Langston, M., Luo, X., Pitre, S., Shaw, P., Zhang, Y.: The cluster editing problem: Implementations and experiments. In: IPEC (2006)
Drange, P.G., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Exploring subexponential parameterized complexity of completion problems. In: STACS (2014)
Drange, P.G., Pilipczuk, M.: A polynomial kernel for trivially perfect editing. In: ESA (to appear, 2015)
Drange, P.G., Dregi, M.S., Lokshtanov, D., Sullivan, B.D.: On the threshold of intractability. CoRR, abs/1505.00612 (2015)
Feder, T., Mannila, H., Terzi, E.: Approximating the minimum chain completion problem. Information Processing Letters 109(17), 980–985 (2009)
Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput. 42(6), 2197–2216 (2013)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Guo, J.: Problem kernels for NP-complete edge deletion problems: Split and related graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 915–926. Springer, Heidelberg (2007)
Liu, Y., Wang, J., Guo, J.: An overview of kernelization algorithms for graph modification problems. Tsinghua Science and Technology 19(4), 346–357 (2014)
Liu, Y., Wang, J., Guo, J., Chen, J.: Complexity and parameterized algorithms for cograph editing. TCS 461, 45–54 (2012)
Liu, Y., Wang, J., You, J., Chen, J., Cao, Y.: Edge deletion problems: Branching facilitated by modular decomposition. Theoretical Computer Science 573, 63–70 (2015)
Mahadev, N., Peled, U.: Threshold graphs and related topics, vol. 56. Elsevier (1995)
Mancini, F.: Graph modification problems related to graph classes. PhD thesis, University of Bergen (2008)
Nastos, J., Gao, Y.: Familial groups in social networks. Social Networks 35(3), 439–450 (2013)
Natanzon, A.: Complexity and approximation of some graph modification problems. PhD thesis, Tel Aviv University (1999)
Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Applied Mathematics 113(1), 109–128 (2001)
Schoch, D., Brandes, U.: Stars, neighborhood inclusion, and network centrality. In: SIAM Workshop on Network Science (2015)
Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Applied Mathematics 144(1), 173–182 (2004)
Sharan, R.: Graph modification problems and their applications to genomic research. PhD thesis, Tel-Aviv University (2002)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic and Discrete Methods 2(1), 77–79 (1981)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Drange, P.G., Dregi, M.S., Lokshtanov, D., Sullivan, B.D. (2015). On the Threshold of Intractability. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_35
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)