Courcelle’s Theorem for Lipschitz Continuity

Now we provide a technical overview of our framework. Since the arguments for clique-width are similar, we focus here on the treewidth results and omit the clique-width case.

For simplicity, here we consider the maximum weight independent set problem on a full binary tree (a rooted tree in which every vertex has exactly 0 or 2 children). This corresponds to the case where $\phi (X)=\forall x\forall y((x\in X\wedge y\in X)\to \neg \mathrm{𝖺𝖽𝗃}(x,y))$. Let $w\in {ℝ}_{\ge 0}^V$ be the weight vector.

If we do not care about Lipschitzness, this problem can exactly be solved by the following algorithm. For each vertex $v\in V$, define $\mathrm{𝖣𝖯}[v][0]$ to be an independent set in the subtree rooted at $v$ that does not include $v$ with the maximum weight. Similarly, define $\mathrm{𝖣𝖯}[v][1]$ to be an independent set in the subtree rooted at $v$ with the maximum weight. If $v$ is a leaf, then $\mathrm{𝖣𝖯}[v][0]=\mathrm{\varnothing }$ and $\mathrm{𝖣𝖯}[v][1]=\{v\}$. Otherwise, let $u_1$ and $u_2$ be the two children of $v$. We have $\mathrm{𝖣𝖯}[v][0]=\mathrm{𝖣𝖯}[u_1][1]\cup \mathrm{𝖣𝖯}[u_2][1]$, and $\mathrm{𝖣𝖯}[v][1]$ is the one with the larger weight of $X_{v,0}:=\mathrm{𝖣𝖯}[u_1][0]\cup \mathrm{𝖣𝖯}[u_2][0]\cup \{v\}$ and $X_{v,1}:=\mathrm{𝖣𝖯}[u_1][1]\cup \mathrm{𝖣𝖯}[u_2][1]$. By performing this dynamic programming in a bottom-up manner, the problem can be solved exactly.

However, this algorithm is not Lipschitz continuous. This is because when we compute $\mathrm{𝖣𝖯}[v][1]$, which of $X_{v,0}$ or $X_{v,1}$ has a larger weight is affected by small changes in the weights. To address this issue, we use the exponential mechanism [7]. Specifically, for some constant $c>0$, we select $X_{v,i}$ with probability proportional to $\exp (c\cdot w(X_{v,i}))$. This approach makes the algorithm Lipschitz continuous, with only a slight sacrifice in the approximation ratio. Specifically, we can prove that by appropriately choosing $c$ for a given ${\epsilon }^{\prime }\in (0,1]$, the increase in the Lipschitz constant can be bounded by $\tilde{O}({\epsilon }^{\prime -1})$ by reducing the approximation guarantee by a factor of $1-{\epsilon }^{\prime }$ at each vertex where the exponential mechanism is applied.

While this approach makes the algorithm Lipschitz continuous, the Lipschitz constant is still too large when the height $h$ of the tree is large. Specifically, to achieve an approximation guarantee of $1-\epsilon$, we need to set ${\epsilon }^{\prime }=\frac{\epsilon }{h}$, leading to a Lipschitz constant of $h\cdot \tilde{O}({\epsilon }^{\prime -1})=\tilde{O}({\epsilon }^{-1}{h}^2)$. This is larger than the trivial bound $n$ when $h=O(n)$. We resolve this issue by using the fact that any tree has a tree decomposition of width 5 and height $O(\log n)$ [2]. By performing dynamic programming with the exponential mechanism on this tree decomposition, we can obtain $(1-\epsilon )$-approximation algorithm with Lipschitz constant $\tilde{O}({\epsilon }^{-1})$. This argument can be naturally extended to the case where $G$ is a bounded treewidth graph. By following the proof of Courcelle’s Theorem [3, 5], we further extend this argument to the case where $\phi$ is a general ${\text{MSO}}_2$ formula with a free vertex variable.

We prove Theorem 5 by leveraging a lower bound on a related notion of sensitivity for the maximum cut problem [8], where sensitivity measures the change in the output with respect to the Hamming distance under edge deletions [21]. Specifically, we reduce the maximum cut problem, where stability is defined with respect to edge deletions, to the max ones problem, where stability is measured with respect to weight changes.

Lipschitz continuity of discrete algorithms is defined by Kumabe and Yoshida [14], and they provided Lipschitz continuous approximation algorithms for the minimum spanning tree, shortest path, and maximum weight matching problems. In a subsequent work [16], they further provided such algorithms for the minimum weight vertex cover, minimum weight set cover, and minimum weight feedback vertex set problems. In another work [15], they defined Lipschitz continuity for allocations in cooperative games and provided Lipschitz continuous allocation schemes for the matching game and the minimum spanning tree game.

A variant known as pointwise Lipschitz continuity has also been studied, which is defined using the unweighted Hamming distance instead of the weighted Hamming distance. Kumabe and Yoshida [14] defined pointwise Lipschitz continuity and provided pointwise Lipschitz continuous algorithms for the minimum spanning tree and maximum weight bipartite matching problems. Liu et al. [18] proposed the proximal gradient method as a general technique for solving LP relaxations stably. Using this, they provided pointwise Lipschitz continuous approximation algorithms for the minimum vertex $(S,T)$-cut, densest subgraph, maximum weight ($b$-)matching, and packing integer programming problems.

(Average) sensitivity, introduced by Varma and Yoshida [21] with preliminary ideas by Murai and Yoshida [19], is a notion similar to Lipschitz continuity. While Lipschitz continuity evaluates an algorithm’s stability against unit changes in the input weights, (average) sensitivity evaluates an algorithm’s stability against (random) deletions of elements from the input. Algorithms with small (average) sensitivity have been studied for several problems, such as maximum matching [21, 23], minimum cut [21], knapsack problem [13], Euclidean $k$-means [22], spectral clustering [20], and dynamic programming problems [12]. Recently, Fleming and Yoshida [8] constructed a PCP framework to prove the sensitivity lower bound for the constraint satisfaction problem.

The rest of this paper is organized as follows. In Section 2, we describe the necessary preliminaries on tree decomposition (Sections 2.1 and 2.2), logic (Section 2.3), and Lipschitz continuity (Section 2.4). In Section 3, we prove Theorem 1 by providing a Lipschitz continuous algorithm for the ${\text{MSO}}_2$ maximization problem. Since the algorithm and analysis for ${\text{MSO}}_2$ minimization are similar, we defer the proof of Theorem 2 to the full version. In Section 4, we give a more precise Lipschitzness analysis for specific formulas $\phi$, which includes the proof of Theorem 3. Proofs of Theorems 4, 5, 6, and 7 are given in the full version.

Let $G$ be a graph with $n$ vertices. A pair $(ℬ,𝒯)$ consisting of a family $ℬ$ of subsets (called bags) of $V(G)$ and a rooted tree $𝒯$ whose vertex set is $ℬ$ is a (rooted) tree decomposition of $G$ if it satisfies the following three conditions.

• $\mathrm{■}$

  ${\bigcup }_{B\in ℬ}B=V(G)$.

• $\mathrm{■}$

  For each edge $e\in E(G)$, there is a bag $B\in ℬ$ such that $e\subseteq B$.

• $\mathrm{■}$

  For each vertex $v\in V(G)$, the set of bags $\{B\in ℬ:v\in B\}$ induces connected subgraph in $T$.

For a tree decomposition $(ℬ,𝒯)$, we may refer to the root node, leaf nodes, and the height of $𝒯$ as those of $(ℬ,𝒯)$, respectively. Moreover, $(ℬ,𝒯)$ is binary if $𝒯$ is a binary tree. The width of a tree decomposition $(ℬ,𝒯)$ is the maximum size of a bag in $ℬ$ minus one. The treewidth of $G$ is the minimum possible width among all possible tree decompositions of $G$. It is known that the tree decomposition of $G$ of width at most $2k+1$ can be computed in $2^{O(k)}n$ time [10], where $k$ is the treewidth of $G$. Moreover, any tree decomposition of $G$ of width $k$ can be transformed into a binary tree decomposition of width at most $3k+2$ and height at most $O(\log n)$ [2]. Thus, we obtain the following lemma.

We introduce the notions of HR-algebra²²2The acronym HR stands for hyperedge replacement [4]., which is one of the algebraic definitions of tree decomposition. A $k$-graph is a tuple $G=⟨V,E,\mathrm{𝗌𝗋𝖼}⟩$ of a set of vertices $V$, a set of edges $E$, and a $k$-vector $\mathrm{𝗌𝗋𝖼}\in {(V\cup \{\mathrm{𝚗𝚒𝚕}\})}^k$. We write the $i$-th element of a vector $\mathrm{𝗌𝗋𝖼}$ by $\mathrm{𝗌𝗋𝖼}(i)$. If $\mathrm{𝗌𝗋𝖼}(i)=u$, we say that $u$ is a $i$-source. We write the set $\{\mathrm{𝗌𝗋𝖼}(i):i\in [k]\}\setminus \{\mathrm{𝚗𝚒𝚕}\}$ by $\mathrm{𝗌𝗋𝖼}(G)$.

Let $G$ and $H$ be $k$-graphs. The parallel-composition of $G$ and $H$, denoted by $G//H$, is the graph generated by the following procedure. First, create the disjoint union of $G$ and $H$, and identify the (non-$\mathrm{𝚗𝚒𝚕}$) vertices ${\mathrm{𝗌𝗋𝖼}}_G(i)$ and ${\mathrm{𝗌𝗋𝖼}}_H(i)$ for each $i\in [k]$. Finally, remove all the self-loops and multi-edges. Let $B$ be a non-empty subset of $[k]$. The source forgetting operation ${\mathrm{𝖿𝗀}}_B$ is the function that maps a $k$-graph $G$ to a $k$-graph $G^{\prime }$ such that $V_G=V_{G^{\prime }}$, $E_G=E_{G^{\prime }}$, and ${\mathrm{𝗌𝗋𝖼}}_{G^{\prime }}(i)=\mathrm{𝚗𝚒𝚕}$ if $i\in B$, and ${\mathrm{𝗌𝗋𝖼}}_{G^{\prime }}(i)={\mathrm{𝗌𝗋𝖼}}_G(i)$ otherwise.

We may associate a term with the graphs represented by it. A term of an HR-algebra $t$ can be decomposed into the parse tree in the usual way, called the (rooted) HR-parse tree of $t$. The height of a HR-parse tree is the maximum distance from the root to a leaf. It is known that tree decompositions are equivalent to HR-parse trees in the following sense.

Moreover, binary tree decomposition can be transformed into an HR-parse tree with approximately the same height.

The proof of Proposition 11 is essentially the same as the proof of Proposition 10 but we give in the full version.

We provide a slightly less formal definition of monadic second-order (MSO) logic over $k$-graphs for accessibility (see, e.g., [17] for more formal definition). An atomic formula is a formula of the form $s=t$, $\mathrm{𝖺𝖽𝗃}(s,t)$, $t\in X$, and Boolean constants $\mathrm{𝚃𝚛𝚞𝚎}$ and $\mathrm{𝙵𝚊𝚕𝚜𝚎}$. Here, $\mathrm{𝖺𝖽𝗃}(s,t)$ is the predicate that represents whether $s$ and $t$ are adjacent. A monadic second-order formula over $k$-graphs is a formula built from atomic formulas, the usual Boolean connectives $\wedge ,\vee ,\neg ,\to$, first-order quantifications $\exists x$ and $\forall x$ (quantifications over vertices), and second-order quantifications $\exists X$ and $\forall X$ (quantification over sets of vertices). The notation $\phi (X)$ indicates that $\phi$ has exactly one free variable $X$. The quantifier height (or quantifier rank) of a formula $\phi$, denoted by $|\phi |$, is the maximum depth of quantifier nesting in $\phi$ (see e.g. [17] for a formal definition). The counting monadic second-order (CMSO) logic is an expansion of MSO logic that have additional predicates ${\mathrm{𝖢𝖺𝗋𝖽}}_{m,r}(X)$ for a second-order variable $X$, meaning $|X|\equiv m(modr)$. A ${\text{C}}_r{\text{MSO}}^q$-formula is a CMSO formula $\phi$ such that the quantifier height of $\phi$ is at most $q$ and $r^{\prime }\le r$ holds for any predicate ${\mathrm{𝖢𝖺𝗋𝖽}}_{m,r^{\prime }}$ in $\phi$. For a logical formula $\phi$ and a graph $G$, we write $G\vDash \phi$ when graph $G$ satisfies the property expressed by $\phi$.

There are two variants of MSO logic: ${\text{MSO}}_1$ (or simply MSO), which is described above, allows quantification over vertices and sets of vertices only, and ${\text{MSO}}_2$ which allows quantification over edges and sets of edges as well. It is well known that, for any graph $G$ and ${\text{MSO}}_2$-formula $\phi$, there exists an ${\text{MSO}}_1$ formula ${\phi }^{\prime }$ such that $G\vDash \phi \iff G^{\prime }\vDash {\phi }^{\prime }$, where $G^{\prime }$ is the incidence graph, obtained by subdividing each edge of $G$ (with two colors meaning the original and the subdivision vertices) (see e.g. [11]). It is easy to see that the treewidth of the incidence graph is at most the treewidth of the original graph. Thus, since this paper focuses on graphs with bounded treewidth, we mainly consider ${\text{MSO}}_1$. However, all the theorems are held for ${\text{MSO}}_2$ and graphs of bounded treewidth.

We introduce some more notations. For a set $V$, two families $𝒜\subseteq 2^V$ and $ℬ\subseteq 2^V$ are separated if $A\cap B=\mathrm{\varnothing }$ for all $A\in 𝒜$, and $B\in ℬ$. We write $A\cup B$ by $A\uplus B$ if $A\cap B=\mathrm{\varnothing }$, and $𝒜⊠ℬ≔\{A\cup B:A\in 𝒜,B\in ℬ\}$ if $𝒜$ and $ℬ$ are separated. For a formula $\phi (X)$ and a graph $G$, the set of vertex sets satisfying $\phi$ is denoted by $\mathrm{𝗌𝖺𝗍}(G,\phi )$, that is, $\mathrm{𝗌𝖺𝗍}(G,\phi )=\{A:G\vDash \phi (A)\}$.

The following theorem is a key of the MSO model-checking algorithm [3, 4].

It is known that, for any $r,q,k$, up to logical equivalence, there are only finitely many different ${\text{C}}_r{\text{MSO}}^q$-formulas $\phi (X)$ over $k$-graphs (see e.g., [17]). Thus, we can obtain a linear-time algorithm, based on dynamic programming over trees, for ${\text{C}}_r{\text{MSO}}^q$ model checking over bounded treewidth. Courcelle and Mosbah [5] adjusted Theorem 12 to address optimization, counting, and other problems. We use a slightly modified version of the theorem of Courcelle and Mosbah.

Let $\mathrm{𝗇𝗈𝗌𝗋𝖼}(X)\equiv {\bigwedge }_{i\in [k]}(\mathrm{𝗌𝗋𝖼}(i)\notin X)$, and $\phi {\upharpoonright }_S(X)$ denote $\phi (X\cup S)\wedge \mathrm{𝗇𝗈𝗌𝗋𝖼}(X)$ for a set $S\subseteq \mathrm{𝗌𝗋𝖼}(G)$.

The proof of Corollary 14 is given in the full version.

Then, we can design an algorithm for an (C)MSO maximization (minimization) problem over graphs of bounded treewidth. For simplicity, we assume that the given graph $G$ has no sources, that is, $\mathrm{𝗌𝗋𝖼}(G)=\mathrm{\varnothing }$. Let $t$ be a term denoting $G_t$ and $\phi (X)$ be the (C)MSO-formula describing the constraint of the problem. We recursively compute the value $\mathrm{𝗈𝗉𝗍}(t^{\prime },{\phi }^{\prime }{\upharpoonright }_S)=\max \{w(A):G\vDash {\phi }^{\prime }{\upharpoonright }_S(A)\}$ for any subterm $t^{\prime }$ of $t$ and MSO-formula ${\phi }^{\prime }{\upharpoonright }_S$ as follows, where $w\in {ℝ}_{\ge 0}^V$ is the given weight vector and $w(X)={\sum }_{x\in X}{w}_x$ for any $X\subseteq V(G)$. If $t^{\prime }$ is of the form ${\mathrm{𝖿𝗀}}_B(t^{\prime \prime })$, then $\mathrm{𝗈𝗉𝗍}({\mathrm{𝖿𝗀}}_B(t^{\prime \prime }),{\phi }^{\prime }{\upharpoonright }_S)={\max }_{S^{\prime }\subseteq B}\{\mathrm{𝗈𝗉𝗍}(t^{\prime \prime },\psi {\upharpoonright }_{S\cup S^{\prime }})+w(S^{\prime })\}$, where, $\psi$ is the formula obtained from Corollary 14. If $t^{\prime }$ is of the form $t_1//t_2$, then $\mathrm{𝗈𝗉𝗍}(t^{\prime },{\phi }^{\prime }{\upharpoonright }_S)={\max }_{i\in [p]}\{\mathrm{𝗈𝗉𝗍}(t_1,\theta {\upharpoonright }_{S_i})+\mathrm{𝗈𝗉𝗍}(t_2,\psi {\upharpoonright }_{S_i^{\prime }})\}$, where, ${\{{\theta }_i{\upharpoonright }_{S_i}(X),{\psi }_i{\upharpoonright }_{S_i^{\prime }}(X)\}}_{i\in [p]}$ are the formulas obtained from Corollary 14. Then, $\mathrm{𝗈𝗉𝗍}(t,\phi {\upharpoonright }_{\mathrm{\varnothing }})$ is the maximum value for the problem since $t$ has no sources. In the following, for simplicity, we may omit the ${\upharpoonright }_S$ notation and consider only formulas $\phi$ such that $\mathrm{𝗌𝖺𝗍}(G,\phi )$ does not contain any sources.

In the above setting, the graphs are considered without any special vertex sets (called as colors) or special vertices (called as labels). However, for $k$-graphs with a constant number of colors and/or labels, an appropriate HR-algebra and logics can be defined, and the similar results for Corollary 14 hold (see e.g. [4, 17]).

We formally define Lipschitz continuity of algorithms. As this is sufficient for this work, we only consider algorithms for vertex-weighted graph problems. The definition can be naturally extended to other settings, such as edge-weighted problems. Let $G=(V,E)$ be a graph. For vertex sets $X,X^{\prime }\subseteq V$ and weight vectors $w,w^{\prime }\in {ℝ}_{\ge 0}^V$, we define the weighted Hamming distance between $(X,w)$ and $(X^{\prime },w^{\prime })$ by
$d_{\mathrm{w}}((X,w),(X^{\prime },w^{\prime })):={\Vert {\displaystyle \sum _{v\in X}}{\mathrm{𝟏}}_v{w}_v-{\displaystyle \sum _{v\in X^{\prime }}}{\mathrm{𝟏}}_v{w}_v^{\prime }\Vert }_1={\displaystyle \sum _{v\in X\cap X^{\prime }}}|w_v-w_v^{\prime }|+{\displaystyle \sum _{v\in X\setminus X^{\prime }}}{w}_v+{\displaystyle \sum _{v\in X^{\prime }\setminus X}}{w}_v^{\prime },$

where ${\mathrm{𝟏}}_v\in {\{0,1\}}^V$ denotes the characteristic vector of $v$, that is, the vector ${\mathrm{𝟏}}_{v,u}=1$ holds if and only if $u=v$. For two probability distributions $𝒳$ and ${𝒳}^{\prime }$ over subsets of $V$, we define

where the minimum is taken over couplings of $𝒳$ and ${𝒳}^{\prime }$, that is, distributions over pairs of sets such that its marginal distributions on the first and second coordinates are equal to $𝒳$ and ${𝒳}^{\prime }$, respectively. Consider an algorithm $𝒜$, that takes a graph $G=(V,E)$ and a weight vector $w\in {ℝ}_{\ge 0}^V$ as an input and outputs a vertex subset $X\subseteq V$. We denote the output distribution of $𝒜$ for weight $w$ as $𝒜(w)$. The Lipschitz constant of $𝒜$ is defined by

For two random variables $𝑿$ and ${𝑿}^{\prime }$, the total variation distance between them is given as:

where the minimum is taken over couplings between $𝑿$ and ${𝑿}^{\prime }$, that is, distributions over pairs such that its marginal distributions on the first and the second coordinates are equal to $𝑿$ and ${𝑿}^{\prime }$, respectively. For an element $u\in V$, we use ${\mathrm{𝟏}}_u\in {ℝ}_{\ge 0}^V$ to denote the characteristic vector of $u$, that is, ${\mathrm{𝟏}}_u(u)=1$ and ${\mathrm{𝟏}}_u(v)=0$ for $v\in V\setminus \{u\}$. The following lemma indicates that, to bound the Lipschitz constant, it suffices to consider pairs of weight vectors that differ by one coordinate.

In our algorithm, we use the following procedures softmax and softmin. These procedures are derived from the exponential mechanism in the literature of differential privacy [7] and frequently appear in the literature on Lipschitz continuity [14, 16]. Here, we organize them into a more convenient form for our use. Let $p\in {\mathbb{Z}}_{\ge 1}$, $x_1,\mathrm{\dots },x_p\in {ℝ}_{\ge 0}$, and $ϵ\in (0,1]$. The softmax of $x_1,\mathrm{\dots },x_p$ is taken as follows. If ${\max }_{i\in [p]}{x}_i=0$, we set ${\mathrm{𝗌𝗈𝖿𝗍𝖺𝗋𝗀𝗆𝖺𝗑}}_{i\in [p]}^{ϵ}{x}_i$ to be an arbitrary index $i$ with $x_i=0$ and ${\mathrm{𝗌𝗈𝖿𝗍𝗆𝖺𝗑}}_{i\in [p]}^{ϵ}{x}_i=0$. Assume otherwise. First, we sample $𝒄$ uniformly from $[\frac{2{ϵ}^{-1}\log (2p{ϵ}^{-1})}{{\max }_{i\in [p]}{x}_i},\frac{4{ϵ}^{-1}\log (2p{ϵ}^{-1})}{{\max }_{i\in [p]}{x}_i}]$. Let ${𝒊}^{\ast }$ be a probability distribution over $[p]$ such that

holds for all $i\in [p]$. Then, we define ${\mathrm{𝗌𝗈𝖿𝗍𝖺𝗋𝗀𝗆𝖺𝗑}}_{i\in [p]}^{ϵ}{x}_i:={𝒊}^{\ast }$ and ${\mathrm{𝗌𝗈𝖿𝗍𝗆𝖺𝗑}}_{i\in [p]}^{ϵ}{x}_i:=x_{{𝒊}^{\ast }}$. We have the following. The proofs of Lemmas 16 and 17 are given in the full version.

Similarly, the softmin of $x_1,\mathrm{\dots },x_p$ is taken as follows. If ${\min }_{i\in [p]}{x}_i=0$, we set ${\mathrm{𝗌𝗈𝖿𝗍𝖺𝗋𝗀𝗆𝗂𝗇}}_{i\in [p]}^{ϵ}{x}_i$ be an arbitrary index $i$ with $x_i=0$ and ${\mathrm{𝗌𝗈𝖿𝗍𝗆𝗂𝗇}}_{i\in [p]}^{ϵ}{x}_i=0$. Assume otherwise. First, we sample $𝒄$ uniformly from $[\frac{2{ϵ}^{-1}\log (2p{ϵ}^{-1})}{{\min }_{i\in [p]}{x}_i},\frac{4{ϵ}^{-1}\log (2p{ϵ}^{-1})}{{\min }_{i\in [p]}{x}_i}]$. Let ${𝒊}^{\ast }$ be a probability distribution over $[p]$ such that

holds for all $i\in [p]$. Then, we define ${\mathrm{𝗌𝗈𝖿𝗍𝖺𝗋𝗀𝗆𝗂𝗇}}_{i\in [p]}^{ϵ}{x}_i:={𝒊}^{\ast }$ and ${\mathrm{𝗌𝗈𝖿𝗍𝗆𝗂𝗇}}_{i\in [p]}^{ϵ}{x}_i:=x_{{𝒊}^{\ast }}$. We have the following. The proofs of Lemmas 18 and 19 are given in the full version.

For a graph $G$, a weight vector $w$, and an ${\text{MSO}}_2$ formula $\phi$, we define

for maximization problems and

for minimization problems. If $\mathrm{𝗌𝖺𝗍}(G,\phi )=\mathrm{\varnothing }$, we define ${\mathrm{𝗈𝗉𝗍}}_w[G,\phi ]=\mathrm{𝚗𝚒𝚕}$. For graphs $G$ and ${\text{MSO}}_2$ formulas $\phi$ with $\mathrm{𝗌𝖺𝗍}(G,\phi )\ne \mathrm{\varnothing }$, our algorithm recursively computes the vertex set ${\mathrm{𝖣𝖯}}_w[G,\phi ]$ that approximately achieves the maximum in Equation (1) or minimum in Equation (2). When it is clear from the context, we omit the subscript $w$ and simply write $\mathrm{𝗈𝗉𝗍}[G,\phi ]$ and $\mathrm{𝖣𝖯}[G,\phi ]$. We perform the dynamic programming algorithm using the formulas defined in Corollary 14 over the parse tree of a term obtained from Lemma 8 and Proposition 11. Specifically, at every stage of the algorithm, it is guaranteed that each $X\in \mathrm{𝗌𝖺𝗍}(G,\phi )$ satisfies $X\subseteq V(G)\setminus \mathrm{𝗌𝗋𝖼}(G)$. Furthermore, our algorithm is randomized. Thus, $\mathrm{𝖣𝖯}[G,\phi ]$ can be considered as a probability distribution over vertex sets in $\mathrm{𝗌𝖺𝗍}(G,\phi )$.

To bound the approximation ratio, for a weight vector $w\in {ℝ}_{\ge 0}^V$, we bound the ratio between $𝔼\left[w(\mathrm{𝖣𝖯}[G,\phi ])\right]$ and $\mathrm{𝗈𝗉𝗍}[G,\phi ]$. To bound the Lipschitz constant, for a weight vector $w\in {ℝ}_{\ge 0}^V$, $u\in V$, and $\delta >0$, we bound $\mathrm{𝖤𝖬}({\mathrm{𝖣𝖯}}_w[G,\phi ],{\mathrm{𝖣𝖯}}_{w+\delta {\mathrm{𝟏}}_u}[G,\phi ])$. From now on, we will concentrate on maximizing problems. The algorithm for minimization problems is similar to that for maximization problems, while the detail of the analysis is slightly differ. We discuss the minimization version in the full version.

Here we consider the base case. Let $G$ be a graph with a single vertex $v$ and no edges, where $v$ is a source of $G$, and $\phi$ be an ${\text{MSO}}_2$ formula such that $\mathrm{𝗌𝖺𝗍}(G,\phi )$ is nonempty and contains no set containing $v$. In particular, we have $\mathrm{𝗌𝖺𝗍}(G,\phi )=\{\mathrm{\varnothing }\}$. We set $\mathrm{𝖣𝖯}[G,\phi ]:=\mathrm{\varnothing }$. Since $w(\mathrm{\varnothing })=0$, it is clear that $w\left(\mathrm{𝖣𝖯}[G,\phi ]\right)=\mathrm{𝗈𝗉𝗍}[G,\phi ]=0$. Furthermore, it is obvious that

Next, we consider the parallel composition. Let

Assume we have already computed $\mathrm{𝖣𝖯}[G,{\theta }_i]$ and $\mathrm{𝖣𝖯}[H,{\psi }_i]$ for each $i\in [p]$. We compute $\mathrm{𝖣𝖯}[G//H,\phi ]$. For each $i\in [p]$, we denote ${\mathrm{𝗈𝗉𝗍}}_i:=\mathrm{𝗈𝗉𝗍}[G,{\theta }_i]+\mathrm{𝗈𝗉𝗍}[H,{\psi }_i]$. By definition, we have ${\max }_{i\in [p]}{\mathrm{𝗈𝗉𝗍}}_i=\mathrm{𝗈𝗉𝗍}[G//H,\phi ]$. Then, we take ${𝒊}^{\ast }={\mathrm{𝗌𝗈𝖿𝗍𝖺𝗋𝗀𝗆𝖺𝗑}}_{i\in [p]}^{\epsilon }{\mathrm{𝗈𝗉𝗍}}_i$ and define $\mathrm{𝖣𝖯}[G//H,\phi ]:=\mathrm{𝖣𝖯}[G,{\theta }_{{𝒊}^{\ast }}]\cup \mathrm{𝖣𝖯}[H,{\psi }_{{𝒊}^{\ast }}]$. First we analyze the approximation ratio.

Here we consider forget operation. Let $B\subseteq {\mathrm{𝗌𝗋𝖼}}_G$ and