Abstract
We consider a graph edge-editing problem, where the goal is to transform a given graph G into a disjoint union of two graphs from a pair of given graph classes, investigating what properties of the classes make the problem fixed-parameter tractable. We focus on the case when the first class is dense, i.e. every such graph G has minimum degree at least \(|V(G)| - \delta \) for a constant \(\delta \), and assume that the cost of editing to this class is fixed-parameter tractable parameterized by the cost. Under the assumptions that the second class either has bounded maximum degree, or is edge-monotone, can be defined in \(\text {MSO}_2\), and has bounded treewidth, we prove that the problem is fixed-parameter tractable parameterized by the cost. We also show that the problem is fixed-parameter tractable parameterized by degeneracy if the second class consists of independent sets and Subgraph Isomorphism is fixed-parameter tractable for the input graphs. On the other hand, we prove that parameterization by degeneracy is in general \(\text { W[1]}\)-hard even for editing to cliques and independent sets.
M. Kotrbčík and S. Ordyniak—Research funded by the Employment of Newly Graduated Doctors of Science for Scientific Excellence (CZ.1.07/2.3.00/30.0009) and the Austrian Science Fund (FWF, project P26696).
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
Similar content being viewed by others
Notes
- 1.
Note that in the case of r-regular graphs the smallest graph in the class has \(r+1\) vertices.
References
Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308–340 (1991)
Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1–3), 89–113 (2004)
Bodlaender, H., Heggernes, P., Lokshtanov, D.: Graph modification problems (Dagstuhl seminar 14071). Dagstuhl Rep. 4(2), 38–59 (2014)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Bova, S., Ganian, R., Szeider, S.: Model checking existential logic on partially ordered sets. In: CSL-LICS. ACM (2014)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inform. Process. Lett. 58(4), 171–176 (1996)
Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M., Schlotter, I.: Parameterized complexity of eulerian deletion problems. Algorithmica 68(1), 41–61 (2014)
Damaschke, P., Mogren, O.: Editing simple graphs. J. Graph Algorithms Appl. 18(4), 557–576 (2014)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol. 41. Springer, Heidelberg (2006)
Fomin, F., Golovach, P.: Long circuits and large euler subgraphs. SIAM J. Discrete Math. 28(2), 878–892 (2014)
Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: STOC. ACM (2014)
Hartung, S., Nichterlein, A., Niedermeier, R., Suchý, O.: A refined complexity analysis of degree anonymization in 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)
Hüffner, F., Komusiewicz, C., Nichterlein, A.: Editing graphs into few cliques: complexity, approximation, and kernelization schemes. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 410–421. Springer, Heidelberg (2015)
Kováč, I., Selečéniová, I., Steinová, M.: On the clique editing problem. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 469–480. Springer, Heidelberg (2014)
Mathieson, L., Szeider, S.: Editing graphs to satisfy degree constraints: a parameterized approach. J. Comput. Syst. 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)
Nastos, J., Gao, Y.: Familial groups in social networks. Soc. Netw. 35(3), 439–450 (2013)
Nešetřil, J., de Mendez, P.O.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics, vol. 28. Springer, Heidelberg (2012)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)
Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757–771 (2003)
Rivest, R.L., Vuillemin, J.: On recognizing graph properties from adjacency matrices. Theor. Comput. Sci. 3(3), 371–384 (1976)
Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: STOC, pp. 253–264. ACM (1978)
Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297–309 (1981)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kotrbčík, M., Královič, R., Ordyniak, S. (2016). Edge-Editing to a Dense and a Sparse Graph Class. In: Kranakis, E., Navarro, G., Chávez, E. (eds) LATIN 2016: Theoretical Informatics. LATIN 2016. Lecture Notes in Computer Science(), vol 9644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49529-2_42
Download citation
DOI: https://doi.org/10.1007/978-3-662-49529-2_42
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49528-5
Online ISBN: 978-3-662-49529-2
eBook Packages: Computer ScienceComputer Science (R0)