I took part today in the successful dissertation defense of Will Maxwell, a student of Amir Nayyeri and Cora Borradaile at Oregon State University. Will has also visited me at UC Irvine, and I’ve worked with him on two papers, on low-stretch spanning trees and Hanoi graph treewidth. But his dissertation has a different focus, his work on generalizations of graph algorithms to higher-dimensional topological spaces.

The main idea can be seen in Will’s paper “Minimum bounded chains and minimum homologous chains in embedded simplicial complexes” (with Cora and Amir, at the 2020 Symposium on Computational Geometry), on topological generalizations of unweighted shortest paths in graphs. An abstract simplicial complex is just a family of finite sets closed under taking subsets, where we think of each set of \(d+1\) elements as defining a \(d\)-dimensional simplex. From this point of view, an undirected graph is just a 1-dimensional simplicial complex, with 1-element subsets for its vertices and 2-element subsets for its edges. A set of \(d\)-dimensional simplices is called a \(d\)-chain (in mod-2 homology), and its boundary is a chain one dimension lower. For instance, a path in a graph has its two endpoints as its boundary, and the shortest path problem asks for the minimum-cardinality 1-chain having two given points as its boundary. More generally the T-join problem asks for a 1-chain having any given 0-chain as its boundary.

The SoCG paper generalizes this problem in two ways. You can either ask for the minimum \(k\)-chain with a given \((k-1)\)-chain as boundary (the “minimum bounded chain” of the first part of the title), or you can ask for the minimum \(k\)-chain that shares a boundary with a given \(k\)-chain and belongs to the same homology class (the second part of the title). Both are \(\mathsf{NP}\)-complete and hard to approximate, even for \(k\)-dimensional complexes that are embedded into \((k+1)\)-dimensional space (analogous to planar graphs). However, they can be approximated to within a \(\sqrt{\log n}\) approximation ratio, and solved exactly in fixed-parameter tractable time. Both the positive and negative results involve translations to and from minimum cut completion, the problem of finding a cut that is as close as possible to a given edge set, on a dual graph of the embedding of the complex.

This use of the dual prevents these algorithms from applying to abstract complexes that are not embedded. And testing whether a complex can be embedded into a space of one higher dimension is itself a hard problem: \(\mathsf{NP}\)-hard for 2-complexes and undecidable for sufficiently higher dimensions. But it turns out that some abstract complexes can have duals even when they cannot be embedded: as Will’s dissertation observes, a dual graph exists whenever homology defines a cographic matroid on the \(k\)-simplices, a condition that generalizes Mac Lane’s planarity criterion and can be tested in polynomial time.

A newer paper, “Generalized max-flows and min-cuts in simplicial complexes” (with Amir), appears at this year’s European Symposium on Algorithms. It performs a similar translation from the maximum flow and minimum cut problems on graphs to analogous problems on simplicial complexes. The generalized problems are defined in a way allowing them to be solved by linear programs, with the flow LP dual to the cut LP, so a version of the max flow min cut theorem applies automatically to this generalization. However, unlike graph max flow and min cut problems, the solutions are not always integral, and finding an optimal integral solution is \(\mathsf{NP}\)-hard.

The SoCG 2020 and ESA 2021 papers form two chapters in the dissertation, with a final chapter on a third direction of generalization that appears not to be public yet. After finalizing his dissertation, Will will be heading to Washington, DC to work as a Department of Defense researcher on (non-classified) applications of topological computation in artificial intelligence.

Congratulations, Will!

(Discuss on Mastodon)