On the hull and interval numbers of oriented graphs
share
In this work, for a given oriented graph D, we study its interval and hull numbers, denoted by in(D) and hn(D), respectively, in the geodetic, P_3 and P_3^* convexities. This last one, we believe to be formally defined and first studied in this paper, although its undirected version is well-known in the literature. Concerning bounds, for a strongly oriented graph D, we prove that hn_g(D)≤ m(D)-n(D)+2 and that there is a strongly oriented graph such that hn_g(D) = m(D)-n(D). We also determine exact values for the hull numbers in these three convexities for tournaments, which imply polynomial-time algorithms to compute them. These results allows us to deduce polynomial-time algorithms to compute hn_P_3(D) when the underlying graph of D is split or cobipartite. Moreover, we provide a meta-theorem by proving that if deciding whether in_g(D)≤ k or hn_g(D)≤ k is NP-hard or W[i]-hard parameterized by k, for some i∈ℤ_+^*, then the same holds even if the underlying graph of D is bipartite. Next, we prove that deciding whether hn_P_3(D)≤ k or hn_P_3^*(D)≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is bipartite; that deciding whether in_P_3(D)≤ k or in_P_3^*(D)≤ k is NP-complete, even if D has no directed cycles and the underlying graph of D is a chordal bipartite graph; and that deciding whether in_P_3(D)≤ k or in_P_3^*(D)≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is split. We also argue that the interval and hull numbers in the oriented P_3 and P_3^* convexities can be computed in polynomial time for graphs of bounded tree-width by using Courcelle's theorem.
READ FULL TEXT