Minimum Vertex Augmentation

Download PDF

Abstract

This paper introduces a class of graph problems named {\em minimum vertex augmentation} (MVA). Given an input graph $G$ where each vertex carries a binary color 0 or 1, we want to flip the colors of the fewest 0-vertices such that the subgraph induced by all the (original and new) 1-vertices satisfies a user-defined predicate $\pi$. In other words, the goal is to minimally augment the subset of 1-vertices to uphold the property $\pi$. Different formulations of $\pi$ instantiate the framework into concrete problems at the core of numerous applications. We first describe a suite of techniques for solving MVA problems with strong performance guarantees, and then present a generic algorithmic paradigm that a user can instantiate to deal with ad-hoc MVA problems. The effectiveness and efficiency of our solutions are verified with an extensive experimental evaluation.