Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp019k41zh59c
Title: Using Submodular Functions To Find Maximum Weighted Stable Sets
Authors: Bergman, Nathan
Advisors: Chudnovsky, Maria
Department: Mathematics
Certificate Program: Applications of Computing Program
Class Year: 2021
Abstract: Given a set V , call a function f : 2V → R submodular if for all X, Y ⊆ V , f(X) + f(Y ) ≥ f(X ∪Y ) +f(X ∩Y ). Mathematicians have developed several versions of a combinatorial algorithm to minimize submodular functions in time polynomial in |V |, including variants by Satoru Iwata, Lisa Fleischer, and Satoru Fujishige [1], and by Alexander Schrijver [2]. These algorithms assume that there exists an oracle which can compute f(X) in polynomial time for any X ⊆ V (G). Our original goal was to extend these algorithms to multiple dimensions through a polynomialtime algorithm for coordinate-wise submodular functions (informally, functions that are submodular in each dimension). Work recently done by Maria Chudnovsky, Cemil Dibek, Daniel McGinnis, and Shira Zerbib showed that coordinate-wise submodular function minimization is NP-Hard [3]. Consequently, we switched our focus over to looking for classes of graphs where we could find a maximum weighted stable set in polynomial time by using a corresponding submodular function. Specifically, this entailed looking for special types of even sets in certain classes of graphs, where an even set is a set S ⊆ V (G) where for any u, v ∈ S, every induced path between u and v in G has even length. In particular, we looked for even sets in the line graph of a bipartite graph and for iterated even sets (even sets which partition the graph’s vertices and can be removed in iteration) in Berge graphs.
URI: http://arks.princeton.edu/ark:/88435/dsp019k41zh59c
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2021

Files in This Item:
File Description SizeFormat 
BERGMAN-NATHAN-THESIS.pdf1.39 MBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.