EE Seminar: DYNAMIC DOMINATING SET IN UNIFORMLY SPARSE GRAPHS

Electrical Engineering Systems Seminar

Speaker: Anton Bukov

M.Sc. student under the supervision of Prof. Shay Solomon

Sunday, 14^th May 2026, at 15:00

Room 011, Kitot Building, Faculty of Engineering

DYNAMIC DOMINATING SET IN UNIFORMLY SPARSE GRAPHS

Abstract

In the dynamic minimum dominating set (MDS) problem, the goal is to efficiently maintain an approximate MDS in an n-vertex graph with vertex costs in 1/C,1 undergoing edge insertions and deletions. In STACS'19 it was shown that an Ologn-approximate MDS can be maintained in unweighted graphs with OΔ⋅logn update time, where Δ is an upper bound on the maximum degree throughout the update sequence, and in STOC'23 this was extended to weighted graphs and improves the approximation guarantee to 1+ϵlnΔ.

Is it possible to achieve polylogn update time without any dependence on Δ, for any nontrivial graph family? This basic question has remained open even in forests and even for unweighted instances. The arboricity α=αG of a graph G is the minimum number of edge-disjoint forests whose union is G, and is a standard measure of sparsity. While α is bounded by Δ in any graph, various real-world graph families exhibit a significant gap between α and Δ.

In this work, we show that one can maintain an Oα-approximate MDS with update time Oα⋅logCn, for dynamic graphs whose arboricity is bounded by α throughout the update sequence. This replaces the dependence on Δ in prior update bounds with α, while also improving the approximation guarantee for bounded-arboricity graphs. In particular, for any graph family of constant arboricity, such as planar graphs, bounded treewidth graphs, and more generally graphs excluding a fixed minor, our algorithm gives an O1-approximation with OlogCn update time. To achieve this result, our algorithm departs from prior greedy-based approaches, relying instead on the primal-dual framework and new structural insights specific to bounded arboricity graphs.

  -סמינר זה ייחשב כסמינר שמיעה לתלמידי תואר שני ושלישי-

This Seminar Is Considered A Hearing Seminar For Msc/Phd Students-

הרישום לסמינר יבוצע בתחילת הסמינר באמצעות סריקת הברקוד למודל (יש להיכנס לפני כן למודל,  לא באמצעות האפליקציה)

Registration to the seminar is done at the beginning of the seminar by scanning the barcode for the Moodle (Please enter ahead to the Moodle, NOT by application)