On directed covering and domination problems

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 generalizations 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 ) - Edge ( ( 1 , 0 ) - Edge , ( 1 , 1 ) - Edge) Dominating Set is fixed-parameter tractable on general graphs. The first result implies that Directed r - Dominating Set on directed line graphs is NP-complete even if r = 1 .