# On directed covering and domination problems

Tesshu Hanaka, Naomi Nishimura, Hirotaka Ono

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

## 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 NPcomplete even if r = 1.

Original language English 28th International Symposium on Algorithms and Computation, ISAAC 2017 Takeshi Tokuyama, Yoshio Okamoto Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing 9783959770545 https://doi.org/10.4230/LIPIcs.ISAAC.2017.45 Published - Dec 1 2017 28th International Symposium on Algorithms and Computation, ISAAC 2017 - Phuket, ThailandDuration: Dec 9 2017 → Dec 22 2017

### Publication series

Name Leibniz International Proceedings in Informatics, LIPIcs 92 1868-8969

### Other

Other 28th International Symposium on Algorithms and Computation, ISAAC 2017 Thailand Phuket 12/9/17 → 12/22/17

• Software

## Fingerprint

Dive into the research topics of 'On directed covering and domination problems'. Together they form a unique fingerprint.