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 Chitaranjan Das, Thesis Honors Advisor Sergei Tabachnikov, Thesis 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.
