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 [Niklas Hjuler et al., 2019] it was shown that an O(log n)-approximate MDS can be maintained in unweighted graphs with O(Δ ⋅ log n) update time, where Δ is an upper bound on the maximum degree throughout the update sequence, and in STOC'23 [Solomon and Uzrad, 2023] this was extended to weighted graphs and improves the approximation guarantee to (1+ε)ln Δ. Is it possible to achieve poly(log n) 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(α⋅log(Cn)), 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 O(1)-approximation with O(log (Cn)) 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.

The dynamic set cover problem has been subject to extensive research since the pioneering works of [BHI, ICALP’15] and [GKKP17, STOC’17]. The input is a set system (U, S ) on a fixed collection S of sets and a dynamic universe of elements, where each element appears in a most f sets and the cost of each set lies in the range [1/C, 1]; the ultimate goal is to maintain a set cover under insertions and deletions of elements, with optimal bounds on both the approximation factor and the update time.

We present a study of a few graph-based problems motivated by fair allocation of resources in a social network. The central role in the paper is played by the following problem: What is the largest number of items we can allocate to the agents in the given social network so that each agent hides at most one item and overall at most k items are hidden, and no one envies its neighbors? We show that the problem admits an XP algorithm and is W[1]-hard parameterized by k . Moreover, within the running time, we can identify agents that should hide its items and can construct an ordering in which agents should pick items into its bundles to get a desired allocation. Besides this problem, we also consider the existence and verification versions of this problem. In the existence problem, we are given a social network, valuations, a budget, and the goal is to find an allocation without envy. In the verification problem, we are additionally given an allocation, and the goal is to determine if the allocation satisfies the required property.