More Like this

1. Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries

   https://doi.org/10.4230/lipics.swat.2026.24  

   Kaudan, Chirag; Nayyeri, Amir (June 2026, SWAT 2026: Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Fraigniaud, Pierre (Ed.)

   Abstract: Eppstein, Goodrich, and Liu [ESA 2025] introduced a new graph parameter, called BFS-width, and gave polylogarithmic bounds on it for bounded bandwidth graphs. Their bounds naturally imply several applications, e.g. in graph reconstruction via shortest path distance queries, graph drawing, and matrix reordering. We study this parameter for a broader class of graphs, namely bounded cutwidth graphs. We prove a sublinear upper bound on the BFS-width of bounded cutwidth graphs and show that our bounds are asymptotically tight. Our upper bound implies the first deterministic algorithm for reconstructing a bounded cutwidth graph with a subquadratic number of shortest path distance queries. 

   more » « less
2. Sampling Random Chordal Graphs by MCMC (Student Abstract)

   https://doi.org/10.1609/aaai.v34i10.7237  

   Sun, Wenbo; Bezáková, Ivona (June 2020, Proceedings of the AAAI Conference on Artificial Intelligence)

   Chordal graphs are a widely studied graph class, with applications in several areas of computer science, including structural learning of Bayesian networks. Many problems that are hard on general graphs become solvable on chordal graphs. The random generation of instances of chordal graphs for testing these algorithms is often required. Nevertheless, there are only few known algorithms that generate random chordal graphs, and, as far as we know, none of them generate chordal graphs uniformly at random (where each chordal graph appears with equal probability). In this paper we propose a Markov chain Monte Carlo (MCMC) method to sample connected chordal graphs uniformly at random. Additionally, we propose a Markov chain that generates connected chordal graphs with a bounded treewidth uniformly at random. Bounding the treewidth parameter (which bounds the largest clique) has direct implications on the running time of various algorithms on chordal graphs. For each of the proposed Markov chains we prove that they are ergodic and therefore converge to the uniform distribution. Finally, as initial evidence that the Markov chains have the potential to mix rapidly, we prove that the chain on graphs with bounded treewidth mixes rapidly for trees (chordal graphs with treewidth bound of one). 

   more » « less
3. Induced Subgraphs and Tree Decompositions IV. (Even Hole, Diamond, Pyramid)-Free Graphs

   https://doi.org/10.37236/11623  

   Abrishami, Tara; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie (April 2023, The Electronic Journal of Combinatorics)

   A hole in a graph $$G$$ is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph $$K_4$$ by removing an edge. A pyramid is a graph consisting of a vertex $$a$$ called the apex and a triangle $$\{b_1, b_2, b_3\}$$ called the base, and three paths $$P_i$$ from $$a$$ to $$b_i$$ for $$1 \leq i \leq 3$$, all of length at least one, such that for $$i \neq j$$, the only edge between $$P_i \setminus \{a\}$$ and $$P_j \setminus \{a\}$$ is $$b_ib_j$$, and at most one of $$P_1$$, $$P_2$$, and $$P_3$$ has length exactly one. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-free if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. Cameron, da Silva, Huang, and Vušković proved that (even hole, triangle)-free graphs have treewidth at most five, which motivates studying the treewidth of even-hole-free graphs of larger clique number. Sintiari and Trotignon provided a construction of (even hole, pyramid, $$K_4$$)-free graphs of arbitrarily large treewidth. Here, we show that for every $$t$$, (even hole, pyramid, diamond, $$K_t$$)-free graphs have bounded treewidth. The graphs constructed by Sintiari and Trotignon contain diamonds, so our result is sharp in the sense that it is false if we do not exclude diamonds. Our main result is in fact more general, that treewidth is bounded in graphs excluding certain wheels and three-path-configurations, diamonds, and a fixed complete graph. The proof uses “non-crossing decompositions” methods similar to those in previous papers in this series. In previous papers, however, bounded degree was a necessary condition to prove bounded treewidth. The result of this paper is the first to use the method of “non-crossing decompositions” to prove bounded treewidth in a graph class of unbounded maximum degree. 

   more » « less
4. Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs

   https://doi.org/10.5802/igt.6  

   Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie (January 2025, Innovations in Graph Theory)

   Given c ∈ N, we say a graph G is c-pinched if G does not contain an induced subgraph consisting of c cycles, all going through a single common vertex and otherwise pairwise disjoint and with no edges between them. What can be said about the structure of c-pinched graphs? For instance, 1-pinched graphs are exactly graphs of treewidth 1. However, bounded treewidth for c > 1 is immediately seen to be a false hope because complete graphs, complete bipartite graphs, subdivided walls and line graphs of subdivided walls are all examples of 2-pinched graphs with arbitrarily large treewidth. There is even a fifth obstruction for larger values of c, discovered by Pohoata and later independently by Davies, consisting of 3-pinched graphs with unbounded treewidth and no large induced subgraph isomorphic to any of the first four obstructions. We fuse the above five examples into a grid-type theorem fully describing the unavoidable induced subgraphs of pinched graphs with large treewidth. More precisely, we prove that for every c ∈ N, a c-pinched graph G has large treewidth if and only if G contains one of the following as an induced subgraph: a large complete graph, a large complete bipartite graph, a subdivision of a large wall, the line graph of a subdivision of a large wall, or a large graph from the Pohoata-Davies construction. Our main result also generalizes to an extension of pinched graphs where the lengths of excluded cycles are lower-bounded. 

   more » « less
5. Totally Δ-Modular Tree Decompositions of Graphic Matrices for Integer Programming

   https://doi.org/10.4230/lipics.wg.2026.33  

   McFarland, Caleb (January 2026, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Goedgebeur, Jan; Rzążewski, Paweł (Ed.)

   We introduce the tree-decomposition-based parameter totally Δ-modular treewidth (TDM-treewidth) for matrices with two nonzero entries per row. We show how to solve integer programs whose matrices have bounded TDM-treewidth in polynomial time when variables have bounded domain. This extends previous graph-based decomposition parameters for matrices with at most two nonzero entries per row to include matrices with entries outside of {-1,0,1}. We also give an analogue of the Grid Theorem of Robertson and Seymour for matrices of bounded TDM-treewidth in the language of rooted signed graphs. 

   more » « less