Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers

Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung +3

We study how covering a graph by a small number of shortest or approximately shortest paths/walks constrains its treewidth and pathwidth. A path or walk is $(\alpha ,\beta )$-quasi-shortest f…