IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v291y2021i1p67-83.html
   My bibliography  Save this article

An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs

Author

Listed:
  • Şeker, Oylum
  • Ekim, Tınaz
  • Taşkın, Z. Caner

Abstract

We consider the selective graph coloring problem, which is a generalization of the classical graph coloring problem. Given a graph together with a partition of its vertex set into clusters, we want to choose exactly one vertex per cluster so that the number of colors needed to color the selected set of vertices is minimized. This problem is known to be NP-hard. In this study, we focus on an exact cutting plane algorithm for selective graph coloring in perfect graphs. Since there exists no suite of perfect graph instances to the best of our knowledge, we also propose an algorithm to randomly (but not uniformly) generate perfect graphs, and provide a large collection of instances available online. We conduct computational experiments to test our method on graphs with varying size and densities, and compare our results with a state-of-the-art algorithm from the literature and with solving an integer programming formulation of the problem by CPLEX. Our experiments demonstrate that our solution strategy significantly improves the solvability of the problem.

Suggested Citation

  • Şeker, Oylum & Ekim, Tınaz & Taşkın, Z. Caner, 2021. "An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs," European Journal of Operational Research, Elsevier, vol. 291(1), pages 67-83.
    • Handle: RePEc:eee:ejores:v:291:y:2021:i:1:p:67-83
    DOI: 10.1016/j.ejor.2020.09.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720308031
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.09.017?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wu, Qinghua & Hao, Jin-Kao, 2015. "A review on algorithms for maximum clique problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 693-709.
    2. Demange, Marc & Ekim, Tınaz & Ries, Bernard & Tanasescu, Cerasela, 2015. "On some applications of the selective graph coloring problem," European Journal of Operational Research, Elsevier, vol. 240(2), pages 307-314.
    3. Lilian Markenzon & Oswaldo Vernet & Luiz Araujo, 2008. "Two methods for the generation of chordal graphs," Annals of Operations Research, Springer, vol. 157(1), pages 47-60, January.
    4. Hanif D. Sherali & J. Cole Smith, 2001. "Improving Discrete Model Representations via Symmetry Considerations," Management Science, INFORMS, vol. 47(10), pages 1396-1407, October.
    5. Anuj Mehrotra & Michael A. Trick, 1996. "A Column Generation Approach for Graph Coloring," INFORMS Journal on Computing, INFORMS, vol. 8(4), pages 344-354, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tınaz Ekim & Mordechai Shalom & Oylum Şeker, 2021. "The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation," Journal of Combinatorial Optimization, Springer, vol. 41(3), pages 710-735, April.
    2. Ferrarini, Luca & Gualandi, Stefano, 2022. "Total Coloring and Total Matching: Polyhedra and Facets," European Journal of Operational Research, Elsevier, vol. 303(1), pages 129-142.
    3. Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
    4. Proll, Les, 2007. "ILP approaches to the blockmodel problem," European Journal of Operational Research, Elsevier, vol. 177(2), pages 840-850, March.
    5. Natalia Castro & María A. Garrido-Vizuete & Rafael Robles & María Trinidad Villar-Liñán, 2020. "Contrast in greyscales of graphs," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 874-898, April.
    6. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    7. Leo Liberti & James Ostrowski, 2014. "Stabilizer-based symmetry breaking constraints for mathematical programs," Journal of Global Optimization, Springer, vol. 60(2), pages 183-194, October.
    8. Laurent, Monique & Vargas, Luis Felipe, 2022. "Finite convergence of sum-of-squares hierarchies for the stability number of a graph," Other publications TiSEM 3998b864-7504-4cf4-bc1d-f, Tilburg University, School of Economics and Management.
    9. Hanif D. Sherali & Ki-Hwan Bae & Mohamed Haouari, 2013. "An Integrated Approach for Airline Flight Selection and Timing, Fleet Assignment, and Aircraft Routing," Transportation Science, INFORMS, vol. 47(4), pages 455-476, November.
    10. Xiao-Feng Xie & Jiming Liu, 2009. "Graph coloring by multiagent fusion search," Journal of Combinatorial Optimization, Springer, vol. 18(2), pages 99-123, August.
    11. Dollevoet, Twan & van Essen, J. Theresia & Glorie, Kristiaan M., 2018. "Solution methods for the tray optimization problem," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1070-1084.
    12. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    13. Ali, Agha Iqbal & O'Connor, Debra J., 2010. "The impact of distribution system characteristics on computational tractability," European Journal of Operational Research, Elsevier, vol. 200(2), pages 323-333, January.
    14. Chung, Yerim & Culus, Jean-François & Demange, Marc, 2015. "Inverse chromatic number problems in interval and permutation graphs," European Journal of Operational Research, Elsevier, vol. 243(3), pages 763-773.
    15. N. Cherfi & M. Hifi, 2010. "A column generation method for the multiple-choice multi-dimensional knapsack problem," Computational Optimization and Applications, Springer, vol. 46(1), pages 51-73, May.
    16. Rahma Lahyani & Leandro C. Coelho & Jacques Renaud, 2018. "Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 125-157, January.
    17. Zhou, Yi & Lin, Weibo & Hao, Jin-Kao & Xiao, Mingyu & Jin, Yan, 2022. "An effective branch-and-bound algorithm for the maximum s-bundle problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 27-39.
    18. Pop, Petrică C., 2020. "The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances," European Journal of Operational Research, Elsevier, vol. 283(1), pages 1-15.
    19. M Plumettaz & D Schindl & N Zufferey, 2010. "Ant Local Search and its efficient adaptation to graph colouring," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 819-826, May.
    20. Massimiliano Caramia & Paolo Dell'Olmo, 2001. "Iterative coloring extension of a maximum clique," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(6), pages 518-550, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:291:y:2021:i:1:p:67-83. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.