Constant-factor approximation of maximum distance-2 independent set in graphs of bounded merge-width
June 30, 2026
Abstract
We give a constant-factor approximation algorithm for Max Dist-\(2\) Independent Set in graphs of bounded radius-\(2\) merge-width. The same result holds for Min Dominating Set from [Bonamy and Geniet, 2025], [Chan et al., SODA ’12]. Both approximation algorithms are LP-based, showing that the domination-to-2-independence ratio is bounded in graphs of bounded radius-\(2\) merge-width. Moreover, this result is tight in the sense that the ratio can be unbounded in graphs of bounded radius-\(1\) merge-width.
1 Introduction↩︎
For a graph \(G\), a distance-\(2\) independent set is a set \(I\subseteq V(G)\) whose vertices are at pairwise distance more than \(2\), or equivalently, that the closed neighbourhoods of vertices in \(I\) are pairwise disjoint. The maximum size of such a set is the 2-independence number \(\alpha_2(G)\), and the corresponding optimisation problem is Max Dist-\(2\) Independent Set. Dually, the Min Dominating Set problem asks for a minimum-size set \(D \subseteq V(G)\) such that every vertex of \(G\) is in \(D\) or adjacent to a vertex of \(D\). The minimum size of such a set is the domination number \(\gamma(G)\). These two values are related by the inequality \(\alpha_2(G) \leqslant\gamma(G)\).
Both problems are NP-complete: Set Cover reduces to Min Dominating Set and Set Packing reduces to Max Dist-\(2\) Independent Set, and both are among Karp’s 21 NP-complete problems Karp72?. On general graphs, Min Dominating Set is approximable with factor \(\ln n\) Johnson74?, Lovasz75? and this is essentially tight unless \(\mathrm{P} = \mathrm{NP}\) DinurS14?. The problem Max Dist-\(2\) Independent Set is NP-hard to approximate within \(n^{1/2-\varepsilon}\) for any \(\varepsilon > 0\), even in bipartite and chordal graphs EtoGM14?, and is APX-hard in cubic graphs, though it admits a PTAS on planar graphs EtoILM22?.
On restricted graph classes, however, constant-factor approximations in polynomial-time become attainable. For Min Dominating Set, there are constant-factor approximations for graph classes of bounded degeneracy LenzenW10?, BansalU17? and of linear neighbourhood complexity CGKS12?. The latter encompass a broad range of graph classes, such as planar, bounded degree, bounded expansion and bounded twin-width. For Max Dist-\(2\) Independent Set, there is are constant-factor approximations for cubic graphs EtoILM17?, graph classes of bounded expansion Dvorak13? and bounded twin-width BGKTW24?. Note that for the latter, the constant-factor approximation requires that a decomposition of small twin-width is given as part of the input, however such decomposition is not known to be computable in polynomial-time.
Merge-width is a family of graph parameters recently introduced by Dreier and Toruńczyk merge-width?. In this paper we are specifically interested in graph classes of bounded radius-\(2\) merge-width, which include graphs classes such as planar, bounded degree, bounded expansion and bounded twin-width.
Notably, it was shown by Bonamy and Geniet bonamy2025chiboundedness? that graph classes of bounded radius-\(2\) merge-width have linear neighbourhood complexity, hence Min Dominating Set admits constant-factor approximation in these classes by the previously mentioned result of Chan et al. CGKS12?.
Contributions
The main result is the following.
Theorem 1. Max Dist-\(2\) Independent Set admits a constant-factor approximation in graphs of bounded radius-\(2\) merge-width.
See 7 for explicit bounds. Our approximation is simple greedy LP-relaxation-based algorithm, which pick vertices whose radius-\(2\) ball in the graph minimize the weight of a fractional distance-\(2\) independent set. The main technical lemma is that the weight of these balls are bounded by a function of the radius-\(2\) merge width. Additionally, we provide a tighter bound for bounded twin-width, improving upon the result of Bonnet et al. BGKTW24? (and providing a truly polynomial-time constant-factor approximation).
Related work
The relaxation of the integer linear program formulations of the two problems are LP-duals of each other, that is \(\gamma^*(G)= \alpha_2^*(G)\). A natural question is to ask is if ratio \(\gamma/\alpha_2\), called the domination-to-2-independence ratio, is small, and has been widely investigated. The ratio is bounded in many graph classes such as asteroidal triple-free BCGY25?, bounded expansion Dvorak13?, Dvorak19? or bounded twin-width BGKTW24?; and unbounded in bipartite 3-degenerate graphs Dvorak13? and split BCGY25?.
Both the constant-factor approximation of Chan et al. CGKS12? for Min Dominating Set and ours for Max Dist-\(2\) Independent Set are LP-based, in particular, the integrality gap of these problems are bounded. Since the LP relaxation of these problems are dual, it shows that the domination-to-2-independence ratio is bounded in graphs of bounded radius-\(2\) merge-width.
Natural generalisations of the considered problems are Min Dist-\(r\) Dominating Set and Max Dist-\(2r\) Independent Set. They also admit constant-factor approximations in graphs of bounded merge-width since these graph classes are closed under taking power. Note however that the radius of the merge-width may depend on \(r\), see 4 for more details.
2 Preliminaries↩︎
Graphs
Graphs are simple, undirected, and finite, that is, a graph \(G\) consists of a finite set \(V(G)\) of vertices and a set \(E(G)\subseteq \binom{V(G)}{2}\) of edges. The edge-complement of \(G\) is \(\overline{G}\), with \(V(\overline{G})\mathrel{\vcenter{:}}= V(G)\) and \(E(\overline{G}) \mathrel{\vcenter{:}}= \binom{V(G)}{2} \setminus E(G)\).
By \(\mathrm{dist}_G(x,y)\) we denote the length of a shortest path between \(x\) and \(y\) in \(G\) , and denote \(\mathrm{Ball}^r_G(v) \mathrel{\vcenter{:}}=\{w\in V(G)\mid \mathrm{dist}_G(v,w)\leqslant r\}\). By \(N_G(v)\) we denote the open neighbourhood of \(v\) in \(G\), that is, the set of vertices adjacent to \(v\); and by \(N_G(X)\) we denote the set of vertices adjacent to \(X\subseteq V(G)\), excluding \(X\) itself.
For two sets \(A,B\), we write \(AB \mathrel{\vcenter{:}}=\{ab\mid a\in A,b\in B,a\neq b\}\), where \(ab\) denotes the unordered pair \(\{a,b\}\). Two sets \(A,B\subseteq V(G)\) are complete if \(AB\subseteq E(G)\), and anticomplete if \(AB\cap E(G)=\varnothing\). The restriction of a partition \(\mathcal{P}\) of \(V(G)\) to a set \(S\subseteq V(G)\) is defined as \[\mathcal{P}\restriction_S = \{P \cap S \mid P\in \mathcal{P}\}\setminus \{\varnothing\}.\]
Merge-width
Let \(\mathcal{P}\) be a partition of the vertices \(V\) of a graph \(G\), and \(R \subseteq \binom{V}{2}\) be a set of pairs of vertices of \(G\). By \(\mathrm{dist}_R(x,y)\) and \(\mathrm{Ball}_R^r(x)\) we mean the corresponding notions in the graph \((V,R)\). We say that \(\mathcal{P}\) is homogeneous modulo \(R\) (in \(G\)) if for any parts \(A,B \in \mathcal{P}\) (possibly \(A=B\)), either all edges or all non-edges are in \(R\), that is for every pairs \(ab,a'b'\in AB\setminus R\), we have that \(ab \in E(G)\) if and only if \(a'b' \in E(G)\). The radius-\(r\) width of \((\mathcal{P},R)\) is \[\max_{v \in V} |\mathcal{P}\restriction_{\mathrm{Ball}^r_R(v)}|.\]
Definition 1 (merge-width?). A merge sequence* for a graph \(G\) is a sequence \[(\mathcal{P}_1,R_1),\dots,(\mathcal{P}_m,R_m)\] where*
\(\mathcal{P}_1\preccurlyeq \mathcal{P}_2\preccurlyeq\ldots\preccurlyeq \mathcal{P}_m\) is a sequence of ever coarser partitions of \(V(G)\) with \(\mathcal{P}_1\) the partition into singletons and \(\mathcal{P}_m\) the partition with one part,
\(R_1 \subseteq \dots \subseteq R_m \subseteq \binom{V(G)}{2}\) is a monotone sequence of set of pairs of vertices, and
\(\mathcal{P}_t\) is homogeneous modulo \(R_t\), for \(t=1,\ldots,m\).
The radius-\(r\) width* of this merge sequence is the maximum radius-\(r\) width of \((\mathcal{P}_{t},R_{t+1})\), for \(1 \leqslant t < m\). Finally, the radius-\(r\) merge-width of \(G\), denoted by \(\mathop{\mathrm{mw}}_r(G)\), is the minimum radius-\(r\) width of a merge sequence for \(G\).*
Note that the mismatched indices in \((\mathcal{P}_t,R_{t+1})\) are intentional, and forbid one from merging many parts and adding many resolved pairs all at once when going from step \(t\) to \(t+1\). A graph class \(\mathcal{C}\) has bounded merge-width there is a function \(f\) such that \(\mathop{\mathrm{mw}}_r(G)<f(r)\) for every \(r\in\mathbb{N}\) and \(G\in \mathcal{C}\).
In the definition of merge-width, the sequence of partitions \(\mathcal{P}_1\preccurlyeq \ldots\preccurlyeq \mathcal{P}_m\) may be equivalently required to be a maximal chain of partitions of \(V(G)\) (i.e. \(|\mathcal{P}_i| = |\mathcal{P}_{i+1}|+1\)). Indeed, given any merge sequence \((\mathcal{P}_1,R_1),\dots,(\mathcal{P}_m,R_m)\), one can transform it into a merge sequence whose sequence of partitions is a maximal chain of partitions as follows: if \(\mathcal{P}_i=\mathcal{P}_{i+1}\) for some \(1\leqslant i<m\), then we can drop the pair \((\mathcal{P}_{i+1},R_{i+1})\) in the sequence, and if \(\mathcal{P}_i\prec \mathcal{P}\prec \mathcal{P}_{i+1}\), then we may insert the pair \((\mathcal{P},R_{i+1})\) into the sequence. Those operations do not increase the radius-\(r\) width of the merge sequence.
VC-dimension and neighbourhood complexity
A set \(A\) of vertices of a graph \(G\) is shattered if \(\{N_G(v)\cap A\mid v\in V(G)\}=2^A\). The VC-dimension of \(G\) is the maximum size of a shattered subset of \(V(G)\). The neighbourhood complexity function (or shatter function) is defined by: \[\pi_G(m) \mathrel{\vcenter{:}}= \max_{\substack{A\subseteq V(G),\\|A|\leqslant m}}\left|\{N_G(v)\cap A\mid v\in V(G)\}\right|.\]
Note the trivial bound \(\pi_G(m) \leqslant 2^m\). The fundamental Sauer-Shelah-Perles lemma sauer72?, shelah72? states that this bound is polynomial in graphs of bounded VC-dimension.
Lemma 1 (Sauer-Shelah-Perles lemma). Let \(G\) be a graph of VC-dimension \(d\). Then \[\pi_G(m) \leqslant\mathcal{O}(m^d)\qquad\text{for all m\in\mathbb{N}.}\]
For graphs of bounded radius-\(2\) merge-width, Bonamy and Geniet bonamy2025chiboundedness? proved that the neighbourhood complexity function is linear.
Theorem 2. Any graph \(G\) with \(\mathop{\mathrm{mw}}_2(G)= k\) has neighbourhood complexity \[\pi_G(m)\leqslant k2^{k+2}\cdot m\qquad\text{for all m\in\mathbb{N}.}\]
Toruńczyk flip-width? showed that the VC-dimension of a graph \(G\) is linear in its radius-\(1\) flip-width. The proof can be easily adapted for radius-\(1\) merge-width (see also merge-width?).
Theorem 3. Any graph \(G\) satisfies \(\mathrm{VCdim}(G) \leqslant\mathcal{O}(\mathop{\mathrm{mw}}_1(G))\).
Duality
Our main result makes use of the following combinatorial notion. For a graph \(G\) and subsets of vertices \(X, Y \subseteq V(G)\), a set \(S_{XY}\) is dual for \((X,Y)\) if:
\(S_{XY} \subseteq X\) and \(S_{XY}\) dominates \(Y\), i.e. \(Y\subseteq N_G(S_{XY})\), or
\(S_{XY} \subseteq Y\) and \(S_{XY}\) anti-dominates \(X\), i.e. \(X\subseteq N_{\overline{G}}(S_{XY}).\)
A graph \(G\) is said to have a duality of order \(d\in \mathbb{N}\) if every pair of subsets of \(V(G)\) has a dual of size at most \(d\). The following, together with 3 shows that the duality of a graph \(G\) is linearly upper bounded by \(\mathop{\mathrm{mw}}_1(G)\).
Theorem 4 (flip-width?). Any graph \(G\) has a duality of order \(\mathcal{O}(\mathrm{VCdim}(G))\).
Linear Program formulation
The domination number and the 2-independence number can be defined as optima of the following linear programs:
Figure 1: 
.
Figure 2: 
.
The relaxations of these linear programs are obtained by replacing the constraints \(w(x)\in\{0,1\}\) by \(w(x)\in [0,1]\). The optima of the relaxations are called fractional domination
number and fractional 2-independence number, denoted by \(\gamma^*(G)\) and \(\alpha_2^*(G)\), respectively. Since the relaxed linear programs are duals, it follows that \(\gamma^*(G)=\alpha_2^*(G)\).
For Min Dominating Set we will use a result of Chan et al. CGKS12? (see also kupavskii?). They show a strong approximation result for instances of set covers with small shallow cell complexity (SCC). The latter can be upper bounded in terms of the shatter function of the set system, and adapting their result to our setting, we get the following.
Theorem 5 (CGKS12?). Fix a non-decreasing function \(f\colon\mathbb{N}\to \mathbb{N}_{+}\). Min Dominating Set admits a randomized polynomial time \(\mathcal{O}\left(\log f(m)\right)\)-approximation algorithm for graphs \(G\) with \(\pi_G(m)\leqslant m\cdot f(m)\) for all \(m\in\mathbb{N}\). Moreover \[\gamma(G) \leqslant\mathcal{O}\Big(\log f(m)\cdot \gamma^*(G)\Big).\]
Combining 5, which states that classes of bounded radius-\(2\) merge-width have linear neighborhood complexity bonamy2025chiboundedness?, with 2, we get that in such classes Min Dominating Set has bounded integrality gap.
Theorem 6 (follows from bonamy2025chiboundedness?, CGKS12?). For any graph \(G\) with \(\mathop{\mathrm{mw}}_2(G)\leqslant k\), we have \[\gamma(G) \leqslant\mathcal{O}(k\cdot \gamma^*(G)).\]
3 Approximation of Max Dist-\(2\) Independent Set↩︎
The constant-factor approximation for Max Dist-\(2\) Independent Set is a simple greedy algorithm, iteratively picking vertices whose ball of radius \(2\) in \(G\) have minimum weight according to a fractional 2-independence weight function. The crucial part is that these balls have weight bounded by a function of radius-\(2\) merge-width. Note that for a fractional 2-independence weight function \(w \colon V(G) \to [0,1]\) of \(G\), for every \(x\in V(G)\), we have \(w(N[x]) \leqslant 1\). This function is optimal if \(w^*(V(G))= \alpha_2^*(G)\).
Lemma 2. For any graph \(G\) of radius-\(2\) merge-width \(k\) and duality of order \(d\), for any fractional 2-independence weight function \(w^*\) of \(G\), there is a vertex \(x\in V(G)\) such that \[w^*(\mathrm{Ball}^2_G(x)) = O(kd^2).\]
Proof. Let \(G\) be a graph of duality of order \(d\) and radius-\(2\) merge-width \(k\) witnessed by a merge-sequence \((\mathcal{P}_1, R_1), \dots , (\mathcal{P}_n , R_n)\). Moreover, assume w.l.o.g. that \(|\mathcal{P}_i| = |\mathcal{P}_{i+1}|+1\). Let \(w^* : V(G) \to \mathbb{R}\) be any fractional 2-independence weight function of \(G\). Let \(i\) be the smallest index such that there is a part \(X\in \mathcal{P}_i\) with \(w^*(X)>d\). We will show that for any \(x\in X\), we have \(w^*(\mathrm{Ball}_G^2(x)) \leqslant\mathcal{O}(kd^2)\), hence proving the lemma.
By the choice of \(X\), since \(|\mathcal{P}_i| = |\mathcal{P}_{i+1}|+1\) we have \(w^*(X) \leqslant 2d\) and for any other part of \(P\in \mathcal{P}_i\), we have \(w^*(P) \leqslant d\). Define now the following sets: \[\begin{align} X_R &= N_{R_{i+1}}(x) &\qquad X_{R,R} &= N_{R_{i+1}}(X_R) &\qquad X_{R,B} &= N_G(X_R) \setminus X_{R,R} \\ X_B &= N_G(x) \setminus X_R &\qquad X_{B,R} &= N_{R_{i+1}}(X_B) &\qquad X_{B,B} &= N_G(X_B) \setminus X_{B,R} \end{align}\] Observe that \[\mathrm{Ball}_G^2(x) \subseteq \{x\}\cup X_R \cup X_B \cup X_{R,R} \cup X_{R,B} \cup X_{B,R} \cup X_{B,B},\] hence it is enough to bound the weight of each of these sets. First, since \(X_R \cup X_{R,R} \subseteq \mathrm{Ball}_{R_{i+1}}^2(x)\) by construction, these sets intersect at most \(k\) parts of \(\mathcal{P}_i\) and \(w^*(X_R \cup X_{R,R}) \leqslant(k+1)d\). Consider now \(X_{R,B}\). Let \(u\in X_{R,B}\); then there is some \(v \in N_G(u) \cap X_R\). Let \(P \in \mathcal{P}_i\restriction_{X_R}\) be such that \(v\in P\). Then \(P \subseteq N_G(u)\), as otherwise \(u\in N_{R_{i+1}}(P) \subseteq X_{R,R}\). Therefore, any vertex \(u\in X_{R,B}\) is complete to some part of \(\mathcal{P}_i\restriction_{X_R}\). Moreover for \(P,Q\subseteq V(G)\), if \(P\) and \(Q\) are complete to each other, then \(w^*(P)\leqslant 1\) and \(w^*(Q) \leqslant 1\). This implies that \(w^*(N_G(P) \cap X_{R,B}) \leqslant 1\) for every part \(P\in \mathcal{P}_i\restriction_{X_R}\), hence \(w^*(X_{R,B}) \leqslant k\).
To conclude the proof we will show that there exists \(S \subseteq X\) such that \(X_B \subseteq N_{R_{i+1}}(S)\) and \(|S| \leqslant d\). This implies that \(w^*((X_B \cup X_{B,R}) \setminus X) \leqslant kd^2\) since \(\mathrm{Ball}_{R_{i+1}}^2(S) \supseteq X_B \cup X_{B,R}\) intersect at most \(kd\) parts, each of them having weight at most \(d\). Furthermore, as \(|\mathcal{P}_i\restriction_{X_B}|\leqslant kd\), using the same arguments as for \(X_{R,B}\), we have \(w^*(X_{B,B}) \leqslant kd\). Recall that \(d\) is the order of duality of \(G\), that is for \(X_B\) and \(X\):
there is a set \(S\subseteq X_B\), \(|S|\leqslant d\), such that \(X \subseteq N_G(S)\), or
there is a set \(S\subseteq X\), \(|S|\leqslant d\), such that \(X_B \subseteq N_{\overline{G}}(S)\).
Since \(w^*(N_G(v)) \leqslant 1, v\in V(G)\) and \(w^*(X)> d\), there is no set \(S\subseteq V(G)\) of size at most \(d\) such that \(X \subseteq N_G(S)\). Hence there is a set \(S \subseteq X\) such that \(X_B \subseteq N_{\overline{G}}(S)\) and \(|S|\leqslant d\). Moreover, since \(N_{R_{i+1}}(x) \cap X_B = \varnothing\) and \(\mathcal{P}_i\) is homogeneous modulo \(R_{i+1}\), we have that for \(v\in X, u\in X_B\) if \(uv\notin E(G)\), then \(uv\in R_{i+1}\), hence \(X_B \subseteq N_{R_{i+1}}(S)\). ◻
The previous lemma can be adapted to obtain a bound that depends only on radius-\(3\) merge-width, which may be smaller in some instances.
Lemma 3. For any graph \(G\) of radius-\(3\) merge-width \(k\), for any fractional 2-independence weight function \(w^*\) of \(G\), there is a vertex \(x\in V(G)\) with \(w^*(x)>0\), such that \[w^*(\mathrm{Ball}^2_G(x)) = O(k).\]
Proof. The proof follows the same structure as that of 2. The main difference here is that we consider the first index such that a part has weight more than \(2\) instead of \(d\). Let \(X\) be the part of weight more than \(2\) (and less than \(4\)). The analysis for \(X_R\), \(X_{R,R}\) and \(X_{R,B}\) is the same.
The crucial observation is that every vertex in \(X_B\) share a common non-neighbour in \(X\) as \(w^*(X)>2\) and \(w^*(N_G[u])\leqslant 1\). As any non-edge between \(X_B\) and \(X\) is in \(R_{i+1}\), it follows that for every \(v \in X_B\), \(X_B \subseteq \mathrm{Ball}_{R_{i+1}}^2(v)\) and furthermore \(X_B \cup X_{B,R} \subseteq \mathrm{Ball}_{R_{i+1}}^3(v)\) and hence intersect \(k\) parts. The analysis of the weight for every other subset of \(\mathrm{Ball}_G^2(x)\) is the same as in the proof of 2. Therefore, as every part except \(X\) has weight less than \(2\), it follows that \(w^*(\mathrm{Ball}_G^2(x)) \leqslant\mathcal{O}(k)\). ◻
From 2 3 we can design a greedy constant-factor approximation algorithm for Max Dist-\(2\) Independent Set in graph classes of bounded radius-\(2\) merge-width.
Theorem 7. Max Dist-\(2\) Independent Set admits a \[\mathcal{O}(\min\{k_2d^2,k_3\})\text{-approximation}\] for graphs \(G\) where \(k_2\geqslant\mathop{\mathrm{mw}}_2(G)\), \(k_3\geqslant\mathop{\mathrm{mw}}_3(G)\) and \(d\) is the order of duality of \(G\). Moreover, \(\alpha_2^*(G) \leqslant\mathcal{O}(\min\{k_2d^2,k_3\}\cdot \alpha_2(G)\big).\)
Proof. Let \(w^*\) be an optimal fractional 2-independence weight function of \(G\) obtained by solving the relaxation of the linear program for \(\mathrm{\small Max Dist-2 Independent Set}\). We will construct a distance-\(2\) independent set\(I\) of \(G\) by the following procedure: while \(w^*(V(G))>0\), pick a vertex \(x\in V(G)\) with \(w^*(x)>0\) such that \(w^*(\mathrm{Ball}_G^2(x))\) is minimum; add \(x\) to \(I\) and set \(w^*(y)\) to \(0\) for every \(y\in \mathrm{Ball}_G^2(x)\).
First, note that \(I\) is a distance-\(2\) independent set of \(G\), indeed, whenever a vertex is picked, its current weight is non-zero, this implies that its distance to vertices previously added to \(I\) is at least \(3\). Moreover, whenever a vertex is added to \(I\), the total weight of \(G\) is decreased by at most \(O(\min\{k_2d^2,k_3\})\) by 2 3. Hence, \(\mathcal{O}(|I|\cdot \min\{k_2d^2,k_3\}) \geqslant\alpha_2^*\), concluding the proof. ◻
7 shows that in graph class of bounded radius-\(2\) merge-width, integrality gap for Min Dominating Set is bounded, since in any graph the duality of order is bounded by the radius-\(1\) merge-width (3 4). Since \(\gamma^*(G) = \alpha_2^*(G)\), it follows from 6 7 that the domination-to-2-independence ratio is bounded in graph of bounded radius-\(2\) merge-width.
Corollary 1. For any graph \(G\) of duality of order \(d\) and with \(\mathop{\mathrm{mw}}_2(G)\leqslant k\), we have \[\gamma(G) \leqslant\mathcal{O}(k^2d^2 \cdot \alpha_2(G)).\]
The twin-width of a graph \(G\), denoted by \(\mathop{\mathrm{tww}}(G)\), is the minimum integer \(k\) such that there exists a maximal chain \[\mathcal{P}_1\prec \mathcal{P}_2\prec \dots\prec \mathcal{P}_n\] of partitions of \(V(G)\) (called a contraction sequence in this context) such that for every \(t\in[n]\), every part \(P\in\mathcal{P}_t\) is non-homogeneous to at most \(k\) parts of \(\mathcal{P}_t\setminus \{P\}\). We can adapt the approximation algorithm of 7 to the setting of twin-width and get an improvement of the approximation factor over the one for Max Dist-\(2\) Independent Set of Bonnet et al. BGKTW24?. Moreover, their approximation required a contraction sequence given as part of the input. This also reaches the \(\mathcal{O}(\mathop{\mathrm{tww}}(G)^2)\) integrality gap implied by Bonamy et al. BCGY25?.
Corollary 2. Max Dist-\(2\) Independent Set admits a \(\mathcal{O}(k^2)\)-approximation for graphs \(G\) where \(\mathop{\mathrm{tww}}(G)\leqslant k\).
Proof. Let \(\mathcal{P}_1\prec\ldots\prec\mathcal{P}_n\) be a contraction sequence witnessing that \(\mathop{\mathrm{tww}}(G)\leqslant k\). Observe that whenever a part \(P\) has weight more than one, no vertex of \(G\) can be complete to it. In particular, all vertices of \(G\) fully adjacent to this part have to be in one of the at most \(k\) parts non-homogeneous with \(P\). It follows that for a step \(\mathcal{P}_i\) of a contraction sequence, if only one part \(X\) has weight more than one, then \(w^*(\mathrm{Ball}_G^2(x)) \leqslant\mathcal{O}(k^2)\) for any \(x \in X\), and the conclusion follows from the algorithm defined in 7.
More precisely, let \(\mathcal{X}_R\) be the set of parts non-homogeneous with \(X\); \(\mathcal{X}_{R,R}\) the set of parts non-homogeneous with at least one part of \(\mathcal{X}_R\); and \(X_{R,B}\) is the set of vertices fully adjacent to at least one part of \(\mathcal{X}_R\). Then it is clear that \(\mathrm{Ball}_G^2(x) \subseteq P\cup \bigcup \mathcal{X}_R \cup \bigcup \mathcal{X}_{R,R} \cup X_{R,B}\). Since \(|\mathcal{X}_{R,R}| \leqslant k^2\) and that for each part \(\mathcal{X}_R\) the weight of the vertices fully adjacent to it is at most one, it follows that \(w^*(\mathrm{Ball}_G^2(x)) \leqslant\mathcal{O}(k^2)\). ◻
4 Related problems and open questions↩︎
Natural generalisations of the two problems investigated in this paper are Min Dist-\(r\) Dominating Set and Max Dist-\(2r\) Independent Set. In these problems we look respectively for a minimum-size set dominating every vertex at distance at most \(r\), and a maximum-size set such that every vertex is at distance at most \(2r\) from at most one vertex from this set. For \(r\in\mathbb{N}\), the \(r\)-power \(G^r\) of a graph \(G\) is the graph obtained by adding an edge between every pair of vertices at distance at most \(r\). It is straightforward to see that solving Min Dominating Set on \(G^r\) provides a solution of Min Dist-\(r\) Dominating Set on \(G\), and similarly for the independent set variant.
Moreover, it is known that the radius-\(2\) merge-width of \(G^r\) depends only on the radius-\(f(r)\) merge-width of \(G\) for some function \(f\) merge-width?1. Therefore, Min Dist-\(r\) Dominating Set and Max Dist-\(2r\) Independent Set can be constant-factor approximated and have bounded integrality gap in graphs of bounded radius-\(f(r)\) merge-width.
It can be asked if the results of this paper can be extended to broader classes of graphs, for example the ones of bounded radius-\(1\) merge-width. Dvorák Dvorak13? observed that there are graphs that are \(3\)-degenerate and for which the domination-to-2-independence ratio is unbounded. Since \(k\)-degenerate graphs have radius-\(1\) merge-width at most \(k+2\) merge-width?, the domination-to-2-independence ratio is also unbounded in graphs of bounded radius-\(1\) merge-width. In particular, the counter-example used shows that the integrality gap Max Dist-\(2\) Independent Set in \(3\)-degenerate graphs can be unbounded. While this does not rule out a constant-factor approximation for Max Dist-\(2\) Independent Set in graphs of bounded radius-\(1\) merge-width, it seems unlikely. However, this leaves the following question for Min Dominating Set.
Does Min Dominating Set admit a constant-factor approximation in graphs of bounded radius-\(1\) merge-width? Does it have bounded integrality gap?
Chan et al. CGKS12? show that Min Dominating Set admits a constant factor approximation in graphs of linear neighbourhood complexity (5). Our main result extends the approximability at constant factor of Max Dist-\(2\) Independent Set to graphs of bounded radius-\(2\) merge-width, we ask if this can be pushed further.
Does Max Dist-\(2\) Independent Set admit a constant-factor approximation in graphs of linear neighbourhood complexity?
This theorem states that graph classes of bounded merge-width are closed under first-order interpretation. The graph \(G^r\) can be interpreted from \(G\) by a first-order formula \(\varphi(u,v)\) that is satisfied if \(\mathrm{dist}_G(u,v) \leqslant r\).↩︎