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

Exact and superpolynomial approximation algorithms for the densest k-subgraph problem

Author

Listed:
  • Bourgeois, Nicolas
  • Giannakos, Aristotelis
  • Lucarelli, Giorgio
  • Milis, Ioannis
  • Paschos, Vangelis Th.

Abstract

The densest k-subgraph problem is a generalization of the maximum clique problem, in which we are given a graph and a positive integer k, and we search among all the subsets of k vertices of the input graph for the subset which induces the maximum number of edges. densest k-subgraph is a well known optimization problem with various applications as, for example, in the design of public encryption schemes, the evaluation of certain financial derivatives, the identification of communities with similar characteristics, etc. In this paper, we first present algorithms for finding exact solutions for densest k-subgraph which improve upon the standard exponential time complexity of an exhaustive enumeration by creating a link between the computation of an optimum for this problem to the computation of other graph-parameters such as dominating set, vertex cover, longest path, etc. An FPT algorithm is also proposed which considers as a parameter the size of the minimum vertex cover. Finally, we present several approximation algorithms which run in moderately exponential or parameterized time, describing trade-offs between complexity and approximability. In contrast with most of the algorithms in the bibliography, our algorithms need only polynomial space.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:262:y:2017:i:3:p:894-903
    DOI: 10.1016/j.ejor.2017.04.034
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717303673
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.04.034?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. Ulrich Pferschy & Joachim Schauer, 2016. "Approximation of the Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 308-318, May.
    2. Gerold Jäger & Anand Srivastav, 2005. "Improved Approximation Algorithms for Maximum Graph Partitioning Problems," Journal of Combinatorial Optimization, Springer, vol. 10(2), pages 133-167, September.
    3. 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.
    4. Frederic Roupin & Alain Billionnet, 2008. "A deterministic approximation algorithm for the Densest k-Subgraph Problem," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 3(3), pages 301-314.
    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. 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.
    2. Tesshu Hanaka, 2023. "Computing densest k-subgraph with structural parameters," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-17, January.

    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. Mourad El Ouali & Helena Fohlin & Anand Srivastav, 2016. "An approximation algorithm for the partial vertex cover problem in hypergraphs," Journal of Combinatorial Optimization, Springer, vol. 31(2), pages 846-864, February.
    2. Federico Della Croce & Vangelis Th. Paschos, 2014. "Efficient algorithms for the max $$k$$ -vertex cover problem," Journal of Combinatorial Optimization, Springer, vol. 28(3), pages 674-691, October.
    3. Britta Schulze & Michael Stiglmayr & Luís Paquete & Carlos M. Fonseca & David Willems & Stefan Ruzika, 2020. "On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(1), pages 107-132, August.
    4. Alain Billionnet & Sourour Elloumi & Amélie Lambert & Angelika Wiegele, 2017. "Using a Conic Bundle Method to Accelerate Both Phases of a Quadratic Convex Reformulation," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 318-331, May.
    5. Fritz Bökler & Markus Chimani & Mirko H. Wagner, 2022. "On the rectangular knapsack problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 96(1), pages 149-160, August.
    6. 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.

    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:262:y:2017:i:3:p:894-903. 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.