Abstract
Given an undirected graph G and a positive integer k, the NP-hard Sparse Split Graph Editing problem asks to transform G into a graph that consists of a clique plus isolated vertices by performing at most k edge insertions and deletions; similarly, the \(P_3\)-Bag Editing problem asks to transform G into a graph which is the union of two possibly overlapping cliques. We give a simple linear-time 3-approximation algorithm for Sparse Split Graph Editing, an improvement over a more involved known factor-3.525 approximation. Further, we show that \(P_3\)-Bag Editing is NP-complete. Finally, we present a kernelization scheme for both problems and additionally for the 2-Cluster Editing problem. This scheme produces for each fixed \(\varepsilon \) in polynomial time a kernel of order \(\varepsilon k\). This is, to the best of our knowledge, the first example of a kernelization scheme that converges to a known lower bound.
F. Hüffner—Supported by DFG project ALEPH (HU 2139/1).
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
Abu-Khzam, F.N., Fernau, H.: Kernels: annotated, proper and induced. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 264–275. Springer, Heidelberg (2006)
Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomassé, S.: Kernels for feedback arc set in tournaments. J. Comput. System Sci. 77(6), 1071–1078 (2011)
Borgatti, S.P., Everett, M.G.: Models of core/periphery structures. Soc. Networks 21(4), 375–395 (1999)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171–176 (1996)
Damaschke, P., Mogren, O.: Editing the simplest graphs. In: Pal, S.P., Sadakane, K. (eds.) WALCOM 2014. LNCS, vol. 8344, pp. 249–260. Springer, Heidelberg (2014)
Damaschke, P., Mogren, O.: Editing simple graphs. J. Graph Algorithms Appl. 18(4), 557–576 (2014). doi:10.7155/jgaa.00337
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer (2013)
Feder, T., Hell, P.: On realizations of point determining graphs, and obstructions to full homomorphisms. Discrete Math. 308(9), 1639–1652 (2008)
Fernau, H.: Parameterized algorithmics: A graph-theoretic approach. Wilhelm-Schickard-Institut für Informatik. Universität Tübingen, Habilitationsschrift (2005)
Fomin, F.V., Kratsch, S., Pilipczuk, M., Pilipczuk, M., Villanger, Y.: Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J. Comput. System Sci. 80(7), 1430–1447 (2014)
Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976)
Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. Theory of Computing 2(1), 249–266 (2006)
Guo, J.: A more effective linear kernelization for cluster editing. Theor. Comput. Sci. 410(8–10), 718–726 (2009)
Hammer, P.L., Simeone, B.: The splittance of a graph. Combinatorica 1(3), 275–284 (1981)
Hell, P.: Graph partitions with prescribed patterns. Eur. J. Combin. 35, 335–353 (2014)
Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discrete Appl. Math. 160(15), 2259–2270 (2012)
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)
Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. System Sci. 20(2), 219–230 (1980)
Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113, 109–128 (2001)
Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math. 144(1–2), 173–182 (2004)
Wu, B.Y., Chen, L.-H.: Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions. Algorithmica (2014, to appear). doi:10.1007/s00453-014-9874-8
Xie, W.: Obstructions to trigraph homomorphisms. Master’s thesis, School of Computing Science. Simon Fraser University, British Columbia, Canada (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Hüffner, F., Komusiewicz, C., Nichterlein, A. (2015). Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes. In: Dehne, F., Sack, JR., Stege, U. (eds) Algorithms and Data Structures. WADS 2015. Lecture Notes in Computer Science(), vol 9214. Springer, Cham. https://doi.org/10.1007/978-3-319-21840-3_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-21840-3_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21839-7
Online ISBN: 978-3-319-21840-3
eBook Packages: Computer ScienceComputer Science (R0)