This thesis initiates the study of the MAX-CUT problem in fully dynamic graphs. Given a graph $G=(V,E)$, we present the first fully dynamic algorithms to maintain a $\frac{1}{2}$-approximate cut in sublinear update time under edge insertions and deletions to $G$. Our results include the following deterministic algorithms: i) an $O(\Delta)$ \textit{worst-case} update time algorithm, where $\Delta$ denotes the maximum degree of $G$ and ii) an $O(m^{1/2})$ amortized update time algorithm where $m$ denotes the maximum number of edges in $G$ during any sequence of updates. \\ \indent We also give the following randomized algorithms when edge updates come from an oblivious adversary: i) a $\tilde{O}(n^{2/3})$ update time algorithm\footnote{Throughout this thesis, $\tilde{O}$ hides a $O(\text{polylog}(n))$ factor.} to maintain a $\frac{1}{2}$-approximate cut, and ii) a $\min\{\tilde{O}(n^{2/3}), \tilde{O}(\frac{n^{{3/2}+2c_0}}{m^{1/2}})\}$ worst case update time algorithm which maintains a $(\frac{1}{2}-o(1))$-approximate cut for any constant $c_0>0$ with high probability. The latter algorithm is obtained by designing a fully dynamic algorithm to maintain a sparse subgraph with sublinear (in $n$) maximum degree which approximates all large cuts in $G$ with high probability. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/11764 |
| Date | 21 May 2020 |
| Creators | Wasim, Omer |
| Contributors | King, Valerie D. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.019 seconds