IDEAS home Printed from https://ideas.repec.org/p/jgu/wpaper/1723.html
   My bibliography  Save this paper

A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques

Author

Listed:
  • Timo Gschwind

    (Johannes Gutenberg-Universität Mainz, Germany)

  • Stefan Irnich

    (Johannes Gutenberg-University Mainz, Germany)

  • Fabio Furini

    (LAMSADE Université Paris Dauphine, France)

  • Roberto Wolfler Calvo

    (LIPN Université Paris, France)

Abstract

We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subset of vertices of a graph for which a clique-defining property is relaxed, e.g., the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new e ective pricing algorithms are developed and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, e.g., structure-preserving versus dichotomous branching and their interplay with di erent pricing algorithms. The finally chosen setup for the branch-and-price produces results that demonstrate the e ectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.

Suggested Citation

  • 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.
  • Handle: RePEc:jgu:wpaper:1723
    as

    Download full text from publisher

    File URL: https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1723.pdf
    File Function: First version, 2017
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. de Werra, D., 1985. "An introduction to timetabling," European Journal of Operational Research, Elsevier, vol. 19(2), pages 151-162, February.
    2. Veremyev, Alexander & Boginski, Vladimir, 2012. "Identifying large robust network clusters via new compact formulations of maximum k-club problems," European Journal of Operational Research, Elsevier, vol. 218(2), pages 316-326.
    3. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1722, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    4. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    5. 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.
    6. Stefano Gualandi & Federico Malucelli, 2012. "Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 81-100, February.
    7. Balabhaskar Balasundaram & Sergiy Butenko & Illya V. Hicks, 2011. "Clique Relaxations in Social Network Analysis: The Maximum k -Plex Problem," Operations Research, INFORMS, vol. 59(1), pages 133-142, February.
    8. Bourjolly, Jean-Marie & Laporte, Gilbert & Pesant, Gilles, 2002. "An exact algorithm for the maximum k-club problem in an undirected graph," European Journal of Operational Research, Elsevier, vol. 138(1), pages 21-28, April.
    9. Pattillo, Jeffrey & Youssef, Nataly & Butenko, Sergiy, 2013. "On clique relaxation models in network analysis," European Journal of Operational Research, Elsevier, vol. 226(1), pages 9-18.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1722, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.

    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. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1722, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    2. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wol?er Calvo, 2015. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1520, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    3. Komusiewicz, Christian & Nichterlein, André & Niedermeier, Rolf & Picker, Marten, 2019. "Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: Theory and experiments," European Journal of Operational Research, Elsevier, vol. 275(3), pages 846-864.
    4. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    5. 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.
    6. Timo Gschwind & Stefan Irnich, 2016. "Dual Inequalities for Stabilized Column Generation Revisited," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 175-194, February.
    7. Alexander Veremyev & Vladimir Boginski & Eduardo Pasiliao, 2015. "Analytical characterizations of some classes of optimal strongly attack-tolerant networks and their Laplacian spectra," Journal of Global Optimization, Springer, vol. 61(1), pages 109-138, January.
    8. Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Illya V. Hicks, 2016. "On the 2-Club Polytope of Graphs," Operations Research, INFORMS, vol. 64(6), pages 1466-1481, December.
    9. Yezerska, Oleksandra & Mahdavi Pajouh, Foad & Butenko, Sergiy, 2017. "On biconnected and fragile subgraphs of low diameter," European Journal of Operational Research, Elsevier, vol. 263(2), pages 390-400.
    10. Bruno Nogueira & Rian G. S. Pinheiro, 2020. "A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems," Annals of Operations Research, Springer, vol. 284(1), pages 367-400, January.
    11. Kristiansen, Simon & Sørensen, Matias & Stidsen, Thomas R., 2011. "Elective course planning," European Journal of Operational Research, Elsevier, vol. 215(3), pages 713-720, December.
    12. 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.
    13. Chitra Balasubramaniam & Sergiy Butenko, 2017. "On robust clusters of minimum cardinality in networks," Annals of Operations Research, Springer, vol. 249(1), pages 17-37, February.
    14. 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.
    15. Furini, Fabio & Ljubić, Ivana & Martin, Sébastien & San Segundo, Pablo, 2019. "The maximum clique interdiction problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 112-127.
    16. David R. Morrison & Jason J. Sauppe & Edward C. Sewell & Sheldon H. Jacobson, 2014. "A Wide Branching Strategy for the Graph Coloring Problem," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 704-717, November.
    17. 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.
    18. David R. Morrison & Edward C. Sewell & Sheldon H. Jacobson, 2016. "Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 67-82, February.
    19. Almeida, Maria Teresa & Carvalho, Filipa D., 2014. "An analytical comparison of the LP relaxations of integer models for the k-club problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 489-498.
    20. Zhou, Qing & Benlic, Una & Wu, Qinghua, 2020. "An opposition-based memetic algorithm for the maximum quasi-clique problem," European Journal of Operational Research, Elsevier, vol. 286(1), pages 63-83.

    More about this item

    Keywords

    Graph decomposition; clique relaxations; branch-and-price algorithm; social networks;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:jgu:wpaper:1723. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: https://edirc.repec.org/data/vlmaide.html .

    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: Research Unit IPP (email available below). General contact details of provider: https://edirc.repec.org/data/vlmaide.html .

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.