Skip to Main content Skip to Navigation
Journal articles

Edge degeneracy: Algorithmic and structural results

Stratis Limnios 1 Christophe Paul 2 Joanny Perret 3 Dimitrios M. Thilikos 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 G-SCOP_OC - Optimisation Combinatoire
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : We consider a cops and robber game where the cops are blocking edges of a graph, while the robber occupies its vertices. At each round of the game, the cops choose some set of edges to block and right after the robber is obliged to move to another vertex traversing at most $s$ unblocked edges ($s$ can be seen as the speed of the robber). Both parts have complete knowledge of the opponent's moves and the cops win when they occupy all edges incident to the robbers position. We introduce the capture cost on $G$ against a robber of speed $s$. This defines a hierarchy of invariants, namely $\delta^{1}_{\rm e},\delta^{2}_{\rm e},\ldots,\delta^{\infty}_{\rm e}$, where $\delta^{\infty}_{\rm e}$ is an edge-analogue of the admissibility graph invariant, namely the {\em edge-admissibility} of a graph. We prove that the problem asking wether $\delta^{s}_{\rm e}(G)\leq k$, is polynomially solvable when $s\in \{1,2,\infty\}$ while, otherwise, it is {\sf NP}-complete. Our main result is a structural theorem for graphs of bounded edge-admissibility. We prove that every graph of edge-admissibility at most $k$ can be constructed using $(\leq k)$-edge-sums, starting from graphs whose all vertices, except possibly from one, have degree at most $k$. Our structural result is approximately tight in the sense that graphs generated by this construction always have edge-admissibility at most $2k-1$. Our proofs are based on a precise structural characterization of the graphs that do not contain $\theta_{r}$ as an immersion, where $\theta_{r}$ is the graph on two vertices and $r$ parallel edges.
Document type :
Journal articles
Complete list of metadatas
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, November 20, 2020 - 12:35:00 PM
Last modification on : Wednesday, January 20, 2021 - 3:25:24 PM


Files produced by the author(s)



Stratis Limnios, Christophe Paul, Joanny Perret, Dimitrios M. Thilikos. Edge degeneracy: Algorithmic and structural results. Theoretical Computer Science, Elsevier, 2020, 839, pp.164-175. ⟨10.1016/j.tcs.2020.06.006⟩. ⟨hal-03001062⟩



Record views


Files downloads