Block decomposition approach to compute a minimum geodetic set. (English) Zbl 1301.05100
Summary: In this paper, we develop a divide-and-conquer approach, called block decomposition, to solve the minimum geodetic set problem. This provides us with a unified approach for all graphs admitting blocks for which the problem of finding a minimum geodetic set containing a given set of vertices (\(g\)-extension problem) can be efficiently solved. Our method allows us to derive linear time algorithms for the minimum geodetic set problem in (a proper superclass of) block-cacti and monopolar chordal graphs. Also, we show that hull sets and geodetic sets of block-cacti are the same, and the minimum geodetic set problem is NP-hard in cobipartite graphs. We conclude by pointing out several interesting research directions.
MSC:
05C12 | Distance in graphs |
05C85 | Graph algorithms (graph-theoretic aspects) |
68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
68Q25 | Analysis of algorithms and problem complexity |