Document Open Access Logo

On Directed Covering and Domination Problems

Authors Tesshu Hanaka, Naomi Nishimura, Hirotaka Ono

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.45.pdf
  • Filesize: 0.65 MB
  • 12 pages

Document Identifiers

Author Details

Tesshu Hanaka
Naomi Nishimura
Hirotaka Ono

Cite As Get BibTex

Tesshu Hanaka, Naomi Nishimura, and Hirotaka Ono. On Directed Covering and Domination Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 45:1-45:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.45

Abstract

In this paper, we study covering and domination problems on directed graphs.
Although undirected Vertex Cover and Edge Dominating Set are well-studied classical graph problems, the directed versions have not been studied much due to the lack of clear definitions.

We give natural definitions for Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set as directed generations of Vertex Cover and Edge Dominating Set.
For these problems, we show that
(1) Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set are NP-complete on planar directed acyclic graphs except when r=1 or (p,q)=(0,0),
(2) if r>=2, Directed r-In (Out) Vertex Cover is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs,
(3) if either p or q is greater than 1,  Directed (p,q)-Edge Dominating Set is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs,
(4) all problems can be solved in polynomial time on trees, and
(5) Directed (0,1),(1,0),(1,1)-Edge Dominating Set are fixed-parameter tractable in general graphs.

The first result implies that (directed) r-Dominating Set on directed line graphs is NP-complete even if r=1.

Subject Classification

Keywords
  • directed graph
  • vertex cover
  • dominating set
  • edge dominating set
  • fixed-parameter algorithms

Metrics

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

References

  1. Alan A. Bertossi. The edge hamiltonian path problem is NP-complete. Information Processing Letters, 13(4):157-159, 1981. Google Scholar
  2. Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, and Jan Obdržálek. The dag-width of directed graphs. Journal of Combinatorial Theory, Series B, 102(4):900-923, 2012. Google Scholar
  3. Jacek Blazewicz, Alain Hertz, Daniel Kobler, and Dominique de Werra. On some properties of DNA graphs. Discrete Applied Mathematics, 98(1):1-19, 1999. Google Scholar
  4. Jacek Blazewicz, Marta Kasprzak, Benjamin Leroy-Beaulieu, and Dominique de Werra. Finding hamiltonian circuits in quasi-adjoint graphs. Discrete Applied Mathematics, 156(13):2573-2580, 2008. Google Scholar
  5. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. Google Scholar
  6. Jonathan F. Buss and Judy Goldsmith. Nondeterminism within P^*. SIAM Journal on Computing, 22(3):560-572, 1993. Google Scholar
  7. Miroslav Chlebík and Janka Chlebíková. Approximation hardness of dominating set problems in bounded degree graphs. Information and Computation, 206(11):1264-1275, 2008. Google Scholar
  8. Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS2009), pages 157-168. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2009. Google Scholar
  9. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing (STOC2014), pages 624-633. ACM, 2014. Google Scholar
  10. Rod G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24(4):873-921, 1995. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Parameterized computational feasibility. In Proceedings of Feasible Mathematics II, pages 219-244. Birkhäuser Boston, 1995. Google Scholar
  12. Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and sparseness: the case of dominating set. In Proceedings of 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), pages 31:1-31:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  13. Henning Fernau. edge dominating set: Efficient enumeration-based exact algorithms. In Proceedings of Parameterized and Exact Computation: Second International Workshop (IWPEC2006), pages 142-153. Springer Berlin Heidelberg, 2006. Google Scholar
  14. Jiří Fiala, Petr A. Golovach, and Jan Kratochvíl. Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theoretical Computer Science, 412(23):2513-2523, 2011. Google Scholar
  15. Robert Ganian, Petr Hliněný, Joachim Kneis, Alexander Langer, Jan Obdržálek, and Peter Rossmanith. Digraph width measures in parameterized algorithmics. Discrete Applied Mathematics, 168:88-107, 2014. Google Scholar
  16. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1979. Google Scholar
  17. Tesshu Hanaka, Shigemi Kagawa, Hirotaka Ono, and Keiichiro Kanemoto. Finding environmentally critical transmission sectors, transactions, and paths in global supply chain networks. Energy Economics, 2017. (in press). Google Scholar
  18. Frank Harary and Robert Z. Norman. Some properties of line digraphs. Rendiconti del Circolo Matematico di Palermo, 9(2):161-168, 1960. Google Scholar
  19. Thor Johnson, Neil Robertson, P.D. Seymour, and Robin Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138-154, 2001. Google Scholar
  20. Shigemi Kagawa, Sangwon Suh, Klaus Hubacek, Thomas Wiedmann, Keisuke Nansai, and Jan Minx. CO₂ emission clusters within global supply chain networks: Implications for climate change mitigation. Global Environmental Change, 35:486-496, 2015. Google Scholar
  21. Stephan Kreutzer and Siamak Tazari. Directed nowhere dense classes of graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2012), pages 1552-1562. Society for Industrial and Applied Mathematics, 2012. Google Scholar
  22. Michael Lahr and Erik Dietzenbacher. Input-Output Analysis: Frontiers and Extensions. Palgrave Macmillan UK, 2001. Google Scholar
  23. Omar Rifki, Hirotaka Ono, and Shigemi Kagawa. The robustest clusters in the input-output networks: global CO₂ emission clusters. Journal of Economic Structures, 6(1):3, 2017. Google Scholar
  24. Mihalis Yannakakis and Fanica Gavril. Edge dominating sets in graphs. SIAM Journal on Applied Mathematics, 38(3):364-372, 1980. 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