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

Kaudan, Chirag; Nayyeri, Amir

doi:10.4230/LIPIcs.SWAT.2026.24

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

Chirag Kaudan

Oregon State University, Corvallis, OR, USA Amir Nayyeri

Oregon State University, Corvallis, OR, USA

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.

Keywords and phrases:

Graph algorithms, graph theory, cutwidth, pathwidth, BFS-width

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Shortest paths

Funding:

The authors were supported by NSF grants CCF-1941086 and CCF-2311180.

DOI:

10.4230/LIPIcs.SWAT.2026.24

Event:

20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Editor:

Pierre Fraigniaud

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Recently, Eppstein, Goodrich, and Liu [13] introduced the parameter BFS-width of a graph, defined as the maximum cardinality of a layer over all breadth-first search trees of the graph. More formally, for an undirected graph $G=(V,E)$ , and any vertex $v\in V$ , the $\operatorname{bfsw}(G,v)$ is the maximum number of vertices that are at the same distance from $v$ , i.e. $\max_{i\geq 0}{|L_{i}(v)|}$ , where $L_{i}(v)$ is the set of all vertices at distance $i$ of $v$ . In turn, the BFS-width of the graph is defined as $\operatorname{bfsw}(G)=\max_{v\in V}(\operatorname{bfsw}(G,v))$ .

BFS-width is a natural parameter to study, as the width of a breadth-first search tree plays a central role in many graph algorithms, for example in the computation of small separators. Eppstein, Goodrich, and Liu study BFS-width in relation to bandwidth, a parameter whose exact computation is NP-hard [14, 15], and show polylogarithmic upper and lower bounds on the BFS-width of bounded bandwidth graphs. Consequently, simple BFS-based algorithms perform well on bounded-bandwidth graphs for a variety of tasks. Specifically, Eppstein, Goodrich, and Liu show applications in analysis of the Cuthill-McKee algorithm, graph drawing, and graph reconstruction from shortest-path distance queries.

Motivated both by this theoretical perspective and by the analysis of simple BFS-based algorithms, we investigate whether there exist families of graphs beyond bounded bandwidth that admit sublinear BFS-width.

Overview of Results

Cutwidth vs. BFS Width

The next natural family to consider is bounded cutwidth graphs. Our primary result shows that such graphs have sublinear BFS-width, although the width may still be polynomially large. Specifically, we prove that

\operatorname{bfsw}(G)=O\Big((\operatorname{cw}(G))^{2}\cdot n^{1-\epsilon(% \operatorname{cw}(G))}\Big),

where $\epsilon(x)=2^{-(2x+1)}$ , and $\operatorname{cw}(G)$ denotes the cutwidth of $G$ (see Theorem 7).

Moreover, we show a nearly matching lower bound by constructing an infinite family of trees such that for every tree $T$ in the family with $n$ vertices,

\operatorname{bfsw}(T)=\Omega\Big(\frac{1}{\operatorname{cw}(T)}\cdot n^{1-% \epsilon\big(\frac{\operatorname{cw}(T)}{2}-1\big)}\Big).

(see Theorem 4)

Our upper bound can be stated more generally in terms of pathwidth and maximum degree. Specifically, we prove that

\operatorname{bfsw}(G)=O\big(\Delta(G)^{2}\cdot n^{1-\epsilon(\operatorname{pw% }(G))}\big),

where $\operatorname{pw}(G)$ and $\Delta(G)$ denote the pathwidth and maximum degree of $G$ , respectively. Since bounded degree together with bounded pathwidth implies bounded cutwidth (and vice versa up to constant factors), this formulation decouples the dependence on $\Delta(G)$ and $\operatorname{pw}(G)$ and is therefore more general. Our lower bound can similarly be expressed in terms of pathwidth.

We note that a bound on the maximum degree is necessary to obtain sublinear BFS-width. For example, a star has linear BFS-width. In particular, bounded pathwidth graphs with unbounded maximum degree may have linear BFS-width. Furthermore, even among bounded-degree trees, linear BFS-width is possible: a binary tree may have more than half of its vertices in its last layer, and therefore linear BFS-width. Thus, the family of bounded-degree trees does not, by itself, guarantee sublinear BFS-width. Hence, it appears that extending beyond bounded cutwidth – e.g., to bounded pathwidth graphs or to bounded-degree graphs of bounded treewidth – breaks the guarantee of sublinear BFS-width.

Finally, since $\operatorname{bw}(G)\leq 2\operatorname{bfsw}(G)$ , as shown by Eppstein, Goodrich, and Liu, our result implies a sublinear bound on the bandwidth of bounded-cutwidth graphs. In particular,

\operatorname{bw}(G)=O\Big((\operatorname{cw}(G))^{2}\cdot n^{1-\epsilon(% \operatorname{cw}(G))}\Big).

Graph Reconstruction

We apply our results to the hidden graph reconstruction problem, which asks to reconstruct a graph which has an invisible edge set using queries to an oracle that returns some information about the graph e.g. a shortest path between a pair of vertices. In this paper, the query model we consider is the shortest path distance model, which returns the shortest path length between the queried pair of vertices. We assume that graphs are connected for the graph reconstruction problem with shortest path distance queries, as there are disconnected graphs which require $\Omega(n^{2})$ queries to reconstruct.

A simple, natural algorithm for graph reconstruction with shortest path distance queries first constructs breadth-first search layers and then simply queries all possible edges, which we know must lie between vertices in the same or consecutive BFS layers. That is, the algorithm simply queries all pairs of vertices that lie in BFS layers at most one apart. Of course, if the BFS-width of an $n$ vertex graph is $\Omega(n)$ , then this algorithm must make $\Omega(n^{2})$ queries to reconstruct it. Conversely, if the graph has sublinear BFS-width then we obtain a subquadratic query reconstruction algorithm, improving on the trivial $\Theta(n^{2})$ query algorithm which simply queries all pairs of vertices. Eppstein, Goodrich, and Liu show that this algorithm based on BFS layers makes nearly linear queries to reconstruct any bounded bandwidth graph.

We show that this algorithm makes a subquadratic number of queries for bounded cutwidth graphs, specifically, $O(\operatorname{cw}(G)^{2}n^{2-\frac{1}{2^{2\operatorname{cw}(G)+1}}})$ queries for any graph $G$ on $n$ vertices and cutwidth $\operatorname{cw}(G)$ (see Theorem 10). Our result is the first subquadratic deterministic algorithm to reconstruct bounded cutwidth graphs to the best of our knowledge. A randomized algorithm with $\widetilde{O}(n^{3/2})$ queries to reconstruct bounded degree graphs was known before [18, 21].

2 Background

In this section, we first briefly review the basic definitions and notation used throughout the paper. We then provide a more detailed overview of graph width parameters, as they are the central subject of study in the paper.

2.1 Basic Definitions and Notation

In this paper, all graphs are unweighted. For a graph $G=(V,E)$ , we use $|V(G)|$ to refer to the cardinality of the vertex set of $G$ . We refer to this quantity $|V(G)|$ as the order of $G$ and the quantity $|E(G)|$ as the size of $G$ . For a vertex $v\in V(G)$ , we use $N_{G}(v)$ to denote the set of all neighbors of $v$ in the graph $G$ and $N_{G}[v]$ = $N_{G}(v)\cup\{v\}$ , the open and closed neighborhood of $v$ respectively. Analogously, for a graph $G=(V,E)$ and a set $S\subseteq V(G)$ , we let $N_{G}[S]=\{u\in V(G)\mid\exists a\in S,d_{G}(a,u)\leq 1\}$ and $N_{G}(S)=N_{G}[S]\setminus S$ be the closed neighborhood and open neighborhood of $S$ in $G$ respectively where $d_{G}(x,y)$ is the shortest path distance between vertices $x$ and $y$ in $G$ . For a graph $G$ , we let $\Delta(G)$ denote the maximum degree of $G$ . For a subset $S\subseteq V(G)$ of a graph $G$ , we denote the subgraph of $G$ induced by $S$ with $G[S]$ .

For any non-trivial tree $T$ , we define $\ell(T)$ as the number of leaves in $T$ . For the trivial tree $T_{1}$ on one vertex, we explicitly define $\ell(T_{1})=1$ , despite $T_{1}$ having no leaves. We define a uniform depth tree as a rooted tree in which every leaf has the same distance from the root.

For any vector $x=(x_{1},x_{2},\dots,x_{n})\in\mathbb{R}^{n}$ and any real $p\geq 1$ , we use $\|x\|_{p}$ to denote the $p$ -norm of $x$ : $\|x\|_{p}=(\sum_{i=1}^{n}|x_{i}|^{p})^{1/p}$ .

We refer to the binary tree of height $k$ with $2^{k+1}-1$ vertices as a full binary tree of height $k$ .

2.2 Preliminaries on Width Parameters and Strahler Numbers

We formally define the graph width parameters bandwidth, pathwidth, and cutwidth, show some of the well-known relationships between them, and define the Strahler number, a well-studied graph parameter for directed rooted trees (arborescences) which we will use to develop our results.

A linear layout, or layout, of an undirected graph $G$ with $n=|V(G)|$ is a bijection $\phi:V(G)\to[n]=\{1,2,\dots,n\}$ . The length of an edge $uv\in E(G)$ in a layout $\phi$ of $G$ is $|\phi(u)-\phi(v)|$ . The bandwidth of $\phi$ , denoted $\operatorname{bw}(\phi)$ , is the maximum length of any edge $uv\in E(G)$ . The bandwidth $\operatorname{bw}(G)$ of graph $G$ is the minimum bandwidth over all bijections $\varphi:V(G)\to[n]$ . The notion of bandwidth is equivalent to finding the length of the longest edge on a linear layout of the graph on a number line that minimizes the longest edge length.

Given an undirected graph $G=(V,E)$ , a layout $\phi$ of $G$ , and an integer $i$ , the edge cut of $\phi$ at position $i$ , denoted $\theta(i,\phi,G)$ , is defined $\theta(i,\phi,G)=|\{uv\in E(G)\mid u\in\{x\in V(G)\mid\phi(x)\leq i\}\land v% \in\{x\in V(G)\mid\phi(x)>i\}\}|$ . That is, if we imagine a layout $\phi$ of $G$ as an ordering of the vertices on a number line, the edge cut of $\phi$ at position $i$ is the number of edges of $G$ crossing the vertical line between vertex $i$ and $i+1$ . The maximum edge cut of $\phi$ , denoted $\Theta(\phi,G)$ , is the maximum value of $\theta(i,\phi,G)$ over all $i$ . The cutwidth $\operatorname{cw}(G)$ of graph $G$ is the minimum value of $\Theta(\phi,G)$ over all bijections $\phi:V(G)\to[n]$ . We will use the informal terms “left” and “right” of an edge cut of layout $\phi$ of $G$ at position $i$ to refer to the sets $\{x\in V(G)\mid\phi(x)\leq i\}$ and $\{x\in V(G)\mid\phi(x)>i\}$ respectively, viewing the layout as embedding the graph on a number line. We specifically note that both of the graph classes bounded cutwidth and bounded pathwidth are monotone graph classes i.e. they are closed under taking any subgraph (in particular, not merely induced subgraphs).

A path decomposition of $G=(V,E)$ is a sequence of subsets of $V(G)$ , called bags, such that each edge of $G$ is contained in a bag and each vertex appears in some contiguous subsequence of the bags. The width of a path decomposition $(V_{i})_{i\geq 1}$ of $G$ is $\max_{i}|V_{i}|-1$ and the pathwidth of undirected graph $G$ , denoted $\operatorname{pw}(G)$ , is the minimum width over any path decomposition of $G$ .

The Strahler number, also called the Horton-Strahler number, of a rooted, directed tree $T$ is given by the following recursive definition.

Definition 1.

Let $T$ be a rooted, directed tree. The Strahler number of a vertex $x\in V(T)$ , denoted $\nu(x)$ , is defined recursively below.

\nu(x)=\begin{cases}1,&\text{if $x$ is a leaf},\\[4.0pt] 1+k,&\begin{aligned} &\text{if $x$ has at least 2 distinct children, each with% Strahler number}\\ &k=\max_{x_{i}\in\operatorname{Ch}(x)}\{\nu(x_{i})\}\end{aligned}\\[2.0pt] \max\limits_{x_{i}\in\operatorname{Ch}(x)}\{\nu(x_{i})\},&\text{otherwise}.% \end{cases}

where $\operatorname{Ch}(v)$ denotes the set of children of a vertex in $T$ . Note that the Strahler number of any vertex must be a positive integer. The Strahler number of a rooted, directed tree $T$ is the Strahler number of its root, denoted $\nu(T)$ .

For technical convenience, we also define a modified notion of the Strahler number called the $t$ -shifted Strahler number which retains the recursive definition of the Strahler number but assigns $t$ to each leaf instead of $1$ as the base case, for some positive integer $t$ .

Definition 2.

Let $T$ be a rooted, directed tree. The t-shifted Strahler number of a vertex $x\in V(T)$ , denoted $\nu_{t}(x)$ , is defined recursively below.
$\nu_{t}(x)=\begin{cases}t,&\text{if $x$ is a leaf},\\[4.0pt] 1+k,&\begin{aligned} &\text{if $x$ has at least 2 distinct children, each with% Strahler number}\\ &k=\max_{x_{i}\in\operatorname{Ch}(x)}\{\nu_{t}(x_{i})\}\end{aligned}\\[2.0pt] \max\limits_{x_{i}\in\operatorname{Ch}(x)}\{\nu_{t}(x_{i})\},&\text{otherwise}% .\end{cases}$

where $\operatorname{Ch}(v)$ denotes the set of children of a vertex in $T$ . Note that the $t$ -shifted Strahler number of any vertex must be an integer at least $t$ . The $𝐭$ -shifted Strahler number of a rooted, directed tree $T$ is the $t$ -shifted Strahler number of its root, denoted $\nu_{t}(T)$ .

For any directed, rooted tree $T$ , the relationship $\nu_{t}(T)=\nu(T)+t-1$ follows immediately from the definitions of Strahler number and $t$ -shifted Strahler number, hence the name.

We briefly discuss some of the many known relationships between these graph parameters. Firstly, note that bounded bandwidth implies bounded maximum degree and also implies bounded pathwidth, but bounded pathwidth does not imply bounded degree e.g. the star graph $K_{1,n-1}$ on $n$ vertices has pathwidth $1$ . That bounded bandwidth implies bounded pathwidth can be seen via the following alternate definition of pathwidth: The pathwidth of $G$ can also be seen as a layout parameter, called the vertex separation number, defined nearly identically to cutwidth but defined in terms of number of vertices with neighbors across a cut rather than number of edges crossing a cut [8, 12].

This alternate definition of pathwidth as the vertex separation number yields the inequality $\operatorname{pw}(G)\leq\operatorname{cw}(G)\leq\Delta\operatorname{pw}(G)$ for any graph $G$ with maximum degree $\Delta$ . Also, $\operatorname{cw}(G)\leq\Delta(G)\operatorname{bw}(G)$ for any graph $G$ [10].

Furthermore, bounded BFS-width implies bounded bandwidth [13]. This can be seen by taking the linear ordering of a graph $G$ induced by the breadth-first search tree that realizes the BFS-width of $G$ and noting that edges of $G$ must lie between vertices in the same or consecutive BFS layers.

In this paper, we need to work with different width parameters of trees as well as their Strahler number. Technically, the Strahler number is defined for directed rooted trees, while the width parameters are defined for undirected trees. Whenever the root is clear from the context, we abuse notation by denoting both of these directed and undirected trees by $T$ . Specifically, we use $\operatorname{pw}(T)$ , $\operatorname{cw}(T)$ , and $\Delta(T)$ for a directed rooted tree $T$ , where we mean the pathwidth, cutwidth and the maximum degree of the underlying undirected tree in order.

In this case, the inequality $\operatorname{pw}(T)\leq\nu(T)\leq 2\operatorname{pw}(T)+2$ holds [20]. The following lemma summarizes some of the most important inequalities for our purposes that were discussed above.

Lemma 3.

For a directed rooted tree $T$ with maximum degree $\Delta$ , we have

\frac{\operatorname{cw}(T)}{\Delta(T)}\leq\operatorname{pw}(T)\leq\nu(T)\leq 2% \operatorname{pw}(T)+2\leq 2\operatorname{cw}(T)+2

3 Lower Bound Construction

In this section, we prove the following theorem.

Theorem 4.

For any $\nu\geq 2$ , there exists an infinite family of (uniform depth) trees $\mathcal{C}_{\nu}$ of Strahler number $\nu$ and cutwidth and pathwidth at most $\nu$ such that for any $T\in\mathcal{C}_{\nu}$ we have

\operatorname{bfsw}(T)\geq\frac{1}{\nu-1}\cdot|V(T)|^{1-1/2^{\nu-1}}\text{ .}

We explicitly construct the infinite sequences of trees $\mathcal{C}_{\nu}=(C_{\nu,p})_{p\geq\nu}$ (one sequence per each value of $\nu\in\{2,3,\ldots\}$ ) with Strahler number $\nu\geq 2$ . First, we consider the case $\nu=2$ .

Base Case ( $p=2$ ).

The tree $C_{2,2}$ is a rooted full binary tree of height $1$ , i.e. a root with two leaves as children.

Recursive case ( $p>2$ ).

The tree $C_{2,p}$ is the rooted binary tree defined by its left and right subtrees: (1) its left subtree is $C_{2,p-1}$ , and (2) its right subtree is a rooted path of length $p-2$ , i.e. $(u_{1},u_{2},\ldots,u_{p-1})$ with root $u_{1}$ . Let $C_{2,p-1}$ be as defined recursively with root $r_{p-1}$ . One can also view the construction $C_{2,p}$ as introducing $p$ vertices to the graph $C_{2,p-1}$ that form a path of length $p-1$ (as an induced subgraph), of which one endpoint is a leaf of $C_{2,p}$ and the other endpoint is the root of $C_{2,p}$ .

Figure 1: Left: The recursive construction of

C_{2,p}

:

C_{2,2}

,

C_{2,3}

and

C_{2,4}

in order. Right: Layout

L_{2,4}

of

C_{2,4}

, which has cutwidth

2

.

Lemma 5.

For any $p\geq 2$ , $C_{2,p}$ has Strahler number $2$ , cutwidth at most $2$ , $p$ leaves, and $p(p+1)/2$ vertices.

Proof.

We use induction on $p$ . The base case is a tree with three vertices, two leaves, and Strahler number two, which satisfies the statement of the lemma.

Inductively, $C_{2,p}$ is a tree with $\ell(C_{2,p-1})+1$ leaves, and $|V(C_{2,p-1})|+p$ vertices. Solving the recurrence, one obtains $\ell(C_{2,p})=p$ and $|V(C_{2,p})|=p(p+1)/2$ , respectively. In addition, $\nu(C_{2,p-1})=2$ (that is, $\nu(r_{p-1})=2$ ) inductively and the Strahler number of the right subtree of $C_{2,p}$ , which is a path rooted at one of its endpoints, is one. Hence, $\nu(C_{2,p})=2$ and $\operatorname{pw}(C_{2,p})\leq 2$ by Lemma 3.

Finally, we show that $C_{2,p}$ has cutwidth at most two by inductively constructing a layout $L_{2,p}$ of cutwidth two for $C_{2,p}$ , with the additional property that the root is the leftmost vertex in $L_{2,p}$ .

For the base case $p=2$ , let $L_{2,2}$ be any layout of $C_{2,2}$ in which the root is the leftmost vertex. Since the root has degree two, this layout has cutwidth at most two (in fact, the cutwidth of $C_{2,2}$ is one).

For $p>2$ , let $r$ be the root of $C_{2,p}$ . The subtrees of $r$ consist of a copy of $C_{2,p-1}$ with root $r^{\prime}$ and a path $(u_{1},\ldots,u_{p-1})$ , where $u_{1}$ is a child of $r$ . We define $L_{2,p}$ to be the layout

r,u_{1},\ldots,u_{p-1}\circ L_{2,p-1},

where the copy of $L_{2,p-1}$ corresponds to the inductively constructed layout of $C_{2,p-1}$ with $r^{\prime}$ as its leftmost vertex (see Figure 1 right).

Consider any cut in this layout. Any cut occurring before $r^{\prime}$ intersects at most two edges: possibly one edge from the path $r,u_{1},\ldots,u_{p-1}$ , and always the edge connecting $r$ to $r^{\prime}$ .

Any cut occurring after $r^{\prime}$ intersects at most two edges of the copy of $C_{2,p-1}$ by the induction hypothesis, and no additional edges, as all other edges of $C_{2,p}$ are on the left side of $r^{\prime}$ .

Thus every cut contains at most two edges, and therefore $C_{2,p}$ has cutwidth at most two. $\hfill\blacktriangleleft$

Figure 2: The recursive construction of

C_{\nu,p}

. Left:

C_{3,2}

is composed of one copy of

C_{2,4}

and four copies of

C_{2,2}

. Middle: Generally,

C_{\nu,p}

is composed of one copy of

C_{2,p^{2^{\nu-2}}}

and

p^{2^{\nu-2}}

copies of

C_{\nu-1,p}

– Lemma 6 shows that

C_{\nu-1,p}

has

p^{2^{\nu-2}}

leaves. Right:

L_{\nu,p}

construction. Copies of

L_{\nu-1,p}

are recursively embedded next to the leaves in the layout

L_{2,p^{2^{\nu-2}}}

.

Next, we build $\mathcal{C}_{\nu}=(C_{\nu,p})_{p\geq\nu}$ for $\nu\geq 3$ , recursively; see Figure 2, left and middle, for an illustration. To construct $C_{\nu,p}$ , let $T$ be a copy of $C_{2,p^{2^{\nu-2}}}$ , and let $T^{\prime}_{1},\ldots,T^{\prime}_{p^{2^{\nu-2}}}$ be $p^{2^{\nu-2}}$ copies of $C_{\nu-1,p}$ . Now, construct $C_{\nu,p}$ by taking $T$ and identifying its leaves with the roots of $T^{\prime}_{1},\ldots,T^{\prime}_{p^{2^{\nu-2}}}$ .

Lemma 6.

For any $\nu\geq 2$ and any $p\geq\nu$ , $C_{\nu,p}$ has Strahler number $\nu$ , cutwidth at most $\nu$ , $p^{2^{\nu-1}-1}$ leaves, and at most $(\nu-1)p^{2^{\nu-1}}$ vertices.

Proof.

We proceed by induction on the value $\nu$ . The basis step is provided by Lemma 5.

For the inductive step $\nu\geq 3$ , note that for each $i\in\{1,\ldots,p^{2^{\nu-2}}\}$ , $T^{\prime}_{i}$ is a copy of $C_{\nu-1,p}$ . Therefore, by the induction hypothesis, $\nu(T^{\prime}_{i})=\nu-1$ , $\ell(T^{\prime}_{i})=p^{2^{\nu-2}-1}$ , and $|V(T^{\prime}_{i})|\leq(\nu-2)p^{2^{\nu-2}}$ . Also, by Lemma 5,

\ell(T)=p^{2^{\nu-2}}\text{, }|V(T)|=p^{2^{\nu-2}}(p^{2^{\nu-2}}+1)/2\leq p^{2% ^{\nu-1}}\text{, and }\nu(T)=2

Therefore, we have

\ell(C_{\nu,p})=\sum_{i\in[\ell(T)]}{\ell(T^{\prime}_{i})}=\ell(T)\cdot p^{2^{% \nu-2}-1}=p^{2^{\nu-2}}\cdot p^{2^{\nu-2}-1}=p^{2^{\nu-1}-1}.

Moreover, we have

	$\displaystyle\|V(C_{\nu,p})\|$	$\displaystyle=\|V(T)\|+\sum_{i\in[\ell(T)]}\|V(T^{\prime}_{i})\|-\ell(T)$
		$\displaystyle\leq p^{2^{\nu-1}}+p^{2^{\nu-2}}(\nu-2)p^{2^{\nu-2}}-p^{2^{\nu-2}}$
		$\displaystyle\leq p^{2^{\nu-1}}+(\nu-2)p^{2^{\nu-1}}$
		$\displaystyle=(\nu-1)\,p^{2^{\nu-1}}.$

To show that the Strahler number of $C_{\nu,p}$ is $\nu$ , we recall that by construction $C_{\nu,p}$ consists of a copy of $T=C_{2,p^{2^{\nu-2}}}$ and $p^{2^{\nu-2}}$ copies of $C_{\nu-1,p}$ whose roots are identified with the leaves of the copy of $T$ . Let $R$ be the set of vertices of $C_{\nu,p}$ that correspond to these identified roots (i.e. the roots of the $T_{i}$ ’s that were identified with leaves of the copy of $T$ ). By the induction hypothesis, the Strahler number on each vertex of $R$ is $\nu-1$ . Observe then that $\nu(C_{\nu,p})=\nu_{t}(T)$ for $t=\nu-1$ . Further, $\nu(T)=2$ by Lemma 5. It follows then that $\nu(C_{\nu,p})=\nu_{t}(T)=\nu(T)+t-1=2+(\nu-1)-1=\nu$ .

Finally, we show that the cutwidth of $C_{\nu,p}$ is at most $\nu$ by inductively constructing a layout $L_{\nu,p}$ of cutwidth $\nu$ .

The base case $\nu=2$ is shown in Lemma 5. For later use, we note an additional property of the layout $L_{2,p}$ constructed there: any cut that appears immediately after a leaf in the layout has width one. In particular, in the (recursive) layout

r,u_{1},\ldots,u_{p-1}\circ L_{2,p-1},

the cut immediately after $u_{p-1}$ contains exactly one edge, namely $(r,r^{\prime})$ , where $r^{\prime}$ is the root of the copy of $C_{2,p-1}$ . All other cuts immediately following a leaf occur within $L_{2,p-1}$ and therefore have width one within $L_{2,p-1}$ inductively. Moreover, every edge not belonging to the copy of $C_{2,p-1}$ has both endpoints to the left of $r^{\prime}$ in $L_{2,p}$ , so such edges are not crossed by those cuts.

We now construct $L_{\nu,p}$ for $\nu>2$ ; see Figure 2, right, for illustration. The tree $C_{\nu,p}$ consists of a copy $T$ of $C_{2,q}$ together with copies $T^{\prime}_{1},\ldots,T^{\prime}_{q}$ of $C_{\nu-1,t}$ whose roots are identified with the leaves of $C_{2,q}$ , for appropriate values $q$ and $t$ (their exact values are not needed for the remainder of the proof).

To build $L_{\nu,p}$ , start with the layout $L_{2,q}$ . For each leaf $v$ in this layout, insert to its right a copy of $L_{\nu-1,t}$ , and identify the root of that copy with $v$ . Since in $L_{\nu-1,t}$ the root is the leftmost vertex, this identification does not increase the cutwidth of $L_{\nu-1,t}$ .

Consider an arbitrary cut in $L_{\nu,p}$ . Such a cut either: (i) crosses only edges of $L_{2,q}$ , or (ii) crosses one edge of $L_{2,q}$ together with edges from a single copy of $L_{\nu-1,t}$ .

In case (i), the cut has cardinality at most two, since $L_{2,q}$ has cutwidth two. In case (ii), the cut crosses at most one edge from $L_{2,q}$ and, by the inductive hypothesis, at most $\nu-1$ edges from the copy of $L_{\nu-1,t}$ ; hence its total width is at most $\nu$ .

Therefore, $L_{\nu,p}$ has cutwidth at most $\nu$ , completing the proof. $\hfill\blacktriangleleft$

Using the lemmas above, we now provide a proof of Theorem 4.

Proof of Theorem 4.

Let $\mathcal{C}_{\nu}=\{C(\nu,p)\}_{p\geq\nu}$ . Let $T=C_{\nu,p}$ . By Lemma 6, we have

\ell(T)=p^{2^{\nu-1}-1}\text{ ,}

	$\displaystyle\|V(T)\|$	$\displaystyle\leq(\nu-1)p^{2^{\nu-1}}\;\Rightarrow\;\|V(T)\|^{\frac{2^{\nu-1}-1}% {2^{\nu-1}}}\leq\left((\nu-1)p^{2^{\nu-1}}\right)^{\frac{2^{\nu-1}-1}{2^{\nu-1% }}}$
		$\displaystyle=(\nu-1)^{\frac{2^{\nu-1}-1}{2^{\nu-1}}}\cdot p^{2^{\nu-1}-1}\leq% (\nu-1)\cdot\ell(T).$

So, $\ell(T)\geq\frac{|V(T)|^{1-\frac{1}{2^{\nu-1}}}}{\nu-1}$ . Therefore, $\operatorname{bfsw}(T)\geq\frac{n^{1-\frac{1}{2^{\nu-1}}}}{\nu-1}.$ $\hfill\blacktriangleleft$

4 Upper Bound on BFS-width of Bounded Cutwidth Graphs

In this section, we prove the following theorem.

Theorem 7.

For any graph $G=(V,E)$ we have

\operatorname{bfsw}(G)\leq 2\Delta^{2}\cdot n^{1-1/2^{2\operatorname{pw}(G)+1}% }=O_{\Delta}(n^{1-\epsilon(\operatorname{pw}(G))})\text{,}

where $\epsilon(x)=1/2^{2x+1}$ , $\Delta=\Delta(G)$ , and $n=|V(G)|$ .

To prove Theorem 7, we will first show that any graph $G$ contains a uniform depth tree $T$ with $\ell(T)=\operatorname{bfsw}(G)$ and Strahler number at most $2\operatorname{cw}(G)+2$ . Next, we prove an upper bound on the number of leaves of any uniform depth tree with respect to its Strahler number and maximum degree $\Delta(G)$ , thereby obtaining an upper bound for $\operatorname{bfsw}(G)$ as a function of $\operatorname{pw}(G)$ or $\operatorname{cw}(G)$ via Strahler number.

We show the following lemma.

Lemma 8.

Any graph $G=(V,E)$ contains a uniform depth tree $T$ with Strahler number at most $2\operatorname{pw}(G)+2$ that has exactly $\operatorname{bfsw}(G)$ leaves.

Proof.

We prove the statement by obtaining such a tree from $G$ . Let $\ell=\operatorname{bfsw}(G)$ . We first run BFS rooted at a vertex $r$ for which the BFS-width of $G$ is realized i.e. any vertex $r$ such that $\operatorname{bfsw}(G,r)=\operatorname{bfsw}(G)$ . Then we scan through the BFS layers and delete every layer deeper than the first layer $L$ that has $\ell$ vertices. We then drop all edges of $G$ not in the BFS tree and iteratively delete all leaves which are not in layer $L$ . This results in a uniform depth tree $T$ with at most $|V(G)|$ vertices. Since $T$ is a subgraph of $G$ , $\operatorname{pw}(T)\leq\operatorname{pw}(G)$ . Also, $\operatorname{bfsw}(T)=\ell$ , as we never delete any vertices in layer $L$ . By Lemma 3, we know that $T$ has Strahler number at most $2\operatorname{pw}(G)+2$ . $\hfill\blacktriangleleft$

4.1 Lower Bound on Number of Vertices in a Uniform Depth Tree with Bounded Strahler Number

The following theorem gives a lower bound on the order of any uniform depth tree with a given Strahler number and a given number of leaves. This theorem, equivalently, gives an upper bound on the number of leaves of a uniform depth tree with a given Strahler number and a given order.

Theorem 9.

Let $T$ be a uniform depth tree with Strahler number $\nu\geq 2$ with maximum degree $\Delta$ . Then $\ell(T)\leq 2\Delta^{2}|V(T)|^{1-1/2^{\nu-1}}$ .

Proof.

We define $f(\nu)=2^{\nu-1}/(2^{\nu-1}-1)=(1-1/2^{\nu-1})^{-1}$ and prove $|V(T)|\geq(\ell(T))^{f(\nu)}/(2\Delta^{2})$ . The statement of the lemma then follows from the following calculation

|V(T)|\geq\frac{(\ell(T))^{f(\nu)}}{2\Delta^{2}}\Rightarrow\ell(T)\leq|V(T)|^{% 1-1/2^{\nu-1}}\cdot(2\Delta^{2})^{1-1/2^{\nu-1}}\leq 2\Delta^{2}\cdot|V(T)|^{1% -1/2^{\nu-1}}\text{.}

Let $P\subseteq V(T)$ be the subset of all vertices of Strahler number $\nu$ in $T$ . Observe that the induced subgraph $T[P]$ is a downward path starting at the root, as (1) the root has value $\nu$ , (2) each non-root vertex of value $\nu$ has a parent of value $\nu$ , and (3) each vertex of value $\nu$ has at most one child of value $\nu$ . Let $P^{\prime}\subseteq P$ be the subset of $P$ that includes vertices with at least one child outside $P$ . As $P^{\prime}$ is a subset of the downward path $P$ , it contains no pair of vertices at the same depth. Let $(p_{1},p_{2},\ldots,p_{t})$ be the set of vertices in $P^{\prime}$ ordered inversely with respect to their depth.

Let $Q\subseteq V(T)$ be the set of neighbors of $P$ that are not in $P$ , i.e. $Q=N_{T}(P)$ . For each $q\in Q$ , let $T_{q}$ be the subtree of $T$ rooted at $q$ . We use $V(T_{q})$ to denote $T_{q}$ ’s vertex set, $\ell(T_{q})$ to denote the number of its leaves, $\nu(T_{q})$ to denote its Strahler number, and $h(T_{q})$ the (maximum) number of vertices in a root to leaf path in $T_{q}$ , i.e. $h(T_{q})=\operatorname{height}(T_{q})+1$ .

First, we derive a lower bound on $|V(T)|$ , from the simple lower bound $|V(T_{q})|\geq h(T_{q})$ for all $q\in Q$ . Specifically, $|V(T)|\geq\sum_{q\in Q}{h(T_{q})}\text{.}$ Further, we observe that each vertex in $p_{i}\in P^{\prime}$ has at least one child in $Q$ , by the definition of $P^{\prime}$ . For $i\in\{1,2,\ldots,t\}$ let $q_{i}$ be an arbitrary child of $p_{i}$ with Strahler number less than $\nu$ , and observe that $h(T_{q_{i}})\geq i$ . Therefore,

|V(T)|\geq\sum_{q\in Q}{h(T_{q})}\geq\sum_{i=1}^{t}{h(T_{q_{i}})}\geq\sum_{i=1% }^{t}{i}=\frac{t(t+1)}{2}\geq\frac{t^{2}}{2}.

(1)

Now, we consider two cases based on the cardinality of $Q$ . In what follows let $\ell=\ell(T)$ .

Case (I) $|Q|\geq\ell^{f(\nu)/2}$ .

We have,

t\Delta\geq|Q|\geq\ell^{f(\nu)/2}\Rightarrow t\geq\frac{\ell^{f(\nu)/2}}{% \Delta}\text{ .}

Therefore, by Equation 1, we have

|V(T)|\geq\frac{\ell^{f(\nu)}}{2\Delta^{2}}\text{ ,}

as desired.

Case (II) $|Q|\leq\ell^{f(\nu)/2}$ .

We proceed by using induction on $\nu$ .

For the base case, $\nu=2$ , the values of all vertices in $V\setminus P$ are one. Hence $T[V\setminus P]$ is a collection of paths, each connecting a leaf of $T$ to a (perhaps identical) vertex in $Q$ . Therefore, $|Q|=\ell=\ell^{f(\nu)/2}$ , as $f(\nu)=2$ for $\nu=2$ . Therefore, the base case is implied by the argument of Case (I).

For the inductive step we first observe that $\ell=\sum_{q\in Q}{\ell(T_{q})}$ , as each leaf of $T$ is a descendant of exactly one vertex in $Q$ (where a vertex is considered a descendant of itself). Next, we use Hölder’s inequality: for any pair of vectors $x, y$ in Euclidean space and any pair $\alpha,\beta\in\mathbb{R}^{+}$ such that $1/\alpha+1/{\beta}=1$ , we have $\|x\cdot y\|_{1}\leq\|x\|_{\alpha}\cdot\|y\|_{\beta}$ . Now let $x=(\ell(T_{q}))_{q\in Q}$ (with an arbitrary order on $Q$ ) and $y=\mathbf{1}$ , the all $1$ vector. We have:

\ell=\sum_{q\in Q}\ell(T_{q})\leq\left(\sum_{q\in Q}(\ell(T_{q}))^{\alpha}% \right)^{\frac{1}{\alpha}}\left(\sum_{q\in Q}1^{\beta}\right)^{\frac{1}{\beta}% }\leq\left(\sum_{q\in Q}(\ell(T_{q}))^{\alpha}\right)^{\frac{1}{\alpha}}\cdot% \Big|Q\Big|^{\frac{\alpha-1}{\alpha}},

where the last equality holds as $1/\alpha+1/\beta=1\Rightarrow\beta=\alpha/(\alpha-1)$ . Raising the sides to $\alpha$ ,

\ell^{\alpha}\leq\sum_{q\in Q}(\ell(T_{q}))^{\alpha}\cdot|Q|^{\alpha-1}.

(2)

Now, we set $\alpha:=f(\nu-1)$ , and observe $\alpha=f(\nu-1)>1$ for $\nu\geq 3$ , justifying our use of Hölder’s inequality. Next, we show $\sum_{q\in Q}(\ell(T_{q}))^{\alpha}\leq 2\Delta^{2}\cdot|V(T)|$ by showing $\ell(T_{q})^{\alpha}\leq 2\Delta^{2}\cdot|V(T_{q})|$ for every $q\in Q$ . We consider two possible cases.

If $\nu(T_{q})=1$ then $T_{q}$ is a path, possibly with just one vertex and no edge. Therefore, $(\ell(T_{q}))^{\alpha}\leq 2\Delta^{2}\cdot|V(T_{q})|$ , as (i) $\ell(T_{q})=1$ , (ii) $|V(T_{q})|\geq 1$ , and (iii) $\alpha=f(\nu-1)>0$ as $\nu\geq 3$ and (iv) $\Delta\geq 2$ (it is important to note that $\Delta$ is the maximum degree in the original $T$ ).

Otherwise, if $\nu(T_{q})>1$ , then we use the induction hypothesis. To that end, note $f(\cdot)$ is a decreasing function over the interval $(1,\infty)$ , and $\nu(T_{q})\leq\nu-1$ for all $q\in Q$ . Thus,

(\ell(T_{q}))^{\alpha}=(\ell(T_{q}))^{f(\nu-1)}\leq(\ell(T_{q}))^{f(\nu(T_{q})% )}\leq 2(\Delta(T_{q}))^{2}\cdot|V(T_{q})|\leq 2\Delta^{2}\cdot|V(T_{q})|\text% {.}

Substituting in Equation 2,

\ell^{f(\nu-1)}\leq 2\Delta^{2}\cdot|V(T)|\cdot|Q|^{f(\nu-1)-1}\Rightarrow|V(T% )|\geq\frac{\ell^{f(\nu-1)}\cdot|Q|^{1-f(\nu-1)}}{2\Delta^{2}}.

Since $|Q|\leq\ell^{f(\nu)/2}$ and $1-f(\nu-1)<0$ ,

\ell^{f(\nu-1)}\cdot|Q|^{1-f(\nu-1)}\geq\ell^{(f(\nu-1)+(1-f(\nu-1))\frac{f(% \nu)}{2})}=\ell^{f(\nu)}\text{,}

which completes the proof. The last equality is proved below.

	$\displaystyle f(\nu-1)+(1-f(\nu-1))f(\nu)/2$	$\displaystyle=\frac{2^{\nu-2}}{2^{\nu-2}-1}+\Big(1-\frac{2^{\nu-2}}{2^{\nu-2}-% 1}\Big)\cdot\frac{1}{2}\cdot\frac{2^{\nu-1}}{2^{\nu-1}-1}$
		$\displaystyle=\frac{2^{\nu-2}}{2^{\nu-2}-1}+\Big(\frac{-1}{2^{\nu-2}-1}\Big)% \cdot\frac{2^{\nu-2}}{2^{\nu-1}-1}$
		$\displaystyle=\frac{2^{\nu-2}}{2^{\nu-2}-1}\Big(1-\frac{1}{2^{\nu-1}-1}\Big)$
		$\displaystyle=\frac{2^{\nu-2}}{2^{\nu-2}-1}\cdot\frac{2^{\nu-1}-2}{2^{\nu-1}-1% }=\frac{2^{\nu-1}}{2^{\nu-1}-1}=f(\nu).\$

$\hfill\blacktriangleleft$

4.2 Proof of Theorem 7

We conclude this section with a proof of Theorem 7 using the results from above.

Proof of Theorem 7.

By Lemma 8, $G$ contains a uniform depth tree $T$ of Strahler number $\nu(T)\leq 2\operatorname{pw}(G)+2$ with at most $|V(G)|$ vertices and exactly $\operatorname{bfsw}(G)$ leaves, i.e. $\ell(T)=\operatorname{bfsw}(G)$ . By Theorem 9,

\ell(T)\leq 2\Delta^{2}|V(T)|^{1-1/2^{\nu(T)-1}}\leq 2\Delta^{2}|V(T)|^{1-1/2^% {2\operatorname{pw}(G)+1}}\leq 2\Delta^{2}|V(G)|^{1-1/2^{2\operatorname{pw}(G)% +1}},

which completes the proof. $\hfill\blacktriangleleft$

5 Graph reconstruction algorithm

In this section, we apply the above results to the hidden graph reconstruction problem mentioned in the introduction. We formally define this problem, briefly summarize some of the known results, and then state our main theorem in this area.

In the hidden graph reconstruction problem, only the vertex set $V(G)$ of a hidden graph $G$ is visible, and the goal is to reconstruct the edge set $E(G)$ by making queries to an oracle. A hidden graph reconstruction algorithm, referred to simply as a reconstruction algorithm, aims to discover the edge set with as few adaptively chosen queries as possible. The reconstruction task is considered complete once there is a unique graph, up to isomorphism, consistent with answers to all the queries. Several query models have been studied for graph reconstruction, including edge existence queries, edge counting, effective resistance queries, and shortest path queries [2, 3, 4, 11, 17, 22].

The query model that will be considered in this paper is the shortest path distance query model (SP query model). In the SP query model, we have access to a distance oracle: for any two vertices $u,v\in V(G)$ , a query returns the length of the shortest path between $u$ and $v$ in $G$ and returns $\infty$ if no such path exists. There are several motivations and applications to studying the hidden graph reconstruction problem with the SP query model [1, 7, 9, 16, 24].

Problem Background and Prior Work

Any unweighted graph can trivially be reconstructed using $\binom{n}{2}$ SP queries simply by querying every pair of vertices to check whether they are adjacent. Importantly, this upper bound is tight even for trees if we allow unbounded degree [22]. Moreover, the bound is tight if one allows disconnected graphs; reconstructing a graph with $n$ vertices and one edge requires $\Omega(n^{2})$ queries. In light of these observations, all non-trivial algorithmic results on graph reconstruction focus on connected, bounded degree graphs.

In 2013, Mathieu et al. [18, 21] showed that general bounded degree graphs can be reconstructed using $\tilde{O}_{\Delta}(n^{3/2})$ expected queries via a randomized algorithm, where $\tilde{O}(f(n))$ is shorthand for $O(f(n)\cdot\text{polylog}(n))$ . This is still the best known general upper bound today. It is unknown whether there exists a deterministic algorithm to reconstruct bounded-degree graphs in $o(n^{2})$ queries. Many graph classes less general than bounded degree graphs have been studied. Nearly linear query complexity algorithms, both randomized and deterministic, have been found for graph classes like chordal graphs, nearly chordal graphs, $k$ -chordal graphs, and bounded treelength graphs [5, 6, 23, 19] and matching lower bounds for some of these classes have also been shown [5].

Our Algorithm

Our result for hidden graph reconstruction in this paper is a deterministic reconstruction algorithm for any graph $G$ with bounded cutwidth using a subquadratic number of queries. More generally, we characterize the number of queries with respect to the maximum degree and the pathwidth of the graph – recall a bounded degree bounded pathwidth graph has bounded cutwidth and vice versa. We note again that this implies a subquadratic query reconstruction algorithm for the class of bounded cutwidth graphs and we emphasize that this reconstruction algorithm runs without knowledge of the value of parameters $\operatorname{pw}(G)$ or $\operatorname{cw}(G)$ .

Theorem 10.

Let $G=(V,E)$ be a graph. Then there is an algorithm to reconstruct $G$ with at most $O((\Delta(G))^{2}\cdot n^{2-\epsilon(\operatorname{pw}(G))})$ shortest path distance queries where $\epsilon(x)=1/{2^{2x+1}}$ .

Proof.

By Theorem 7,

\operatorname{bfsw}(G)\leq 2(\Delta(G))^{2}\cdot n^{1-\epsilon(\operatorname{% pw}(G))}=:b\text{ .}

The algorithm selects an arbitrary vertex $s\in V$ . It runs $n-1$ queries to obtain $s$ to $v$ distances for all $v\in V\setminus\{s\}$ . Then, it computes BFS layers $B_{1},B_{2},\ldots,B_{k}\subseteq V$ with respect to $s$ , i.e. for each $i\in[k]$ , $B_{i}$ is the subset of vertices at distance $i$ of $s$ . We know all the edges of the graph are between vertices that belong to the same or consecutive layers of BFS. The algorithm, thus, queries all these pairs to find all possible edges, i.e. all pairs $u,v\in V$ that belong to the same $B_{i}$ or consecutive $B_{i}$ and $B_{i+1}$ . Hence, setting $x_{i}=|B_{i}|$ , the number of queries made in this part of the algorithm is bounded above by

\sum_{i\in[k]}{x_{i}^{2}}+\sum_{i\in[k-1]}{x_{i}x_{i+1}}\leq 3\sum_{i\in[k]}{x% _{i}^{2}}\text{ ,}

as $x_{i}x_{i+1}\leq x_{i}^{2}+x_{i+1}^{2}$ for all $i\in[k-1]$ .

Next, we show that $\sum_{i\in[k]}{x_{i}^{2}}\leq bn$ , hence the algorithm makes at most

3bn+n-1=6\Delta^{2}\cdot n^{2-\epsilon(\operatorname{pw}(G))}+n-1=O(\Delta^{2}% \cdot n^{2-\epsilon(\operatorname{pw}(G))})

queries in total.

To that end, let $x=(x_{1},x_{2},\ldots,x_{k})\in\mathbb{R}^{k}$ be a vector. Recall the Hölder’s inequality for two vectors $f,g\in\mathbb{R}^{k}$ is $\|f\cdot g\|_{1}\leq\|f\|_{\alpha}\cdot\|g\|_{\beta}$ with $1/\alpha+1/\beta=1$ . Now, we apply the inequality with $f=g=x$ , $\alpha=\infty$ and $\beta=1$ . So,

\sum_{i\in[k]}{x_{i}^{2}}=\|x\cdot x\|\leq\|x\|_{\infty}\|x\|_{1}=\max_{i\in[k% ]}{|x_{i}|}\cdot\sum_{i\in[k]}{|x_{i}|}\leq bn\text{ .}\

$\hfill\blacktriangleleft$

References

[1] Dimitris Achlioptas, Aaron Clauset, David Kempe, and Cristopher Moore. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. J. ACM, 56(4), 2009. doi:10.1145/1538902.1538905.
[2] Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM Journal on Discrete Mathematics, 18(4):697–712, 2005. doi:10.1137/S0895480103431071.
[3] Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden matching. SIAM Journal on Computing, 33(2):487–501, 2004. doi:10.1137/S0097539702420139.
[4] Dana Angluin and Jiang Chen. Learning a hidden graph using o(log n) queries per edge. In John Shawe-Taylor and Yoram Singer, editors, Learning Theory, pages 210–223, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. doi:10.1007/978-3-540-27819-1_15.
[5] Paul Bastide and Carla Groenland. Optimal distance query reconstruction for graphs without long induced cycles, 2024. doi:10.48550/arXiv.2306.05979.
[6] Paul Bastide and Carla Groenland. Quasi-linear distance query reconstruction for graphs of bounded treelength. In Édouard Bonnet and Pawel Rzazewski, editors, 19th International Symposium on Parameterized and Exact Computation, IPEC 2024, September 4-6, 2024, Royal Holloway, University of London, Egham, United Kingdom, volume 321 of LIPIcs, pages 20:1–20:11. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.IPEC.2024.20.
[7] Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matúš Mihaľák, and L. Shankar Ram. Network discovery and verification. In Dieter Kratsch, editor, Graph-Theoretic Concepts in Computer Science, pages 127–138, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/11604686_12.
[8] Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1):1–45, 1998. doi:10.1016/S0304-3975(97)00228-4.
[9] Luca Dall’Asta, Ignacio Alvarez-Hamelin, Alain Barrat, Alexei Vázquez, and Alessandro Vespignani. Exploring networks with traceroute-like probes: Theory and simulations. Theoretical Computer Science, 355(1):6–24, 2006. Complex Networks. doi:10.1016/j.tcs.2005.12.009.
[10] Josep Díaz, Jordi Petit, and Maria Serna. A survey of graph layout problems. ACM Comput. Surv., 34(3):313–356, 2002. doi:10.1145/568522.568523.
[11] W. Ellens, F.M. Spieksma, P. Van Mieghem, A. Jamakovic, and R.E. Kooij. Effective graph resistance. Linear Algebra and its Applications, 435(10):2491–2506, 2011. Special Issue in Honor of Dragos Cvetkovic. doi:10.1016/j.laa.2011.02.024.
[12] J.A. Ellis, I.H. Sudborough, and J.S. Turner. The vertex separation and search number of a graph. Information and Computation, 113(1):50–79, 1994. doi:10.1006/inco.1994.1064.
[13] David Eppstein, Michael T. Goodrich, and Songyu (Alfred) Liu. Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing. In 33rd Annual European Symposium on Algorithms (ESA 2025), Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1–69:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ESA.2025.69.
[14] Uriel Feige. Coping with the NP-hardness of the graph bandwidth problem. In Algorithm Theory—SWAT 2000, volume 1851 of Lecture Notes in Computer Science, pages 10–19, Berlin, Heidelberg, 2000. Springer. doi:10.1007/3-540-44985-X_2.
[15] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979.
[16] Jotun J. Hein. An optimal algorithm to reconstruct trees from additive distance data. Bulletin of Mathematical Biology, 51(5):597–603, 1989. doi:10.1016/S0092-8240(89)80102-8.
[17] Jeremy Hoskins, Cameron Musco, Christopher Musco, and Babis Tsourakakis. Inferring networks from random walk-based node similarities. In Advances in Neural Information Processing Systems, volume 31, 2018. URL: https://papers.nips.cc/paper/2018/hash/2f25f6e3.pdf.
[18] Sampath Kannan, Claire Mathieu, and Hang Zhou. Graph reconstruction and verification. ACM Trans. Algorithms, 14(4), 2018. doi:10.1145/3199606.
[19] Chirag Kaudan and Amir Nayyeri. Reconstructing bounded treelength graphs with linearithmic shortest path distance queries. In Shahin Kamali, editor, Proceedings of the 37th Canadian Conference on Computational Geometry (CCCG 2025), York University, Toronto, Canada, August 13-15, 2025, pages 243–248, 2025.
[20] Michael Luttenberger. An extension of Parikh’s theorem beyond idempotence. CoRR, abs/1112.2864, 2011. arXiv:1112.2864.
[21] Claire Mathieu and Hang Zhou. Graph reconstruction via distance oracles. In Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming, pages 733–744, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. doi:10.1007/978-3-642-39206-1_62.
[22] Lev Reyzin and Nikhil Srivastava. Learning and verifying graphs using queries with a focus on edge counting. In Marcus Hutter, Rocco A. Servedio, and Eiji Takimoto, editors, Algorithmic Learning Theory, pages 285–297, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. doi:10.1007/978-3-540-75225-7_24.
[23] Guozhen Rong, Wenjun Li, Yongjie Yang, and Jianxin Wang. Reconstruction and verification of chordal graphs with a distance oracle. Theoretical Computer Science, 859:48–56, 2021. doi:10.1016/j.tcs.2021.01.006.
[24] M.S. Waterman, T.F. Smith, M. Singh, and W.A. Beyer. Additive evolutionary trees. Journal of Theoretical Biology, 64(2):199–213, 1977. doi:10.1016/0022-5193(77)90351-4.

[bib.bib1] [1] Dimitris Achlioptas, Aaron Clauset, David Kempe, and Cristopher Moore. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. J. ACM, 56(4), 2009. doi:10.1145/1538902.1538905.

[bib.bib2] [2] Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM Journal on Discrete Mathematics, 18(4):697–712, 2005. doi:10.1137/S0895480103431071.

[bib.bib3] [3] Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden matching. SIAM Journal on Computing, 33(2):487–501, 2004. doi:10.1137/S0097539702420139.

[bib.bib4] [4] Dana Angluin and Jiang Chen. Learning a hidden graph using o(log n) queries per edge. In John Shawe-Taylor and Yoram Singer, editors, Learning Theory, pages 210–223, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. doi:10.1007/978-3-540-27819-1_15.

[bib.bib5] [5] Paul Bastide and Carla Groenland. Optimal distance query reconstruction for graphs without long induced cycles, 2024. doi:10.48550/arXiv.2306.05979.

[bib.bib6] [6] Paul Bastide and Carla Groenland. Quasi-linear distance query reconstruction for graphs of bounded treelength. In Édouard Bonnet and Pawel Rzazewski, editors, 19th International Symposium on Parameterized and Exact Computation, IPEC 2024, September 4-6, 2024, Royal Holloway, University of London, Egham, United Kingdom, volume 321 of LIPIcs, pages 20:1–20:11. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.IPEC.2024.20.

[bib.bib7] [7] Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matúš Mihaľák, and L. Shankar Ram. Network discovery and verification. In Dieter Kratsch, editor, Graph-Theoretic Concepts in Computer Science, pages 127–138, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/11604686_12.

[bib.bib8] [8] Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1):1–45, 1998. doi:10.1016/S0304-3975(97)00228-4.

[bib.bib9] [9] Luca Dall’Asta, Ignacio Alvarez-Hamelin, Alain Barrat, Alexei Vázquez, and Alessandro Vespignani. Exploring networks with traceroute-like probes: Theory and simulations. Theoretical Computer Science, 355(1):6–24, 2006. Complex Networks. doi:10.1016/j.tcs.2005.12.009.

[bib.bib10] [10] Josep Díaz, Jordi Petit, and Maria Serna. A survey of graph layout problems. ACM Comput. Surv., 34(3):313–356, 2002. doi:10.1145/568522.568523.

[bib.bib11] [11] W. Ellens, F.M. Spieksma, P. Van Mieghem, A. Jamakovic, and R.E. Kooij. Effective graph resistance. Linear Algebra and its Applications, 435(10):2491–2506, 2011. Special Issue in Honor of Dragos Cvetkovic. doi:10.1016/j.laa.2011.02.024.

[bib.bib12] [12] J.A. Ellis, I.H. Sudborough, and J.S. Turner. The vertex separation and search number of a graph. Information and Computation, 113(1):50–79, 1994. doi:10.1006/inco.1994.1064.

[bib.bib13] [13] David Eppstein, Michael T. Goodrich, and Songyu (Alfred) Liu. Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing. In 33rd Annual European Symposium on Algorithms (ESA 2025), Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1–69:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ESA.2025.69.

[bib.bib14] [14] Uriel Feige. Coping with the NP-hardness of the graph bandwidth problem. In Algorithm Theory—SWAT 2000, volume 1851 of Lecture Notes in Computer Science, pages 10–19, Berlin, Heidelberg, 2000. Springer. doi:10.1007/3-540-44985-X_2.

[bib.bib15] [15] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979.

[bib.bib16] [16] Jotun J. Hein. An optimal algorithm to reconstruct trees from additive distance data. Bulletin of Mathematical Biology, 51(5):597–603, 1989. doi:10.1016/S0092-8240(89)80102-8.

[bib.bib17] [17] Jeremy Hoskins, Cameron Musco, Christopher Musco, and Babis Tsourakakis. Inferring networks from random walk-based node similarities. In Advances in Neural Information Processing Systems, volume 31, 2018. URL: https://papers.nips.cc/paper/2018/hash/2f25f6e3.pdf.

[bib.bib18] [18] Sampath Kannan, Claire Mathieu, and Hang Zhou. Graph reconstruction and verification. ACM Trans. Algorithms, 14(4), 2018. doi:10.1145/3199606.

[bib.bib19] [19] Chirag Kaudan and Amir Nayyeri. Reconstructing bounded treelength graphs with linearithmic shortest path distance queries. In Shahin Kamali, editor, Proceedings of the 37th Canadian Conference on Computational Geometry (CCCG 2025), York University, Toronto, Canada, August 13-15, 2025, pages 243–248, 2025.

[bib.bib20] [20] Michael Luttenberger. An extension of Parikh’s theorem beyond idempotence. CoRR, abs/1112.2864, 2011. arXiv:1112.2864.

[bib.bib21] [21] Claire Mathieu and Hang Zhou. Graph reconstruction via distance oracles. In Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming, pages 733–744, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. doi:10.1007/978-3-642-39206-1_62.

[bib.bib22] [22] Lev Reyzin and Nikhil Srivastava. Learning and verifying graphs using queries with a focus on edge counting. In Marcus Hutter, Rocco A. Servedio, and Eiji Takimoto, editors, Algorithmic Learning Theory, pages 285–297, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. doi:10.1007/978-3-540-75225-7_24.

[bib.bib23] [23] Guozhen Rong, Wenjun Li, Yongjie Yang, and Jianxin Wang. Reconstruction and verification of chordal graphs with a distance oracle. Theoretical Computer Science, 859:48–56, 2021. doi:10.1016/j.tcs.2021.01.006.

[bib.bib24] [24] M.S. Waterman, T.F. Smith, M. Singh, and W.A. Beyer. Additive evolutionary trees. Journal of Theoretical Biology, 64(2):199–213, 1977. doi:10.1016/0022-5193(77)90351-4.

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

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Funding:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Overview of Results

Cutwidth vs. BFS Width

Graph Reconstruction

2 Background

2.1 Basic Definitions and Notation

2.2 Preliminaries on Width Parameters and Strahler Numbers

Definition 1.

Definition 2.

Lemma 3.

3 Lower Bound Construction

Theorem 4.

Base Case (𝒑=𝟐).

Recursive case (𝒑>𝟐).

Lemma 5.

Proof.

Lemma 6.

Proof.

Proof of Theorem 4.

4 Upper Bound on BFS-width of Bounded Cutwidth Graphs

Theorem 7.

Lemma 8.

Proof.

4.1 Lower Bound on Number of Vertices in a Uniform Depth Tree with Bounded Strahler Number

Theorem 9.

Proof.

Case (I) |𝑸|≥ℓ𝒇⁢(𝝂)/𝟐.

Case (II) |𝑸|≤ℓ𝒇⁢(𝝂)/𝟐.

4.2 Proof of Theorem 7

Proof of Theorem 7.

5 Graph reconstruction algorithm

Problem Background and Prior Work

Our Algorithm

Theorem 10.

Proof.

References

Base Case ( $p=2$ ).

Recursive case ( $p>2$ ).

Case (I) $|Q|\geq\ell^{f(\nu)/2}$ .

Case (II) $|Q|\leq\ell^{f(\nu)/2}$ .