Annotated graph parameters unified by torsos simplify structural analysis
Invitation to torso parameters of annotated graphs
Discrete Mathematics
Summary
Many problems in computer science can be understood by studying graphs, which are like networks of points connected by lines. Sometimes, certain points are marked as special, and analyzing these marked networks is tricky. The authors introduce a new way to look at these marked points by focusing on smaller, simpler parts of the graph called torsos. This lets them define and study many network measurements in a unified way and connect these measurements to known graph properties and classes. They also explore some new theoretical connections and suggest future research directions.
What this means in practice
- •For network algorithm designers: Use torso-based parameters to design algorithms that handle graphs with important vertex subsets in routing or optimization problems.
- •For software engineers working on graph analytics: Incorporate torso parameter insights to improve preprocessing and structural decomposition of graphs with highlighted vertex sets for more efficient computations.
A theory result. No direct application yet.
Authors
Maël Dumas, Jędrzej Hodor, Tomasz Mazur, Piotr Micek, Clément Rambaud, Giannos Stamoulis
Abstract
An annotated graph is a pair $(G,S)$, where $G$ is a graph and $S$ is a subset of vertices of $G$. We present a unified approach for definitions of annotated versions of classical graph parameters such as treewidth, pathwidth, treedepth, etc. A generic way to incorporate a distinguished set of vertices into a graph parameter is via torsos. Given a graph $G$ and a subset $S'\subseteq V(G)$, we define $\mathrm{torso}_G(S')$ to be the graph with vertex set $S'$ in which distinct vertices $u,v\in S'$ are adjacent if and only if there exists a $u$-$v$ path in $G$ whose internal vertices lie outside $S'$. Now let $\mathrm{p}$ be any graph parameter. For an annotated graph $(G,S)$, we define the torso $\mathrm{p}$ of $(G,S)$ by \[\mathrm{p}(G,S) = \min\{\mathrm{p}(\mathrm{torso}_G(S')) \mid S \subset S' \subset V(G)\}.\] For a minor-closed class of annotated graphs $\mathcal{C}$, we discuss equivalent conditions for $\mathrm{p}(G,S)$ bounded for all $(G,S)\in\mathcal{C}$ in terms of annotated graphs excluded in $\mathcal{C}$. In many cases, we collect known results from the literature. We include two new arguments for $\mathrm{p}$ being the $2$-treedepth and the feedback vertex number. Among other statements, we also include a variant of the Erdős-Pósa property for annotated cycles. We propose some new research directions.