Abstract
A complete graph is the graph in which every two vertices are adjacent. For a graph \(G=(V,E)\), the complete width of G is the minimum k such that there exist k independent sets \(\mathtt {N}_i\subseteq V\), \(1\le i\le k\), such that the graph \(G'\) obtained from G by adding some new edges between certain vertices inside the sets \(\mathtt {N}_i\), \(1\le i\le k\), is a complete graph. The complete width problem is to compute the complete width of a given graph. In this paper we study the complete width problem. We show that the complete width problem is NP-hard on \(3K_2\)-free bipartite graphs and polynomially solvable on \(2K_2\)-free bipartite graphs and on \((2K_2,C_4)\)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on \(K_{2,2,2}\)-free co-bipartite graphs and polynomially solvable on \(K_{2,2}\)-free co-bipartite graphs and on \((2K_2, C_4)\)-free graphs. We also determine all graphs of small complete width \(k\le 3\).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Blázsik, Z., Hujter, M., Pluhár, A., Tuza, Z.: Graphs with no induced \(C_4\) and \(2K_2\). Discrete Mathematics 115, 51–55 (1993)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia (1999)
Chandler, D.B., Chang, M.-S., Kloks, T., Peng, S.-L.: Probe Graphs, (2009). http://www.cs.ccu.edu.tw/~hunglc/ProbeGraphs.pdf
Chang, M.-S., Hung, L.-J., Kloks, T., Peng, S.-L.: Block-graph width. Theoretical Computer Science 412, 2496–2502 (2011)
Chang, M.-S., Kloks, T., Liu, C.-H.: Edge-clique graphs of cocktail parties have unbounded rankwidth, (2012). arXiv:1205.2483 [cs.DM]
Chang, M.-S., Müller, H.: On the tree-degree of graphs. In: Brandstädt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 44–54. Springer, Heidelberg (2001)
Ma, S., Wallis, W.D., Wu, J.: Clique covering of chordal graphs. Utilitas Mathematica 36, 151–152 (1989)
Cygan, M., Pilipczuky, M., Pilipczuk, M.: Known algorithms for EDGE CLIQUE COVER are probably optimal. In: Proc. SODA, 1044–1053 (2013)
Foldes, S., Hammer, P.L.: Split graphs. Congressus Numerantium, No. XIX, 311–315 (1977)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Math., vol. 57, 2nd edn. Elsevier, Amsterdam (2004)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Data reduction and exact algorithms for clique cover. ACM Journal of Experimental Algorithmics 13 (2008). Article 2.2
Hammer, P.L., Peled, U.N., Sun, X.: Difference graphs. Discrete Applied Mathematics 28, 35–44 (1990)
Holyer, I.: The NP-completeness of some edge-partition problems. SIAM Journal on Computing 4, 713–717 (1981)
Hoover, D.N.: Complexity of graph covering problems for graphs of low degree. Journal of Combinatorial Mathematics and Combinatorial Computing 11, 187–208 (1992)
Hsu, W.-L., Tsai, K.-H.: Linear time algorithms on circular-arc graphs. Inf. Process. Lett. 40, 123–129 (1991)
Kou, L.T., Stockmeyer, L.J., Wong, C.K.: Covering edges by cliques with regard to keyword conflicts and intersection graphs. Comm. ACM 21, 135–139 (1978)
Le, V.B., Peng, S.-L.: Characterizing and recognizing probe block graphs. Theoretical Computer Science 568, 97–102 (2015)
Le, V.B., Peng, S.-L.: Good characterizations and linear time recognition for 2-probe block graphs. In: Proceedings of the International Computer Symposium, Taichung, Taiwan, December 12–14, 2014, pp. 22–31. IOS Press (2015). doi:10.3233/978-1-61499-484-8-22
Maffray, F., Preissmann, M.: Linear recognition of pseudo-split graphs. Discrete Applied Mathematics 52, 307–312 (1994)
Mahadev, N.V.R., Peled, U.N.: Threshold Graphs and Related Topics. Annals of discrete mathematics, vol. 56. Elsevier, Amsterdam (1995)
Müller, H.: On edge perfectness and classes of bipartite graphs. Discrete Math. 149, 159–187 (1996)
Orlin, J.: Contentment in graph theory: covering graphs with cliques. Indagationes Mathematicae 80, 406–424 (1977)
Pullman, N.J.: Clique covering of graphs IV. Algorithms. SIAM Journal on Computing 13, 57–75 (1984)
Raychaudhuri, A.: Intersection number and edge clique graphs of chordal and strongly chordal graphs. Congressus Numer. 67, 197–204 (1988)
Yannakakis, M.: Node-delection problems on bipartite graphs. SIAM Journal on Computing 10, 310–327 (1981)
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
Le, V.B., Peng, SL. (2015). On the Complete Width and Edge Clique Cover Problems. In: Xu, D., Du, D., Du, D. (eds) Computing and Combinatorics. COCOON 2015. Lecture Notes in Computer Science(), vol 9198. Springer, Cham. https://doi.org/10.1007/978-3-319-21398-9_42
Download citation
DOI: https://doi.org/10.1007/978-3-319-21398-9_42
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21397-2
Online ISBN: 978-3-319-21398-9
eBook Packages: Computer ScienceComputer Science (R0)