Stable Approximation Algorithms for Dominating Set and Independent Set

Mark de Berg, Arpan Sadhukhan, Frits Spieksma · 2024

Read Stable Approximation Algorithms for Dominating Set and Independent Set by Mark de Berg, Arpan Sadhukhan, Frits Spieksma (2024) 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-2412-13358.txt.

Introduction

Mark de Berg, Arpan Sadhukhan, and Frits Spieksma study the tradeoff between stability and accuracy in graph choices as vertices stream in. Two tasks rule the study. One is a dominating set, a guard set that sees all vertices. The other is an independent set, with no two chosen vertices linked. A dynamic method is stable if each new vertex costs it only a few swaps. Their 2024 work maps what stability can buy.

For both tasks, near-perfect accuracy forces huge swap counts, on the scale of the whole graph, even on bipartite graphs of low degree. When arrival degree is capped, stable methods do far better. A method with one swap per step reaches a modest ratio, and one with three swaps does leaner still. A method with swaps on the scale of the cap reaches a flat ratio. Independent set methods extend to full dynamic graphs as well.

Catalog record

CREATORMark de Berg, Arpan Sadhukhan, Frits Spieksma
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-13358

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stable Approximation Algorithms for Dominating Set and Independent Set Mark de Berg, Arpan Sadhukhan, Frits Spieksma Abstract We study Dominating Set and Independent Set for dynamic graphs in the vertex-arrival model. We say that a dynamic algorithm for one of these problems is k k -stable when it makes at most k k changes to its output independent set or dominating set upon the arrival of each vertex. We study trade-offs between the stability parameter k k of the algorithm and the approximation ratio it achieves. We obtain the following results. • We show that there is a constant ε ∗ > 0 \varepsilon^{*}>0 such that any dynamic ( 1 + ε ∗ ) (1+\varepsilon^{*}) -approximation algorithm for Dominating Set has stability parameter Ω ⁡ ( n ) \Omega(n) , even for bipartite graphs of maximum degree 4. • We present algorithms with very small stability parameters for Dominating Set in the setting where the arrival degree of each vertex is upper bounded by d d . In particular, we give a 1 1 -stable ( d + 1 ) 2 (d+1)^{2} -approximation algorithm, a 3 3 -stable ( 9 ​ d / 2 ) (9d/2) -approximation algorithm, and an O ⁡ ( d ) O(d) -stable O ⁡ ( 1 ) O(1) -approximation algorithm. • We show that there is a constant ε ∗ > 0 \varepsilon^{*}>0 such that any dynamic ( 1 + ε ∗ ) (1+\varepsilon^{*}) -approximation algorithm for Independent Set has stability parameter Ω ⁡ ( n ) \Omega(n) , even for bipartite graphs of maximum degree 3. • Finally, we present a 2-stable O ⁡ ( d ) O(d) -approximation algorithm for Independent Set , in the setting where the average degree of the graph is upper bounded by some constant d d at all times. We extend this latter algorithm to the fully dynamic model where vertices can also be deleted, achieving a 6-stable O ⁡ ( d ) O(d) -approximation algorithm. Department of Mathematics and Computer Science, TU Eindhoven, the [email protected] Department of Mathematics and Computer Science, TU Eindhoven, the [email protected] Department of Mathematics and Computer Science, TU Eindhoven, the [email protected] ccs Theory of computation Design and analysis of algorithms keywords Dynamic algorithms, approximation algorithms, stability, dominating set, independent set † † funding: MdB, AS, and FS are supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. † † runningauthor: M. de Berg, A. Sadhukhan and F. Spieksma † † copyright: Mark de Berg and Arpan Sadhukhan and Frits Spieksma 1 Introduction A dominating set in a simple, undirected graph G=(V,E) is a subset D\subset V such that each vertex in V is either a neighbor of a vertex in D , or it is in D itself. An independent set is a set of vertices I\subset V such that no two vertices in I are neighbors. Dominating Set (the problem of finding a minimum-size dominating set) and Independent Set (the problem of finding a maximum-size independent set) are fundamental problems in algorithmic graph theory. They have numerous applications and served as prototypical problems for many algorithmic paradigms. We are interested in Dominating Set and Independent Set in a dynamic setting, where the graph G changes over time. In particular, we consider the well-known vertex-arrival model . Here one starts with an empty graph G(0) , and new vertices arrive one by one, along with their edges to previously arrived vertices. In this way, we obtain a sequence of graphs G(t) , for t=0,1,2,\ldots . Our algorithm is then required to maintain a valid solution—a dominating set, or an independent set—at all times. In the setting we have in mind, computing a new solution is not the bottleneck, but each change to the solution (adding or deleting a vertex from the solution) is expensive. Of course we also want that the maintained solution has a good approximation ratio. To formalize this, and following De Berg et al. [ 13 ] , we say that a dynamic algorithm is a k -stable \rho -approximation algorithm if, upon the arrival of each vertex, the number of changes (vertex additions or removals) to the solution is at most k and the solution is a \rho -approximation at all times. In this framework, we study trade-offs between the stability parameter k and the approximation ratio that can be achieved. Ideally, we would like to have a so-called stable approximation scheme (SAS) : an algorithm that, for any given yet fixed parameter \varepsilon>0 is k_{\varepsilon} -stable and gives a (1+\varepsilon) approximation algorithm, where k_{\varepsilon} only depends on \varepsilon and not on the size of the current instance. (There is an intimate relationship between local-search PTASs and SASs; we come back to this issue in Section 2 .) The vertex-arrival model is a standard model for online graph algorithms, and our stability framework is closely related to online algorithms with bounded recourse. However, there are two important differences. First, computation time is free in our framework—for instance, the algorithm may decide to compute an optimal solution in exponential time upon each insertion—while in online algorithms with bounded recourse the update time is typically taken into account. Thus we can fully focus on the trade-off between stability and approximation ratio. Secondly, we consider the approximation ratio of the solution, while in online algorithm one typically considers the competitive ratio. Thus we compare the quality of our solution at time t to the static optimum , which is simply the optimum for the graph G(t) . A competitive analysis, one the other hand, compares the quality of the solution at time t to the offline optimum : the best solution for G(t) that can be computed by a dynamic algorithm that knows the sequence G(0),\ldots,G(t) in advance but must still process the sequence with bounded recourse. See also the discussion in the paper by Boyar et al. [ 7 ] . Thus approximation ratio is a much stronger notion that competitive ratio. As a case in point, consider Dominating Set , and suppose that n singleton vertices arrive, followed by a single vertex with edges to all previous ones. Then the static optimum for the final graph is 1, while the offline optimum with bounded recourse is \Omega(n) . Related work. We now review some of the most relevant existing literature on the online version of our problems. (Borodin and El-Yaniv [ 6 ] give a general introduction to online computation.) The classical online model, where a vertex that has been added to the dominating set or to the independent set, can never be removed from it—that is, the no-recourse setting—is e.g. considered by King and Tzeng [ 19 ] and Lipton and Tomkins [ 21 ] . They show that already for the special case of interval graphs no online algorithm has constant competitive ratio; see also De et al. [ 10 ] , who study these two problems for geometric intersection graphs. For Dominating Set in the vertex-arrival model, Boyar et al. [ 7 ] give online algorithms with bounded competitive ratio for trees, bipartite graphs, bounded degree graphs, and planar graphs. They actually analyze both the competitive ratio and the approximation ratio (which, as discussed earlier, can

Read the complete text