Induced packing branchwidth links graph structures and decompositions

Induced packing treewidth III. Branch decompositions

Discrete Mathematics

Summary

This work studies a new way to measure structural complexity in networks called induced packing branchwidth. The authors connect this measure to existing concepts that describe how graphs can be broken into simpler pieces while avoiding certain patterns. They also show how graphs with small values of this measure have useful properties, like constraints on colorings and distances. This helps unify different approaches to understanding complicated networks.

What this means in practice

  • For network algorithm designers: Optimize algorithms by using graph decompositions based on induced packing branchwidth to handle special graph classes more effectively.
  • For database indexing teams: Develop query optimization strategies that exploit structural graph decompositions to improve processing of complex relational data.

A theory result. No direct application yet.

Authors

Amir Nikabadi, Paweł Rzążewski

Abstract

The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. In this paper, we introduce induced packing branchwidth, a branch-decomposition analogue of induced packing treewidth. For a graph $H$, the induced $H$-packing branchwidth of a graph $G$, denoted by $\branchpi_H(G)$, is the minimum, over all branch decompositions of $G$, of the largest number of pairwise anticomplete induced copies of $H$ that cross one displayed cut. For $H=P_2$, it equals sim-width. We prove several structural properties of graphs of bounded $\branchpi_H$, for various choices of $H$, including $χ$-boundedness, polynomial degree-boundedness, and metric properties.