2019/11/22 by Araujo, Julio C. S., Arraes, Pedro S. M.
#05Cxx #Combinatorics (math.CO) #F.2 #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.1911.10240
Let D be an orientation of a simple graph. Given u,v∈ V(D), a directed shortest (u,v)-path is a (u,v)-geodesic. S ⊆ V(D) is convex if, for every u,v ∈ S, the vertices in each (u,v)-geodesic and in each (v,u)-geodesic are in S. For each S ⊆ V(D) the (convex) hull of S, denoted by [S], is the smallest convex set containing S. S ⊆ V(D) is a hull set if [S] = V(D). S ⊆ V(D) is a geodetic set of D if each vertex of D lies in a (u,v)-geodesic, for some u,v ∈ S. The cardinality of a minimum hull set (resp. geodetic set) of G is the hull number (resp. geodetic number) of D, denoted by \overrightarrow\textrmhn (D) (resp. \overrightarrow\textrmgn(D)). We first show a tight upper bound on \overrightarrow\textrmhn(D). Given k∈ℤ+^*, we prove that deciding if \overrightarrow\textrmhn≤ k is NP-complete when D is an oriented partial cube; and if \overrightarrow\textrmgn(D)≤ k is W[2]-hard parameterized by k and has no (c ⋅ ln n)-approximation algorithm, unless P = NP, even if D has an underlying graph that is bipartite or split or cobipartite. We also show polynomial-time algorithms to compute \overrightarrow\textrmhn(D) and \overrightarrow\textrmgn(D) when D is an oriented cactus.