Graph widths measured differently on one explicit graph example
Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width
Databases
Summary
The paper studies different ways to measure how complicated a graph is by looking at several types of 'widths.' The authors present one specific graph with 32 points where all these width measurements are different from each other. They calculate these widths exactly or provide close bounds for them. The paper uses known mathematical inequalities and creates examples to prove their findings.
What this means in practice
- •For graph algorithm designers: Choose the best graph width measure to optimize algorithms based on revealing their differences through one explicit example.
- •For information theorists: Assess limits of entropic inequalities in graph-related problems by examining explicit bounds on entropic width of a graph.
A theory result. No direct application yet.
Authors
Matthias Lanzinger, Timo Camillo Merkl, Dan Suciu
Abstract
We describe one explicit simple graph G on 32 vertices whose adaptive, normal, linear, entropic, and submodular widths are pairwise distinct. We compute all these widths exactly, except for the entropic width, where we only give a lower and upper bound. We use Ingleton's inequality and the Zhang-Yeung inequality for upper bounds, and give explicit constructions of modular, normal, linear, entropic, and non-entropic polymatroids for lower bounds.