Document Open Access Logo

Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs

Authors Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, Bodhayan Roy

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.7.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Dibyayan Chakraborty
  • Indraprastha Institute of Information Technology, Delhi, India
Sandip Das
  • Indian Statistical Institute, Kolkata, India
Florent Foucaud
  • Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France
Harmender Gahlawat
  • Indian Statistical Institute, Kolkata, India
Dimitri Lajou
  • Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France
Bodhayan Roy
  • Indian Institute of Technology, Kharagpur, India

Funding

This research was financed by the IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39) and the ANR project HOSIGRA (ANR-17-CE40-0022).
  • Roy, Bodhayan: B. Roy is supported by an ISIRD Grant from Sponsored Research and Industrial Consultancy, IIT Kharagpur.

Cite AsGet BibTex

Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, and Bodhayan Roy. Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.7

Abstract

We study the complexity of finding the geodetic number on subclasses of planar graphs and chordal graphs. A set S of vertices of a graph G is a geodetic set if every vertex of G lies in a shortest path between some pair of vertices of S. The Minimum Geodetic Set (MGS) problem is to find a geodetic set with minimum cardinality of a given graph. The problem is known to remain NP-hard on bipartite graphs, chordal graphs, planar graphs and subcubic graphs. We first study MGS on restricted classes of planar graphs: we design a linear-time algorithm for MGS on solid grids, improving on a 3-approximation algorithm by Chakraborty et al. (CALDAM, 2020) and show that MGS remains NP-hard even for subcubic partial grids of arbitrary girth. This unifies some results in the literature. We then turn our attention to chordal graphs, showing that MGS is fixed parameter tractable for inputs of this class when parameterized by their treewidth (which equals the clique number minus one). This implies a linear-time algorithm for k-trees, for fixed k. Then, we show that MGS is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012). As interval graphs are very constrained, to prove the latter result we design a rather sophisticated reduction technique to work around their inherent linear structure.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Geodetic set
  • Planar graph
  • Chordal graph
  • Interval graph
  • FPT algorithm

Metrics

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

Related Versions

References

  1. B. Allgeier. Structure and properties of maximal outerplanar graphs. PhD Thesis, University of Louisville, 2009. Google Scholar
  2. R. Belmonte, P. A. Golovach, P. Heggernes, P. van't Hof, M. Kamiński, and D. Paulusma. Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica, 69:501-521, 2014. Google Scholar
  3. É. Bonnet and P. Rzążewski. Optimality program in segment and string graphs. Algorithmica, 81(7):3047-3073, 2019. Google Scholar
  4. L. R. Bueno, L. D. Penso, F. Protti, V. R. Ramos, D. Rautenbach, and U. S. Souza. On the hardness of finding the geodetic number of a subcubic graph. Information Processing Letters, 135:22-27, 2018. Google Scholar
  5. D. Chakraborty, S. Das, F. Foucaud, H. Gahlawat, D. Lajou, and B. Roy. Algorithms and complexity for geodetic sets on planar and chordal graphs, 2020. URL: http://arxiv.org/abs/2006.16511.
  6. D. Chakraborty, F. Foucaud, H. Gahlawat, S. K. Ghosh, and B. Roy. Hardness and approximation for the geodetic set problem in some graph classes. In CALDAM'20, pages 102-115. Springer, 2020. Google Scholar
  7. B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete mathematics, 86(1-3):165-177, 1990. Google Scholar
  8. M. C. Dourado, F. Protti, D. Rautenbach, and J.L. Szwarcfiter. Some remarks on the geodetic number of a graph. Discrete Mathematics, 310(4):832-837, 2010. Google Scholar
  9. M. C. Dourado, F. Protti, and J.L. Szwarcfiter. On the complexity of the geodetic and convexity numbers of a graph. In ICDM, volume 7, pages 101-108. Ramanujan Mathematical Society, 2008. Google Scholar
  10. T. Ekim, A. Erey, P. Heggernes, P. van’t Hof, and D. Meister. Computing minimum geodetic sets of proper interval graphs. In LATIN'12, pages 279-290. Springer, 2012. Google Scholar
  11. M. Farber and R. E. Jamison. Convexity in graphs and hypergraphs. SIAM Journal on Algebraic Discrete Methods, 7(3):433-444, 1986. Google Scholar
  12. A. E. Feldmann and P. Widmayer. An o(n⁴) time algorithm to compute the bisection width of solid grid graphs. In European Symposium on Algorithms, pages 143-154. Springer, 2011. Google Scholar
  13. F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 78:914-944, 2017. Google Scholar
  14. M. R. Garey and D. S. Johnson. Computers and intractability, volume 29. W. H.Freeman New York, 2002. Google Scholar
  15. G. C. M. Gomes, C. V. G. C. Lima, and V. F. dos Santos. Parameterized Complexity of Equitable Coloring. Discrete Mathematics & Theoretical Computer Science, vol. 21 no. 1, ICGT 2018, May 2019. Google Scholar
  16. A. Gregori. Unit-length embedding of binary trees on a square grid. Information Processing Letters, 31(4):167-173, 1989. Google Scholar
  17. F. Harary, E. Loukakis, and C. Tsouros. The geodetic number of a graph. Mathematical and Computer Modelling, 17(11):89-95, 1993. Google Scholar
  18. P. Heggernes, P. van't Hof, D. Meister, and Y. Villanger. Induced subgraph isomorphism on proper interval and bipartite permutation graphs. Theoretical Computer Science, 562:252-269, 2015. Google Scholar
  19. L. Kellerhals and T. Koana. Parameterized complexity of geodetic set. arXiv, 2020. URL: http://arxiv.org/abs/2001.03098.
  20. F. Keshavarz-Kohjerdi, A. Bagheri, and A. Asgharian-Sardroud. A linear-time algorithm for the longest path problem in rectangular grid graphs. Discrete Applied Mathematics, 160(3):210-217, 2012. Google Scholar
  21. M. Mezzini. Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs. Theoretical Computer Science, 745:63-74, 2018. Google Scholar
  22. I. M. Pelayo. Geodesic Convexity in Graphs. Springer, 2013. Google Scholar
  23. C. Thomassen. Interval representations of planar graphs. Journal of Combinatorial Theory, Series B, 40(1):9-20, 1986. Google Scholar
  24. C. Umans and W. Lenhart. Hamiltonian cycles in solid grid graphs. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 496-505. IEEE, 1997. Google Scholar
  25. L. G. Valiant. Universality considerations in VLSI circuits. IEEE Transactions on Computers, 100(2):135-140, 1981. 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 Imprint Privacy Contact