Graduate Thesis Or Dissertation
 

Computing Bounded Chains and Surfaces in a Simplicial Complex with Bounded-treewidth 1-skeleton

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/bv73c697f

Descriptions

Attribute NameValues
Creator
Abstract
  • We consider three problems on simplicial complexes: the Optimal Bounded Chain Problem, the Optimal Homologous Chain Problem, and 2-Dim-Bounded-Surface. The Optimal Bounded Chain Problem asks to find the minimum weight d-chain in a simplicial complex K bounded by a given (d−1)-chain, if such a d-chain exists. The Optimal Homologous Chain problem asks to find the minimum weight (d−1)-chain in K homologous to a given (d−1)-chain. 2-Dim-Bounded-Surface asks whether or not there is a subcomplex of K homeomorphic to a given compact, connected surface bounded by a given subcomplex. All three problems are NP-hard, and the first two problems are hard to approximate within any constant factor assuming the Unique Games Conjecture. We prove that all three problems are fixed-parameter tractable with respect to the treewidth of the 1-skeleton of K.
License
Resource Type
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Rights Statement
Publisher
Peer Reviewed
Language

Relationships

Parents:

This work has no parents.

In Collection:

Items