Document Open Access Logo

Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width

Authors Lars Jaffke , O-joung Kwon , Torstein J. F. Strømme , Jan Arne Telle

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.6.pdf
  • Filesize: 0.62 MB
  • 14 pages

Document Identifiers

Author Details

Lars Jaffke
  • Department of Informatics, University of Bergen, Norway
O-joung Kwon
  • Department of Mathematics, Incheon National University, Incheon, South Korea
Torstein J. F. Strømme
  • Department of Informatics, University of Bergen, Norway
Jan Arne Telle
  • Department of Informatics, University of Bergen, Norway

Funding

  • Jaffke, Lars: Supported by the Bergen Research Foundation (BFS).

Cite AsGet BibTex

Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.IPEC.2018.6

Abstract

We generalize the family of (sigma, rho)-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-r dominating set and distance-r independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as k-trapezoid graphs, Dilworth k-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, k-polygon graphs, circular arc graphs, complements of d-degenerate graphs, and H-graphs if given an H-representation. To supplement these findings, we show that many classes of (distance) (sigma, rho)-problems are W[1]-hard parameterized by mim-width + solution size.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Graph Width Parameters
  • Graph Classes
  • Distance Domination Problems
  • Parameterized Complexity

Metrics

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

Related Versions

References

  1. Geir Agnarsson, Peter Damaschke, and Magnús M. Halldórsson. Powers of geometric intersection graphs and dispersion algorithms. Discrete Appl. Math., 132(1-3):3-16, 2003. URL: http://dx.doi.org/10.1016/S0166-218X(03)00386-X.
  2. Gábor Bacsó, Dániel Marx, and Zsolt Tuza. H-free graphs, independent sets, and subexponential-time algorithms. In Proc. IPEC 2016, pages 3:1-3:12, 2017. Google Scholar
  3. Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci., 511:54-65, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.01.011.
  4. Norman Biggs. Perfect codes in graphs. J. Combin. Theory, Ser. B, 15(3):289-296, 1973. URL: http://dx.doi.org/10.1016/0095-8956(73)90042-7.
  5. A. Brandstädt, V. Le, and J. Spinrad. Graph Classes: A Survey. SIAM, 1999. URL: http://dx.doi.org/10.1137/1.9780898719796.
  6. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci., 511:66-76, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.01.009.
  7. Steven Chaplick, Martin Töpfer, Jan Voborník, and Peter Zeman. On H-topological intersection graphs. In Proc. WG 2017, pages 167-179. Springer, 2017. Google Scholar
  8. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53-61, 2009. Google Scholar
  9. Carsten Flotow. On powers of m-trapezoid graphs. Discrete Appl. Math., 63(2):187-192, 1995. URL: http://dx.doi.org/10.1016/0166-218X(95)00062-V.
  10. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs. In Proc. ESA 2018, pages 30:1-30:14, 2018. Google Scholar
  11. M. A. Henning, Ortrud R. Oellermann, and Henda C. Swart. Bounds on distance domination parameters. J. Combin. Inform. Syst. Sci., 16(1):11-18, 1991. Google Scholar
  12. Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized Distance-Domination Problems and Their Complexity on Graphs of Bounded Mim-Width. arXiv preprint, 2018. arXiv:1803.03514. Google Scholar
  13. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. In Proc. STACS 2018, pages 42:1-42:14, 2018. Google Scholar
  14. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci., 67(4):757-771, 2003. Google Scholar
  15. Akul Rana, Anita Pal, and Madhumangal Pal. An efficient algorithm to solve the distance k-domination problem on permutation graphs. J. Discrete Math. Sci. Cryptography, 19(2):241-255, 2016. Google Scholar
  16. Arundhati Raychaudhuri. On powers of strongly chordal and circular arc graphs. Ars Combin., 34:147-160, 1992. Google Scholar
  17. Sigve Hortemo Sæther and Martin Vatshelle. Hardness of computing width parameters based on branch decompositions over the vertex set. Theor. Comput. Sci., 615:120-125, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.11.039.
  18. Peter J. Slater. R-domination in graphs. J. ACM, 23(3):446-450, 1976. Google Scholar
  19. Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math., 10(4):529-550, 1997. Google Scholar
  20. Martin Vatshelle. New width parameters of graphs. PhD thesis, University of Bergen, 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 Imprint Privacy Contact