The NP-Completeness of Finding Treewidth for Graphs and a 4-Approximation for Finding Treewidth
Open Access
- 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.