Courcelle’s Theorem for Lipschitz Continuity
Tatsuya Gima, Soh Kumabe, Yuichi Yoshida · 2025
Read Courcelle’s Theorem for Lipschitz Continuity by Tatsuya Gima, Soh Kumabe, Yuichi Yoshida (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-21118.txt.
Introduction
Tatsuya Gima, Soh Kumabe, and Yuichi Yoshida published a computer science paper in 2025 on stable algorithms. A stable algorithm barely changes its answer when inputs shift slightly. That property, called Lipschitz continuity, supports reliable decisions. Until now, stable algorithms were designed separately for each problem.
The authors prove a broad meta-theorem for the field. It parallels a classic result about graphs with small tree-like structure. For weighted vertex problems stated in a standard logic, good stable approximations exist. The guarantee holds on graphs of bounded treewidth. Similar results cover a second graph measure, clique-width. Their method beats most earlier problem-specific designs on quality, stability, or both.
Catalog record
| CREATOR | Tatsuya Gima, Soh Kumabe, Yuichi Yoshida |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-21118
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Courcelle’s Theorem for Lipschitz Continuity Tatsuya Gima, Soh Kumabe, Yuichi Yoshida Abstract Lipschitz continuity of algorithms, introduced by Kumabe and Yoshida (FOCS’23), measures the stability of an algorithm against small input perturbations. Algorithms with small Lipschitz continuity are desirable, as they ensure reliable decision-making and reproducible scientific research. Several studies have proposed Lipschitz continuous algorithms for various combinatorial optimization problems, but these algorithms are problem-specific, requiring a separate design for each problem. To address this issue, we provide the first algorithmic meta-theorem in the field of Lipschitz continuous algorithms. Our result can be seen as a Lipschitz continuous analogue of Courcelle’s theorem, which offers Lipschitz continuous algorithms for problems on bounded-treewidth graphs. Specifically, we consider the problem of finding a vertex set in a graph that maximizes or minimizes the total weight, subject to constraints expressed in monadic second-order logic ( MSO 2 \textsf{MSO}_{2} ). We show that for any ε > 0 \varepsilon>0 , there exists a ( 1 ± ε ) (1\pm\varepsilon) -approximation algorithm for the problem with a polylogarithmic Lipschitz constant on bounded treewidth graphs. On such graphs, our result outperforms most existing Lipschitz continuous algorithms in terms of approximability and/or Lipschitz continuity. Further, we provide similar results for problems on bounded-clique-width graphs subject to constraints expressed in MSO 1 \textsf{MSO}_{1} . Additionally, we construct a Lipschitz continuous version of Baker’s decomposition using our meta-theorem as a subroutine. 1 Introduction Lipschitz continuity of algorithms, introduced by Kumabe and Yoshida [ 15 ] , is a measure of an algorithm’s stability in response to errors or small perturbations in the input for weighted optimization problems. Roughly speaking, it is the maximum ratio of the (weighted) Hamming distance between the outputs of an algorithm for two different weights to the \ell_{1} distance between those weights (see Section 2.4 for the precise definition). It is desirable for algorithms to have small Lipschitz constants, as large constants can undermine the reliability of decision-making and the reproducibility of scientific research. Since its introduction, Lipschitz continuous algorithms have been proposed for various optimization problems [ 15 , 17 ] . However, we need to design a different algorithm and analyze its Lipschitz continuity for each problem, which can be impractical. To address this limitation, we present an algorithmic meta-theorem for Lipschitz continuous algorithms, which can be seen as Lipschitz continuity analogue of celebrated Courcelle’s theorem [ 3 ] . To present our results, we first introduce some notation. Let G=(V,E) be a graph of n vertices with treewidth \mathrm{tw} , \varphi(X) be an \textsf{MSO}_{2} formula with a free vertex set variable X (see Section 2.3 for details about logic), and w\in\mathbb{R}_{\geq 0}^{V} be a weight vector. We consider the problem of finding a vertex subset X\subseteq V such that G\models\varphi(X) and w(X) is maximized, which we call the \textsf{MSO}_{2} maximization problem . We also consider the problem of finding X such that w(X) is minimized, which we call the \textsf{MSO}_{2} minimization problem . Our main results are the following. Theorem 1 . For any \varepsilon\in(0,1] , there is a (1-\varepsilon) -approximation algorithm for the \textsf{MSO}_{2} maximization problem with Lipschitz constant O\left((f(\mathrm{tw},|\varphi|)+\log\varepsilon^{-1}+\log\log n)\varepsilon^{-1}\log^{2}n\right) , where f is some computable function. The time complexity is bounded by O\left(f(\mathrm{tw},|\varphi|)n\right) . Theorem 2 . For any \varepsilon\in(0,1] , there is a (1+\varepsilon) -approximation algorithm for the \textsf{MSO}_{2} minimization problem with Lipschitz constant O\left((f(\mathrm{tw},|\varphi|)+\log\varepsilon^{-1}+\log\log n)\varepsilon^{-1}\log^{2}n\right) , where f is some computable function. The time complexity is bounded by O\left(f(\mathrm{tw},|\varphi|)n\right) . We note that the trivial upper bound on Lipschitz constant is n [ 17 ] ; therefore the bounds in the theorems above are significantly smaller for fixed \mathrm{tw} and \varphi . We also remark that our meta-theorems yield randomized approximation algorithms. This is necessary since, for most problems, it is known that exact or deterministic algorithms cannot be Lipschitz continuous [ 15 ] . When the treewidth of the input graph is bounded by a constant, Theorems 1 and 2 provide algorithms that outperform existing algorithms in terms of approximability and/or Lipschitz continuity: • For the minimum weight vertex cover problem, Theorem 2 yields an algorithm with a better approximation ratio than the previous 2 -approximation algorithm with Lipschitz constant 4 [ 17 ] , at the polylogarithmic sacrifice of the Lipschitz constant. • For the minimum weight feedback vertex set problem, Theorem 2 outperforms the previous O(\log n) -approximation algorithm with Lipschitz constant O(\sqrt{n}\log^{3/2}n) [ 17 ] in terms of both approximability and Lipschitz continuity. • For the maximum weight matching problem 1 1 1 Although the output of this problem is an edge set rather than a vertex set, this problem can be expressed by an \textsf{MSO}_{2} formula on a new graph G^{\prime}=(V\cup E,\{(v,e)\colon e\text{ is incident to }v\}) , Theorem 1 yields an algorithm with a better approximation ratio than the previous \left(\frac{1}{8}-\varepsilon\right) -approximation algorithm with Lipschitz constant O(\varepsilon^{-1}) [ 15 ] , at the polylogarithmic sacrifice of the Lipschitz constant. • For the shortest path problem, Theorem 2 slightly improves the Lipschitz continuity compared to the previous (1-\varepsilon) -approximation algorithm with Lipschitz constant O(\varepsilon^{-1}\log^{3}n) [ 15 ] , without losing approximability. For a fixed \varphi , by explicitly specifying the transitions in the dynamic programming within the algorithm, we can provide more precise bounds on the function f that appears in Theorems 1 and 2 . In particular, considering the case that \varphi is an \textsf{MSO}_{2} formula representing the independent set constraint, we have the following. Theorem 3 . For any \varepsilon\in(0,1] , there is a (1-\varepsilon) -approximation algorithm for the maximum weight independent set problem with Lipschitz constant O\left((\mathrm{tw}+\log\varepsilon^{-1}+\log\log n)\varepsilon^{-1}\log^{2}n\right) . The time complexity is bounded by 2^{O(\mathrm{tw})}n . This result is surprising as the dependence of \mathrm{tw} on the Lipschitz constant is subexponential and, even more remarkably, linear. We note that through similar arguments, analogous results hold for several other problems, such as the minimum weight vertex cover problem and the minimum weight dominating set problem. We further demonstrate that Theorems 1 and 2 lead to Lipschitz continuous version of Baker’s technique [ 1 ] . As a representative example, we consider the maximum weight independent set problem on planar graphs, where a vertex subset X is an independent set of a graph G if no two vertices in X are adjacent in G . We prove the following. Theorem 4 . For any \varepsilon\in(0,1] , there is a (1-\varepsilon) -approximation algorithm for the maximum weight independent set problem on planar graphs with Lipschitz constant O\left((\varepsilon^{-1}+\log\log n)\varepsilon^{-1}\log^{2}n\right) . The time complexity is bounded by 2^{O(\varepsilon^{-1})}n . Using similar algorithms, Lipschitz continuous PTASes can be obtained for many problems, including the minimum weight vertex cover problem and the minimum weight dominating set problem. As a lower bound result, we prove that the Lipschitz constant of any (1-\varepsilon) -approximation algorithm for some \textsf{MSO}_{2} maximization problem is large on general graphs, which justifies considering the \textsf{MSO}_{2} maximization problem on a restricted graph class. Specifically, we consider the max ones problem [ 7 , 10 ] , where the instance is a 3CNF formula over a variable set X and a weight function w:X\to\mathbb{R}_{\geq 0} , and the goal is to find a satisfying assignment \sigma:X\to\{0,1\} that maximizes the weight \sum_{x\in\sigma^{-1}(1)}w(x) . It is easy