Abstract
We study the kernelizability of a class of NP-hard graph modification problems based on vertex degree properties. Our main positive results refer to NP-hard graph completion (that is, edge addition) cases while we show that there is no hope to achieve analogous results for the corresponding vertex or edge deletion versions. Our algorithms are based on a method that transforms graph completion problems into efficiently solvable number problems and exploits f-factor computations for translating the results back into the graph setting. Indeed, our core observation is that we encounter a win-win situation in the sense that either the number of edge additions is small (and thus faster to find) or the problem is polynomial-time solvable. This approach helps in answering an open question by Mathieson and Szeider [JCSS 2012].
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
Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 17–37. Springer, Heidelberg (2009)
Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: Proc. 50th FOCS, pp. 629–638. IEEE (2009)
Borri, A., Calamoneri, T., Petreschi, R.: Recognition of unigraphs through superposition of graphs. J. Graph Algorithms Appl. 15(3), 323–343 (2011)
Brandstädt, A., Le, V.B., Spinrad, J.P.: SIAM Monographs on Discrete Mathematics and Applications, vol. 3. SIAM (1999)
Chartrand, G., Lesniak, L., Mynhardt, C.M., Oellermann, O.R.: Degree uniform graphs. Ann. N. Y. Acad. Sci. 555(1), 122–132 (1989)
Chester, S., Kapron, B., Srivastava, G., Venkatesh, S.: Complexity of social network anonymization. Social Netw. Analys. Mining 3(2), 151–166 (2013)
Cornuéjols, G.: General factors of graphs. J. Combin. Theory Ser. B 45(2), 185–198 (1988)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer (2013)
Eppstein, D., Spiro, E.S.: The h-index of a graph and its application to dynamic subgraph statistics. J. Graph Algorithms Appl. 16(2), 543–567 (2012)
Fellows, M.R., Guo, J., Moser, H., Niedermeier, R.: A generalization of Nemhauser and Trotter’s local optimization theorem. J. Comput. System Sci. 77(6), 1141–1158 (2011)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman (1979)
Golovach, P.A.: Editing to a connected graph of given degrees. CoRR, abs/1308.1802 (2013)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007)
Hartung, S., Nichterlein, A., Niedermeier, R., Suchý, O.: A refined complexity analysis of degree anonymization on graphs. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 594–606. Springer, Heidelberg (2013)
Hartung, S., Hoffman, C., Nichterlein, A.: Improved upper and lower bound heuristics for degree anonymization in social networks. CoRR, abs/1402.6239 (2014)
Katerinis, P., Tsikopoulos, N.: Minimum degree and f-factors in graphs. New Zealand J. Math. 29(1), 33–40 (2000)
Komusiewicz, C., Niedermeier, R.: New races in parameterized algorithmics. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 19–30. Springer, Heidelberg (2012)
Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: ACM SIGMOD Conference, SIGMOD 2008, pp. 93–106. ACM (2008)
Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization - preprocessing with a guarantee. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol. 7370, pp. 129–161. Springer, Heidelberg (2012)
Lovász, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics, vol. 29. North-Holland (1986)
Mathieson, L., Szeider, S.: Editing graphs to satisfy degree constraints: A parameterized approach. J. Comput. System Sci. 78(1), 179–191 (2012)
Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discrete Algorithms 7(2), 181–190 (2009)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Froese, V., Nichterlein, A., Niedermeier, R. (2014). Win-Win Kernelization for Degree Sequence Completion Problems. In: Ravi, R., Gørtz, I.L. (eds) Algorithm Theory – SWAT 2014. SWAT 2014. Lecture Notes in Computer Science, vol 8503. Springer, Cham. https://doi.org/10.1007/978-3-319-08404-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-08404-6_17
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08403-9
Online ISBN: 978-3-319-08404-6
eBook Packages: Computer ScienceComputer Science (R0)