UNI-MB - logo
UMNIK - logo
 
E-viri
Recenzirano Odprti dostop
  • On directed covering and do...
    Hanaka, Tesshu; Nishimura, Naomi; Ono, Hirotaka

    Discrete Applied Mathematics, 04/2019, Letnik: 259
    Journal Article

    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 Directedr-In (Out) Vertex Cover and Directed(p,q)-Edge Dominating Set as directed generalizations of Vertex Cover and Edge Dominating Set. For these problems, we show that (1) Directedr-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, Directedr-In (Out) Vertex Cover is W2-hard and clnk-inapproximable on directed acyclic graphs, (3) if either p or q is greater than 1, Directed(p,q)-Edge Dominating Set is W2-hard and clnk-inapproximable on directed acyclic graphs, (4) all problems can be solved in polynomial time on trees, and (5) Directed(0,1)-Edge ((1,0)-Edge, (1,1)-Edge) Dominating Set is fixed-parameter tractable on general graphs. The first result implies that Directedr-Dominating Set on directed line graphs is NP-complete even if r=1.