Animation scientifique

In this talk, we investigate the structural properties of graphs admitting a cover by a small set of metrically relevant routes, i.e. shortest paths and quasi-shortest walks. A walk (or path) is quasi-shortest if each contiguous segment between vertices u and v of the walk has a length bounded by an affine function of the distance between u and v. We give pathwidth and treewidth polynomial upper bounds in various covering scenarios and derive superlinear lower bounds. Finally, the treewidth bounds yield XP algorithms parameterized by k for recognizing graphs coverable by k shortest paths or k quasi-shortest walks, using exact evaluations of Blocked-CMSO formulas on bounded-treewidth graphs.