A Generalization of Join and an Algorithmic Recognition Problem

• Autorzy: Shalu M. A. , Yamini S. D.

Identyfikatory

DOI

10.3233/FI-2016-1347

• Języki publikacji: EN

Abstrakty

EN

We consider a new graph operation c²-join which generalizes join and co-join. We show that odd hole-free graphs (odd antihole-free graphs) are closed under c²-join and describe a polynomial time algorithm to recognize graphs that admit a c²-join. The time complexity of the (a) recognition problem, (b) maximum weight independent set (MWIS) problem, and (c) minimum coloring (MC) problem for odd hole-free graphs are still unknown. Let H be an odd hole-free graph that contains an odd antihole as an induced subgraph and G_H be the class of all graphs generated from the induced subgraphs of H by using c²-join recursively. Then G_H is odd hole-free, contains all P₄-free graphs, complement of all bipartite graphs, and some imperfect graphs. We show that the MWIS problem, maximum weight clique (MWC) problem, MC problem, and minimum clique cover (MCC) problem can be solved efficiently for G_H.

Słowa kluczowe

EN

c2-join; odd-hole free graphs; modular decomposition; maximum weight independent set problem; maximum weight clique problem; minimum coloring problem; minimum clique cover problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 1
• Strony: 81--91
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Shalu M. A.

• Indian Institute of Information Technology Design & Manufacturing (IIITD&M) Kancheepuram, Chennai, India

autor

Yamini S. D.

• Indian Institute of Information Technology Design & Manufacturing (IIITD&M) Kancheepuram, Chennai, India

Bibliografia

• [1] Corneil DG, Lerchs H, Burlingham LS. Complement reducible graphs. Discrete Applied Mathematics. 1981;3:163–174.
• [2] Chudnovsky M, Seymour P. The Structure of Claw-free Graphs. In: Proceedings of the British Combinatorial Conference. vol. 327. Cambridge University Press; 2005. p. 153–171.
• [3] Atay FM, Biyikoğlu T. Graph operations and synchronization of complex networks. Physical Review. 2005;72(016217). Available from: http://dx.doi.org/10.1103/PhysRevE.72.016217. doi:10.1103/PhysRevE.72.016217.
• [4] Brualdi RA. The Mutually Beneficial Relationship of Graphs and Matrices. In: CBMS Regional Conference Series in Mathematics, 12-16 July, 2010. vol. 115; 2011. ISBN:10:0-8218-5315-5. Available from: http://www.ams.org/publications/authors/books/postpub/cbms-115/\#sthash.yN340hUg.dpuf.
• [5] Chudnovsky M, Penev I, Scott A, Trotignon N. Substitution and _-boundedness. Journal of Combinatorial Theory. 2013;103(5):567–586.
• [6] Cvetković DM, Rowlinson P, Simić S. An Introduction to the Theory of Graph Spectra. vol. 75. Cambridge University Press, Cambridge-New York; 2010. Available from: http://dx.doi.org/10.1017/CBO9780511801518.
• [7] Kamsu-Foguem B, Chapurlat V. Requirements modelling and formal analysis using graph operations. International Journal of Production Research. 2007;44(17):3451–3470. doi:10.1080/00207540500499377.
• [8] Conforti M, Cornuéjols G, Liu X, Vušković K, Zambelli G. Odd hole recognition in graphs of bounded clique size. SIAM Journal of Discrete Mathematics. 2006;20(1):42–48. doi:10.1137/S089548010444540X.
• [9] Conforti M, Cornuéjols G, Vušković K. Decomposition of odd hole-free graphs by double star cutsets and 2-joins. Discrete Applied Mathematics. 2004;141(1-3):41–91. doi:10.1016/S0166-218X(03)00364-0.
• [10] Vušković K. Even hole-free graphs: A Survey. Applicable Analysis and Discrete Mathematics. 2010;4:219–240.
• [11] West DB. Introduction to Graph Theory. Prentice Hall, USA; 1996.
• [12] Bodlaender HL, Brandstädt A, Kratsch D, Rao M, Spinrad JP. On algorithms for fP5; gemg-free graphs. Theoretical Computer Science. 2005;349(1):2–21. doi:10.1016/j.tcs.2005.09.026.
• [13] Brandstädt A, Mahfud S. Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. Information Processing Letters. 2001;84(5):251–259. doi:10.1016/S0020-0190(02)00291-0.
• [14] Gallai T. Transitiv orientierbare Graphen. Acta Mathematica Academia Scientia Hungarica. 1967;18:25–66.
• [15] Giakoumakis V, Rusu I. Weighted parameters in fP5; P5g-free graphs. Discrete Applied Mathematics. 1997; 80:255–261.
• [16] Habib M, Maurer MC. On the X-join decomposition of undirected graphs. Discrete Applied Mathematics. 1979;1:201–207.
• [17] Hoáng CT, Reed B. Some classes of perfectly orderable graphs. Journal of Graph Theory. 1989;13(4):445–463. doi:10.1002/jgt.3190130407.
• [18] Möhring RH. Algorithmic aspect of the substitution decomposition in optimization over relations, set systems and boolean functions. Annals of Operations Research. 1985;4:195–225.
• [19] McConnell RM, Spinrad JP. Modular decomposition and transitive orientation. Discrete Mathematics. 1999; 201:189–241.
• [20] Brandstädt A, Le VB, Spinrad JP. Graph Classes - A Survey. SIAM, Society for Industrial and Applied Mathematics, Philadelphia; 1999. ISBN:978-0-898714-32-6.
• [21] Martin B, Paulusma D. The computational complexity of disconnected cut and 2K2 partition. In: 17th Int. Conf. on Principles and Practice of Constraint Programming. vol. 6876. LNCS; 2011. p. 561–575. doi:10.1007/978-3-642-30642-6.
• [22] Lozin VV, Milanic M. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. In: Proceeding SODA ’06 Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. vol. 6. SIAM Journal of Discrete Algorithms; 2008. p. 595–604. ISBN:0-89871-605-5.
• [23] Desler JF, Hakimi SL. On finding a maximum stable set of a graph. In: Proc. 4-th Annual Princeton Conference on Information Science and System. Princeton, NJ; 1970. p. 459–462.
• [24] Broersma HJ, Capponi A, Paulusma D. A new algorithm for on-line coloring bipartite graphs. SIAM Journal of Discrete Mathematics. 2008;22(1):72–91. Available from: http://dx.doi.org/10.1137/060668675. doi:10.1137/060668675.
• [25] Kierstead HA, Penrice SG, Trotter WT. On-line and rst-t coloring of graphs which do not induce P5. SIAM Journal of Discrete Mathematics. 1995;8(4):485–498. doi:10.1137/S0895480191218861.
• [26] Kierstead HA, Trotter WT. Colorful induced subgraphs. Discrete Mathematics. 1992;101(1-3):165–169.
• [27] Kisielewicz A, Szykula M. Rainbow induced subgraphs in proper vertex colorings. Fundamenta Informaticae. 2011;111(4):437–451. ISBN:0169-2968.
• [28] Simson D. Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams. Fundamenta Informaticae. 2013;123:447–490. doi:10.3233/FI-2013-820.
• [29] Simson D. A framework for Coxeter spectral analysis of edge-bipartite graphs, their rational morsifications and mesh geometries of root orbits. Fundamenta Informaticae. 2013;124:309–338. doi:10.3233/FI-2013-836.
• [30] Simson D. A Coxeter-Gram classification of simply laced edge-bipartite graphs. SIAM Journal of Discrete Mathematics. 2013;27(2):827–854. doi:10.1137/110843721.