The NP-Completeness of Finding Treewidth for Graphs and a 4-Approximation for Finding Treewidth

Open Access
Author:
Hofman, Daniel Stephen
Area of Honors:
Interdisciplinary in Computer Engineering and Mathematics
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
  • Martin Furer, Thesis Supervisor
  • Chita Das, Honors Advisor
  • Sergei Tabachnikov, Honors Advisor
Keywords:
  • computer science
  • graph theory
  • treewidth
  • NP-completeness
  • approximation algorithms
Abstract:
Knowing certain parameters related to a graph can make solving problems known to be hard tractable when the parameter is fixed. One such widely studied parameter is treewidth, or a graph's closeness to a tree. Therefore, finding the treewidth of a graph can be very useful. Here, we present findings on the NP-completeness of finding treewidth for arbitrary graphs as well as a useful 4-approximation algorithm for finding the treewidth of a graph.