CS Paper Radar

Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width

Matthias Lanzinger, Timo Camillo Merkl, Dan Suciu

cs.DB math.CO ·submitted 2026-09-30 15:56 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.60
Abstract · Accepted at ISAAC 2026

To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

0.29

Entanglement Geometry Beyond Polygons: Graph-Theoretic Entanglement Inequalities

cs.IT quant-phmath-ph ·2026-11-18 ·Masoud Gharahi
theory similarity 0.59
Abstract · 29 pages, 3 figures, comments are welcome

Entanglement entropies of pure multipartite states can be constrained by organizing subsystem cuts as edges (hyperedges) of graphs (hypergraphs). Starting from the one-party entanglement polygon inequality, we derive these constraints from strong subadditivity and pure-state complementarity, with optimal coefficients and explicit equality conditions. Our central result determines, for a distinguished two-party cut and an arbitrary weighted family of cuts, the optimal polygon coefficient: the smallest total weight of the cuts separating a member of the distinguished pair from a remaining party. A refinement involving three mutual information terms gives the exact minimum of the weighted sum at fixed entropies of the two parties and of their union, attained by at most three independent bipartite pure states. This criterion recovers the cycle and complete-graph inequalities and shows that uniform incidence parity, which we prove sufficient for polygon inequalities on hypergraphs, is not necessary. Averaging strong subadditivity over both sides of a bipartition gives a sharp $k$-marginal inequality with coefficient $2\binom{n-2}{k-1}$, and we determine uniformly optimal coefficients for collective hyperstar inequalities. For paths and overlapping hyperchains, the deficits are exact sums of conditional mutual information terms; genuinely multipartite entangled cluster states saturate the hyperchain inequality while the chain inequality remains strict. We characterize pure chain equality states, bound the trace distance to cycle equality states independently of the number of parties and local dimensions, and obtain bond-dimension bounds for matrix product states and sequential-recovery error estimates.

0.47

Metric Dimension Parameterized by Bag-Connected Treewidth and Bag-Connected Pathwidth

cs.CC ·2026-11-06 ·Dibyayan Chakraborty, Sebastian Ordyniak, Sebastian Siebertz
theory similarity 0.58
Abstract

The metric dimension of a graph is the minimum size of a set of vertices whose distance vectors distinguish all vertices of the graph. We prove that \MetricDimension{} is NP-complete on planar graphs of treewidth and bag-connected treewidth exactly three. The graphs in our construction have no induced cycle longer than four and have (prefix-connected) pathwidth at most four. In particular, the problem admits no XP algorithm parameterized by bag-connected treewidth unless $\mathrm P=\mathrm{NP}$. This answers questions of Bonnet and Purohit and of Bousquet, Deschamps, and Parreau. We prove that the problem is fixed-parameter tractable when parameterized by bag-connected pathwidth.

0.17

On the Maximum Number of Vertices that Belong to Every Metric Basis

cs.DM math.CO ·2026-08-25 ·Anni Hakanen, Ville Junnila, Tero Laihonen, Havu Miikonen, Ismael G. Yero
published similarity 0.58
Abstract · 19 pages, 8 figures. Parts of this paper appeared in CALDAM 2025

Metric bases of graphs have been widely studied since their introduction in the 1970's by Slater and, independently, by Harary and Melter. In this paper, we concentrate on the existence of vertices in a graph $G$ that belong to all metric bases of $G$. We call these basis forced vertices, and denote the number of them by $\mathrm{bf}(G)$. We show that $\mathrm{bf}(G)\le 2/3(n-k-1)$ for any connected nontrivial graph $G$ of order $n$ having $k$ vertices in each metric basis. In addition, we show that this bound can be attained. Furthermore, the previous result implies the bound $\mathrm{bf}(G)\le 2/5(n-1)$ formulated in terms of the order $n$ of the graph for any nontrivial connected graph $G$. This result answers a question posed by Bagheri et al. in 2016. Moreover, we provide a complete realization of the parameters $n$, $\dim(G)$ and $\mathrm{bf}(G) \ge 1$ within the previous bounds. We consider some extremal cases related to basis forced vertices in a graph, in particular, we give a full characterization of the graphs with $\mathrm{bf}(G) = 2$ and $\dim(G) = n-4$.

0.37

Pairwise Compatibility Graphs of Unweighted Caterpillars

cs.DM math.CO ·2026-10-10 ·Cyriac Antony, Manuel Lafond, Angelo Monti, Blerina Sinaimeri
similarity 0.58
Abstract

In this paper we study pairwise compatibility graphs whose witness tree is required to be an unweighted caterpillar. This is a natural restriction of PCGs, in the same line of research as the study of star witnesses, which led to the class of double-threshold graphs. In the caterpillar case, we show that this restriction is equivalent to a one-dimensional difference-labelling problem: a graph admits such a representation if and only if its vertices can be assigned integer labels so that adjacency is determined exactly by whether the absolute difference of two labels belongs to a given interval. Using this characterization, we derive structural properties of the class, including bounded twin-width, and study its relation with familiar graph families. We show that the class contains cycles and two-dimensional grids, while it excludes natural obstructions such as the subdivided star $S_{2,2,2,2,2}$, the cube graph $Q_3$, the wheel $W_6$, and the complement of the $3$-sunlet. We also consider restricted representations, including centipede witnesses and representations with a given interval and we give a polynomial-time recognition algorithm when the interval is fixed.

0.31

An improved bound on the treewidth of planar graphs excluding a grid minor

cs.DM math.CO ·2026-09-14 ·Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret, Robin Petit, Jean-Florent Raymond +1 more
similarity 0.58
Abstract

We show that every planar graph with no $t \times t$ grid minor has treewidth at most $4t +4$. This improves on the previously best known bound of $\frac{9}{2}t - \frac{11}{2}$, due to Gu and Tamaki (2012), and is within a factor $2$ of optimal. A key step in the proof is showing the following result, which might be of independent interest: Every $2$-connected plane graph $G$ with radius $d$ and faces of size at most $k$ has a tree-decomposition of width at most $\max\{3d+ k+5, 2d+2k+1\}$ such that the vertex set of every face of $G$ is contained in some bag.

0.41

Asymptotic dimension of graphs excluding an induced or fat minor

cs.DM math.CO ·2026-10-15 ·Robert Hickingbotham, Freddie Illingworth, Piotr Micek, Bartosz Walczak
theory similarity 0.57
Abstract

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed graph $H$, the class of graphs excluding $H$ as a fat minor has bounded asymptotic dimension. A weaker conjecture asserts the same conclusion for graphs excluding $H$ as an induced minor. We substantially expand the range of graphs $H$ for which these conjectures are known to hold. Specifically, we prove bounded asymptotic dimension for the following classes of graphs: graphs excluding a fixed planar graph as a fat minor; and graphs excluding a fixed string graph as an induced minor. All of our results also hold for the stronger notion of Assouad--Nagata dimension, a refinement of asymptotic dimension. These results have a number of applications, two of which we mention here. First they imply that an induced minor-closed class is $χ$-bounded if and only if it does not contain some Burling graph. Second they imply that, in graph classes excluding a fixed planar graph as an induced minor, treewidth is polynomial in maximum degree.

0.24

Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers

cs.DM math.CO ·2026-10-10 ·Yusuke Watanabe
theorycode/data similarity 0.57
Abstract · 39 pages. Main Theorems A-C formalized in Lean 4; code: https://github.com/ywatanabex/coefficientwise-rigidity-lean

Let $G$ be a finite bipartite graph and let $\widetilde G$ be an $M$-fold cover. We compare independent sets of $\widetilde G$ with those of the trivial cover, consisting of $M$ disjoint copies of $G$, after prescribing how many vertices are selected above each vertex of $G$. A conjecture from 2011, motivated by the Bethe approximation, asserts that the trivial cover maximizes every such count. We prove this for every feasible occupation profile whose active graph has treewidth at most two or is chordal bipartite. Equality holds exactly when the restricted cover is flat, meaning that fibre relabelings make it trivial. For $M\ge2$ and positive feasible occupations, a nonflat cover of a connected bipartite graph of treewidth at most two has a deficit of at least twice the coefficient of $p_G^{M-2}$ with every occupation reduced by one. A holonomy-dependent bound improves the factor to three for odd-order holonomy; both uniform constants are sharp. Comparison and rigidity survive finite compositions along an edge or a vertex, and quantitative bounds from one piece propagate to the whole graph, giving results beyond the two original classes. On any bipartite base, the first nonzero homogeneous defect is determined by the shortest cycles with nontrivial holonomy. At singleton occupations, our counts are numbers of DP-colorings of full covers. The dual DP color function on these classes and their finite seam compositions equals the chromatic polynomial, with equality attained precisely by canonical labelings. Dong's chromatic-polynomial inequality then yields the Dual-DP Shameful inequality on the same graph class. The main theorems have been formalized in Lean 4.

0.28