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 | Size | Format | |
---|---|---|---|---|

BERGMAN-NATHAN-THESIS.pdf | 1.39 MB | Adobe PDF | Request a copy |

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