IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v76y2020i3d10.1007_s10898-018-0694-2.html
   My bibliography  Save this article

The maximum independent union of cliques problem: complexity and exact approaches

Author

Listed:
  • Zeynep Ertem

    (The University of Texas at Austin)

  • Eugene Lykhovyd

    (Texas A&M University)

  • Yiming Wang

    (Texas A&M University)

  • Sergiy Butenko

    (Texas A&M University)

Abstract

Given a simple graph, the maximum independent union of cliques problem is to find a maximum-cardinality subset of vertices such that each connected component of the corresponding induced subgraph is a complete graph. This recently introduced problem allows both cliques and independent sets as feasible solutions and is of significant theoretical and applied interest. This paper establishes the complexity of the problem on several classes of graphs (planar, claw-free, and bipartite graphs), and develops an integer programming formulation and an exact combinatorial branch-and-bound algorithm for solving it. Results of numerical experiments with numerous benchmark instances are also reported.

Suggested Citation

  • Zeynep Ertem & Eugene Lykhovyd & Yiming Wang & Sergiy Butenko, 2020. "The maximum independent union of cliques problem: complexity and exact approaches," Journal of Global Optimization, Springer, vol. 76(3), pages 545-562, March.
    • Handle: RePEc:spr:jglopt:v:76:y:2020:i:3:d:10.1007_s10898-018-0694-2
    DOI: 10.1007/s10898-018-0694-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-018-0694-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-018-0694-2?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. Svyatoslav Trukhanov & Chitra Balasubramaniam & Balabhaskar Balasundaram & Sergiy Butenko, 2013. "Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations," Computational Optimization and Applications, Springer, vol. 56(1), pages 113-130, September.
    2. Egon Balas & Vašek Chvátal & Jaroslav Nešetřil, 1987. "On the Maximum Weight Clique Problem," Mathematics of Operations Research, INFORMS, vol. 12(3), pages 522-535, August.
    3. Lucas Bastos & Luiz Satoru Ochi & Fábio Protti & Anand Subramanian & Ivan César Martins & Rian Gabriel S. Pinheiro, 2016. "Efficient algorithms for cluster editing," Journal of Combinatorial Optimization, Springer, vol. 31(1), pages 347-371, January.
    4. Buchanan, Austin & Sung, Je Sang & Boginski, Vladimir & Butenko, Sergiy, 2014. "On connected dominating sets of restricted diameter," European Journal of Operational Research, Elsevier, vol. 236(2), pages 410-418.
    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. 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.
    2. F. Bendali & A.R. Mahjoub & J. Mailfert, 2002. "Composition of Graphs and the Triangle-Free Subgraph Polytope," Journal of Combinatorial Optimization, Springer, vol. 6(4), pages 359-381, December.
    3. Teobaldo Bulhões & Anand Subramanian & Gilberto F. Sousa Filho & Lucídio dos Anjos F. Cabral, 2017. "Branch-and-price for p-cluster editing," Computational Optimization and Applications, Springer, vol. 67(2), pages 293-316, June.
    4. Maciej Rysz & Mohammad Mirghorbani & Pavlo Krokhmal & Eduardo L. Pasiliao, 2014. "On risk-averse maximum weighted subgraph problems," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 167-185, July.
    5. Benati, Stefano & Ponce, Diego & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "A branch-and-price procedure for clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 297(3), pages 817-830.
    6. Timo Gschwind & Stefan Irnich & Isabel Podlinski, 2015. "Maximum Weight Relaxed Cliques and Russian Doll Search Revisited," Working Papers 1504, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 19 May 2015.
    7. Bulhões, Teobaldo & Correia, Rubens & Subramanian, Anand, 2022. "Conference scheduling: A clustering-based approach," European Journal of Operational Research, Elsevier, vol. 297(1), pages 15-26.
    8. Şuvak, Zeynep & Altınel, İ. Kuban & Aras, Necati, 2020. "Exact solution algorithms for the maximum flow problem with additional conflict constraints," European Journal of Operational Research, Elsevier, vol. 287(2), pages 410-437.
    9. Maciej Rysz & Foad Mahdavi Pajouh & Pavlo Krokhmal & Eduardo L. Pasiliao, 2018. "Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights," Annals of Operations Research, Springer, vol. 262(1), pages 89-108, March.
    10. Hamidreza Validi & Austin Buchanan, 2020. "The Optimal Design of Low-Latency Virtual Backbones," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 952-967, October.
    11. Thays A. Oliveira & Yuri B. Gabrich & Helena Ramalhinho & Miquel Oliver & Miri W. Cohen & Luiz S. Ochi & Serigne Gueye & Fábio Protti & Alysson A. Pinto & Diógenes V. M. Ferreira & Igor M. Coelho & Vi, 2020. "Mobility, Citizens, Innovation and Technology in Digital and Smart Cities," Future Internet, MDPI, vol. 12(2), pages 1-27, January.
    12. Zhuqi Miao & Balabhaskar Balasundaram, 2020. "An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 763-778, July.
    13. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2021. "A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1070-1090, July.
    14. Zhuqi Miao & Balabhaskar Balasundaram & Eduardo L. Pasiliao, 2014. "An exact algorithm for the maximum probabilistic clique problem," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 105-120, July.
    15. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques," Working Papers 1723, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    16. Austin Buchanan & Je Sang Sung & Sergiy Butenko & Eduardo L. Pasiliao, 2015. "An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 178-188, February.
    17. Li, Xiangyong & Aneja, Y.P., 2017. "Regenerator location problem: Polyhedral study and effective branch-and-cut algorithms," European Journal of Operational Research, Elsevier, vol. 257(1), pages 25-40.
    18. Tuan Le & Jon M. Stauffer & Bala Shetty & Chelliah Sriskandarajah, 2023. "An optimization framework for analyzing dual‐donor organ exchange," Production and Operations Management, Production and Operations Management Society, vol. 32(3), pages 740-761, March.
    19. Alexander Veremyev & Oleg A. Prokopyev & Sergiy Butenko & Eduardo L. Pasiliao, 2016. "Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs," Computational Optimization and Applications, Springer, vol. 64(1), pages 177-214, May.
    20. Gang Yu & Olivier Goldschmidt, 1996. "On locally optimal independent sets and vertex covers," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(5), pages 737-748, August.

    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:spr:jglopt:v:76:y:2020:i:3:d:10.1007_s10898-018-0694-2. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.