Edge degeneracy: algorithmic and structural results

DOI10.1016/J.TCS.2020.06.006MaRDI QIDQ2196572zbMATH OpenOpenAlexFDO

Authors Stratis Limnios, Christophe Paul, Joanny Perret, Dimitrios M. Thilikos

Publication date 3 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.03809

zbMATH Keywords

cops and robber gamesgraph admissibilitygraph decomposition theoremsgraph degeneracygraph searching

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

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 $delt{a}_{me}^1,delt{a}_{me}^2,ldots,delt{a}_{me}^{infty}$, where $delt{a}_{me}^{infty}$ is an edge-analogue of the admissibility graph invariant, namely the {em edge-admissibility} of a graph. We prove that the problem asking wether $delt{a}_{me}^s(G)leqk$, is polynomially solvable when $sin1,2,infty$ while, otherwise, it is 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 $(leqk)$-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 $het{a}_r$ as an immersion, where $het{a}_r$ is the graph on two vertices and $r$ parallel edges.

Recommendations

• Cops and robbers playing on edges
• Edge-critical cops and robber in planar graphs
• A game of cops and robbers
• The cops and robber game on graphs with forbidden (induced) subgraphs
• Pursuing a fast robber on a graph

Cites work

• A note on forbidding clique immersions
• An annotated bibliography on guaranteed graph searching
• Colouring and covering nowhere dense graphs
• Constant-factor approximation of the domination number in sparse graphs
• Contraction and Treewidth Lower Bounds
• Forbidding Kuratowski graphs as immersions
• Fraternal augmentations, arrangeability and linear Ramsey numbers
• Graphs with linearly bounded Ramsey numbers
• scientific article; zbMATH DE number 431513 (Why is no real title available?)
• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 1151792 (Why is no real title available?)
• Length-Bounded Cuts and Flows
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Multi-Terminal Network Flows
• On the block number of graphs
• Profiles of separations: in graphs, matroids, and beyond
• Searching and sweeping graphs: a brief survey
• Searching for a Visible, Lazy Fugitive
• Sparsity. Graphs, structures, and algorithms
• The complexity of finding maximum disjoint paths with length constraints
• The Linkage of a Graph
• The structure of graphs not admitting a fixed immersion
• The theory of search games and rendezvous.

Cited in

(2)

• A constant-factor approximation for weighted bond cover
• An overview of universal obstructions for graph parameters

This page was built for publication: Edge degeneracy: algorithmic and structural results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196572)