Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs
Mamadou Moustapha Kanté, Lhouari Nourine · SIAM Journal on Discrete Mathematics · 2016
We give linear and polynomial time algorithms for computing the hull number of distance-hereditary and chordal graphs, respectively. The complexity of computing the hull number in chordal and distance-hereditary graphs has been open since the introduction of the notion in [M. G. Everett and S. B. Seidman, Discrete Math., 57 (1985), pp. 217--223]. Prior to our result polynomial time algorithms were only known for subclasses of considered graph classes, e.g., split graphs, cographs, interval graphs. Our techniques allow us to give at the same time a linear time algorithm for computing the geodetic number in distance-hereditary graphs. Another consequence of the techniques used is an incremental output-polynomial algorithm to list the set of (inclusion-wise) minimal hull sets in any graphs.