Document Open Access Logo

Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

Authors A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, Shakhar Smorodinsky

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.2.pdf
  • Filesize: 0.63 MB
  • 12 pages

Document Identifiers

Author Details

A. Karim Abu-Affash
Paz Carmi
Anil Maheshwari
Pat Morin
Michiel Smid
Shakhar Smorodinsky

Cite As Get BibTex

A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, and Shakhar Smorodinsky. Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.2

Abstract

We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0.
In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.

Subject Classification

Keywords
  • Approximation algorithms
  • maximum diameter-bounded subgraph
  • unit disk graphs
  • fractional Helly theorem
  • VC-dimension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. E. Ackerman. On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discrete Comput. Geom., 41:365-375, 2009. Google Scholar
  2. P. K. Agarwal, B. Aronov, J. Pach, and M. Sharir. Quasi-planar graphs have linear number of edges. Combinatorica, 17:1-9, 1997. Google Scholar
  3. R. D. Alba. A graph-theoretic definition of a sociometric clique. J. Math. Sociol., 3:113-126, 1973. Google Scholar
  4. M. T. Almeida and F. D. Carvalho. Integer models and upper bounds for the 3-club problem. Networks, 60:155-166, 2012. Google Scholar
  5. Y. Asahiro, E. Miyano, and K. Samizo. Approximating maximum diameter-bounded subgraphs. In LATIN, LNCS 6034, pages 615-626, 2010. Google Scholar
  6. B. Balasundaram, S. Butenko, and Trukhanov S. Novel approaches for analyzing biological networks. J. Combin. Optim., 10:23-39, 2005. Google Scholar
  7. I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo. The maximum clique problem. Handbook of Combinatorial Optimization, pages 1-74, Kluwer Academic Publishers, 1999. Google Scholar
  8. J.-M. Bourjolly, G. Laporte, and G. Pesant. An exact algorithm for the maximum k-club problem in an undirected graph. European J. Oper. Res., 138:21-28, 2002. Google Scholar
  9. A. Buchanan and H. Salemi. Parsimonious formulations for low-diameter clusters. http://www.optimization-online.org/DB_HTML 09/6196.html, 2017. Google Scholar
  10. F. D. Carvalho and M. T. Almeida. Upper bounds and heuristics for the 2-club problem. European J. Oper. Res., 210:489-494, 2011. Google Scholar
  11. M.-S. Chang, L.-J. Hung, C.-R. Lin, and P.-C. Su. Finding large k-clubs in undirected graphs. Computing, 95:739-758, 2013. Google Scholar
  12. V. Chepoi, B. Estellon, and Y. Vaxès. Covering planar graphs with a fixed number of balls. Discrete Comput. Geom., 37:237-244, 2007. Google Scholar
  13. B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Math., 86:165-177, 1990. Google Scholar
  14. A. Gräf, M. Stumpf, and G. Weißenfels. On coloring unit disk graphs. Algorithmica, 20(3):277-293, 1998. Google Scholar
  15. S. Har-Peled. Geometric Approximation Algorithms. American Mathematical Society, Boston, USA, 2011. Google Scholar
  16. J. Håstad. Clique is hard to approximate within n^1-ε. In FOCS, pages 627-636, 1996. Google Scholar
  17. J. Matoušek. Lectures on Discrete Geometry. Springer, New York, USA, 2002. Google Scholar
  18. J. Matoušek. Bounded VC-dimension implies a fractional Helly theorem. Discrete Comput. Geom., 31:251-255, 2004. Google Scholar
  19. J. Pattillo, Y. Wang, and S. Butenko. Approximating 2-cliques in unit disk graphs. Discrete Appl. Math., 166:178-187, 2014. Google Scholar
  20. J. Pattillo, N. Youssef, and S. Butenko. On clique relaxation models in network analysis. European J. Oper. Res., 226:9-18, 2013. Google Scholar
  21. A. Veremyev and V. Boginski. Identifying large robust network clusters via new compact formulations of maximum k-club problems. European J. Oper. Res., 218:316-326, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact