University of Waterloo
Combinatorially Thin Trees and Spectrally Thin Trees in Structured Graphs
Abstract
dc:description.abstractGiven a graph $G=(V,E)$, finding simpler estimates of $G$ with possibly fewer edges or vertices while capturing some of its specific properties has been used in order to design efficient algorithms. The concept of estimating a graph with a simpler graph is known as graph sparsification. Spanning trees are an important family of graph sparsifiers that maintain connectivity of graphs, and have been utilized in many applications. However, spanning trees are a wide family, and for some applications one might need the spanning tree to have specific properties. Combinatorially thin trees are a type of spanning trees that show up in applications such as Asymmetric Travelling Salesman Problem (ATSP). A spanning tree $T$ of $G$ is combinatorially thin if there is no cut $U\subset V$ such that $T$ contains all the edges in δ(U), and the thinness parameter αG(T) measures the maximum fraction of edges in E(T)\cap δ(U) compared to δ(U) over all cuts $U\subset V$. Intuitively, combinatorial thinness measures how much edge-connectivity we lose while removing the spanning tree $T$ from $G$. It is easy to verify that if $G$ has connectivity $k$, then $\frac{1}{k}$ lower bounds αG. On the other hand, Goddyn conjectured that αG can also be upper bounded as a function of connectivity αG = f(\frac{1}{k}). This conjecture which is known as thin tree conjecture, was proved for the special case of graphs with bounded genus by Oveis-Gharan and Saberi, in 2011. However, the general case is still open. In the first part of this thesis, we study some of the known connections between edge-connectivity and αG and investigate the result of Oveis-Gharan and Saberi for the special case of planar graphs. For a general graph $G$ and spanning tree $T$, even verifying the combinatorial thinness αG(T) of $T$ is an $\text{NP}$-hard problem. A natural more efficiently computable relaxation of combinatorial thinness is the notion of spectral thinness. For a graph $G$ and a spanning tree $T$ in $G$ the spectral thinness θG(T) is the smallest value of θ such that θ\LG - \LT is a positive semidefinite matrix where \LG and \LT are Laplacian matrices of $G$ and $T$. Additionally, we define θG to be the minimum value of θG(T) over all spanning trees $T$ of $G$. Similar to combinatorial thinness and connectivity, θG(T) can be lower bounded by the maximum effective resistance of edges in $T$. It was also proven by Harvey and Olver in 2014 that the maximum effective resistance of edges in $G$ asymptotically upper bounds θG. However, finding a mathematical characterization of θG(T), even for structured graphs, is still a challenge. In the second part of this thesis, we will give general lower bound and upper bound certificates for θG(T) and utilize these certificates for circulant matrices to estimate spectral thinness of graphs such as complete graphs, complete bipartite graphs, and prism graphs.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Alghasi, Mahtab
- Advisors dc:contributor.advisor
-
- Cheriyan, Joseph
- Tunçel, Levent
Subjects
dc:subject × 5Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/20183