Event Type:

Geometry-Topology Seminar

Date/Time:

Monday, April 27, 2020 - 12:00 to 12:50

Location:

Zoom

Guest Speaker:

Mitchell Black

Institution:

Graduate Student - Computer Science

Abstract:

The treewidth of a graph is the size of the smallest tree decomposition of the

graph. Intuitively, a graph with small treewidth looks like a tree. Tree decom-

positions are used in faster algorithms for problems on graphs with bounded

treewidth that are hard otherwise. While algorithmic problems for bounded

treewidth graphs have been well studied, there has been little work on problems

for simplicial complexes with bounded treewidth 1-skeleton

In this talk, we introduce the notion of tree decompositions and treewidth of

graphs. we then show how we can design algorithms on tree decompositions of

the 1-skeleton of simplicial complexes. If the size of these tree decompositions

is bounded, these algorithms run in polynomial time. In particular, we present

algorithms for the minimum bounded chain problem and the problem of nding

a predetermined surface within a 2-complex with bounded treewidth 1-skeleton.

Strong hardness results exists for both of these problems in their general form.