IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v23y2012i1d10.1007_s10878-010-9343-5.html
   My bibliography  Save this article

The max quasi-independent set problem

Author

Listed:
  • N. Bourgeois

    (CNRS FRE 3234 and Université Paris-Dauphine)

  • A. Giannakos

    (CNRS FRE 3234 and Université Paris-Dauphine)

  • G. Lucarelli

    (CNRS FRE 3234 and Université Paris-Dauphine
    Athens University of Economics and Business)

  • I. Milis

    (Athens University of Economics and Business)

  • V. T. Paschos

    (CNRS FRE 3234 and Université Paris-Dauphine)

  • O. Pottié

    (CNRS FRE 3234 and Université Paris-Dauphine)

Abstract

In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f-max quasi-independent set, consists of, given a graph and a non-decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f(|Q|). For this problem, we show an exact solution method that runs within time $O^{*}(2^{\frac{d-27/23}{d+1}n})$ on graphs of average degree bounded by d. For the most specifically defined γ-max quasi-independent set and k-max quasi-independent set problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.

Suggested Citation

  • N. Bourgeois & A. Giannakos & G. Lucarelli & I. Milis & V. T. Paschos & O. Pottié, 2012. "The max quasi-independent set problem," Journal of Combinatorial Optimization, Springer, vol. 23(1), pages 94-117, January.
    • Handle: RePEc:spr:jcomop:v:23:y:2012:i:1:d:10.1007_s10878-010-9343-5
    DOI: 10.1007/s10878-010-9343-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-010-9343-5
    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/s10878-010-9343-5?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. Leland H. Hartwell & John J. Hopfield & Stanislas Leibler & Andrew W. Murray, 1999. "From molecular to modular cell biology," Nature, Nature, vol. 402(6761), pages 47-52, December.
    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. Bourgeois, Nicolas & Giannakos, Aristotelis & Lucarelli, Giorgio & Milis, Ioannis & Paschos, Vangelis Th., 2017. "Exact and superpolynomial approximation algorithms for the densest k-subgraph problem," European Journal of Operational Research, Elsevier, vol. 262(3), pages 894-903.
    2. 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.

    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. Ochiai & J. C. Nacher, 2007. "Stochastic analysis of autoregulatory gene expression dynamics," Mathematical and Computer Modelling of Dynamical Systems, Taylor & Francis Journals, vol. 14(4), pages 377-388, November.
    2. Simeon D. Castle & Michiel Stock & Thomas E. Gorochowski, 2024. "Engineering is evolution: a perspective on design processes to engineer biology," Nature Communications, Nature, vol. 15(1), pages 1-10, December.
    3. Frederic Li Mow Chee & Bruno Beernaert & Billie G. C. Griffith & Alexander E. P. Loftus & Yatendra Kumar & Jimi C. Wills & Martin Lee & Jessica Valli & Ann P. Wheeler & J. Douglas Armstrong & Maddy Pa, 2023. "Mena regulates nesprin-2 to control actin–nuclear lamina associations, trans-nuclear membrane signalling and gene expression," Nature Communications, Nature, vol. 14(1), pages 1-19, December.
    4. Joshua S Weitz & Philip N Benfey & Ned S Wingreen, 2007. "Evolution, Interactions, and Biological Networks," PLOS Biology, Public Library of Science, vol. 5(1), pages 1-3, January.
    5. Bo Xu & Hongfei Lin & Yang Chen & Zhihao Yang & Hongfang Liu, 2013. "Protein Complex Identification by Integrating Protein-Protein Interaction Evidence from Multiple Sources," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-12, December.
    6. Robrecht Cannoodt & Joeri Ruyssinck & Jan Ramon & Katleen De Preter & Yvan Saeys, 2018. "IncGraph: Incremental graphlet counting for topology optimisation," PLOS ONE, Public Library of Science, vol. 13(4), pages 1-11, April.
    7. Margaritis Voliotis & Philipp Thomas & Ramon Grima & Clive G Bowsher, 2016. "Stochastic Simulation of Biomolecular Networks in Dynamic Environments," PLOS Computational Biology, Public Library of Science, vol. 12(6), pages 1-18, June.
    8. Cui, Xue-Mei & Yoon, Chang No & Youn, Hyejin & Lee, Sang Hoon & Jung, Jean S. & Han, Seung Kee, 2017. "Dynamic burstiness of word-occurrence and network modularity in textbook systems," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 487(C), pages 103-110.
    9. Yongli Li & Chong Wu & Zizheng Wang, 2015. "An information-theoretic approach for detecting communities in networks," Quality & Quantity: International Journal of Methodology, Springer, vol. 49(4), pages 1719-1733, July.
    10. Anne Lopes & Sophie Sacquin-Mora & Viktoriya Dimitrova & Elodie Laine & Yann Ponty & Alessandra Carbone, 2013. "Protein-Protein Interactions in a Crowded Environment: An Analysis via Cross-Docking Simulations and Evolutionary Information," PLOS Computational Biology, Public Library of Science, vol. 9(12), pages 1-18, December.
    11. Sun, Lanfang & Jiang, Lu & Li, Menghui & He, Dacheng, 2006. "Statistical analysis of gene regulatory networks reconstructed from gene expression data of lung cancer," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 370(2), pages 663-671.
    12. Andriani, Pierpaolo & Carignani, Giuseppe, 2014. "Modular exaptation: A missing link in the synthesis of artificial form," Research Policy, Elsevier, vol. 43(9), pages 1608-1620.
    13. Mahdieh Ghasemi & Maseud Rahgozar & Gholamreza Bidkhori & Ali Masoudi-Nejad, 2013. "C-element: A New Clustering Algorithm to Find High Quality Functional Modules in PPI Networks," PLOS ONE, Public Library of Science, vol. 8(9), pages 1-12, September.
    14. Bogna J. Smug & Krzysztof Szczepaniak & Eduardo P. C. Rocha & Stanislaw Dunin-Horkawicz & Rafał J. Mostowy, 2023. "Ongoing shuffling of protein fragments diversifies core viral functions linked to interactions with bacterial hosts," Nature Communications, Nature, vol. 14(1), pages 1-16, December.
    15. Andras Gyorgy, 2023. "Competition and evolutionary selection among core regulatory motifs in gene expression control," Nature Communications, Nature, vol. 14(1), pages 1-12, December.
    16. Tracy Chih-Ting Koubkova-Yu & Jung-Chi Chao & Jun-Yi Leu, 2018. "Heterologous Hsp90 promotes phenotypic diversity through network evolution," PLOS Biology, Public Library of Science, vol. 16(11), pages 1-29, November.
    17. Krishnan, Arun & Tomita, Masaru & Giuliani, Alessandro, 2008. "Evolution of gene regulatory networks: Robustness as an emergent property of evolution," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(8), pages 2170-2186.
    18. Haijia Shi & Lei Shi, 2014. "Identifying Emerging Motif in Growing Networks," PLOS ONE, Public Library of Science, vol. 9(6), pages 1-12, June.
    19. Elena Kutumova & Ilya Akberdin & Ilya Kiselev & Ruslan Sharipov & Fedor Kolpakov, 2022. "Modular Representation of Physiologically Based Pharmacokinetic Models: Nanoparticle Delivery to Solid Tumors in Mice as an Example," Mathematics, MDPI, vol. 10(7), pages 1-20, April.
    20. Cai Gao & Xin Lan & Xiaoge Zhang & Yong Deng, 2013. "A Bio-Inspired Methodology of Identifying Influential Nodes in Complex Networks," PLOS ONE, Public Library of Science, vol. 8(6), pages 1-11, June.

    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:jcomop:v:23:y:2012:i:1:d:10.1007_s10878-010-9343-5. 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.