Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs.
Nikhil Bansal, Daniel Reichman, Seeun William Umboh · arXiv (Cornell University) · 2016
We give a general approach to solve various optimization problems on noisy minor-free and bounded treewidth graphs, where some fraction of the edges have been corrupted adversarially. Our results are motivated by a previous work of Magen and Moharrami, who gave a $(1+\epsilon)$-approximate estimation algorithm for the independent set problem on noisy planar graphs, but left open the question of how to actually find a $(1+\epsilon)$-approximate independent set. While there are several approaches known for planar independent set, based on recursively using separators or decomposition into $k$-outerplanar or bounded treewidth graphs, they break down completely with noise. Our main contribution is to design robust variants of these algorithms using LP-based techniques that also work in the noisy setting.