Submodular functions and perfect graphs

arXiv2110.00108MaRDI QIDQ6504696FDOQ6504696

Authors: Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Kristina Vušković 

Abstract: We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm.

This page was built for publication: Submodular functions and perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504696)