Back to search

University of Waterloo

Combinatorially Thin Trees and Spectrally Thin Trees in Structured Graphs

Abstract

dc:description.abstract

Given 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 × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/20183

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Alghasi, Mahtab. Combinatorially Thin Trees and Spectrally Thin Trees in Structured Graphs. University of Waterloo, 2023. http://hdl.handle.net/10012/20183