Pointwise Lipschitz Continuous Graph Algorithms via Proximal Gradient Analysis

In many real-world applications, it is prohibitively expensive to drastically change the solution to a problem after a small perturbation in the environment. Therefore, the stability of an algorithm is a very desirable property. In this paper, we study the class of pointwise Lipschitz continuous algorithms as introduced in the recent work of Kumabe and Yoshida [FOCS'23]. The Lipschitz constant of an algorithm, intuitively, bounds the ratio of the changes in its output (measured in $\ell_1$ distance) over the $\ell_1$ perturbations of the weights of the underlying graph. In this work, we give a general and simple framework for bounding the Lipschitz constant of algorithms measured through the unweighted $\ell_1$ distance of their outputs. Our approach consists of three main steps. First, we consider a natural continuous relaxation of the underlying graph problem by adding a smooth and strongly convex regularizer to the objective function. Then, we give upper bounds on the $\ell_1$ distance of the optimal solutions of the convex programs, under small perturbations of the weights, via a stability analysis of the trajectory of the proximal gradient method. Finally, we present new problem-specific rounding techniques to obtain integral solutions to several graph problems that approximately maintain the stability guarantees of the fractional solutions. We apply our framework to a number of problems including minimum $s$-$t$ cut, densest subgraph, maximum $b$-matching, and packing integer programs. To complement our algorithms, we show the tightness of our results for certain problems by establishing tight lower bounds.