Distance-Based Covering Problems for Graphs of Given Cyclomatic Number

Dibyayan Chakraborty (1) , Florent Foucaud (2) , Anni Hakanen (2)

1 ENS de Lyon - École normale supérieure de Lyon
2 LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes

We study a large family of graph covering problems, whose definitions rely on distances, for graphs of bounded cyclomatic number (that is, the minimum number of edges that need to be removed from the graph to destroy all cycles). These problems include (but are not restricted to) three families of problems: (i) variants of metric dimension, where one wants to choose a small set S of vertices of the graph such that every vertex is uniquely determined by its ordered vector of distances to the vertices of S; (ii) variants of geodetic sets, where one wants to select a small set S of vertices such that any vertex lies on some shortest path between two vertices of S; (iii) variants of path covers, where one wants to select a small set of paths such that every vertex or edge belongs to one of the paths. We generalize and/or improve previous results in the area which show that the optimal values for these problems can be upper-bounded by a linear function of the cyclomatic number and the degree 1-vertices of the graph. To this end, we develop and enhance a technique recently introduced in [C. Lu, Q. Ye, C. Zhu. Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs, Journal of Combinatorial Optimization 44:2029–2039, 2022] and give near-optimal bounds in several cases. This solves (in some cases fully, in some cases partially) some conjectures and open questions from the literature. The method, based on breadth-first search, is of algorithmic nature and thus, all the constructions can be computed in linear time. Our results also imply an algorithmic consequence for the computation of the optimal solutions: they can all be computed in polynomial time for graphs of bounded cyclomatic number.

Domaines: Mathématique discrète [cs.DM]; Algorithme et structure de données [cs.DS]; Combinatoire [math.CO]

Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen. Distance-Based Covering Problems for Graphs of Given Cyclomatic Number. 24th International Symposium on Fundamentals of Computation Theory (FCT 2023), Sep 2023, Trier, Germany. pp.132-146, ⟨10.1007/978-3-031-43587-4_10⟩. ⟨hal-04214541⟩