An Approximation Algorithm for the Connected Maximum Coverage Problem in Directed Graphs
Gianlorenzo D’Angelo, Esmaeil Delfaraz · 2025
Read An Approximation Algorithm for the Connected Maximum Coverage Problem in Directed Graphs by Gianlorenzo D’Angelo, Esmaeil Delfaraz (2025) 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-2504-07725.txt.
Introduction
Gianlorenzo D'Angelo and Esmaeil Delfaraz give an approximation algorithm for a coverage problem on directed graphs, in work from 2025. The task is to pick a set of nodes that forms a tree from a root, stays within a budget, and covers as much prize value as possible. Each set carries its own cost, and each covered item gives its own prize.
Their algorithm guarantees a stated fraction of the best possible prize, while allowing the budget to be exceeded by a small set factor. The guarantee improves on what was known for a related Steiner tree problem on directed graphs, which appears as a special case. Approximation algorithms matter here because exact solutions are out of reach for large graphs. The result sharpens the known trade-off between cost and coverage.
Catalog record
| CREATOR | Gianlorenzo D’Angelo, Esmaeil Delfaraz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-07725
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Approximation Algorithm for the Connected Maximum Coverage Problem in Directed Graphs Gianlorenzo D’Angelo, Esmaeil Delfaraz Abstract In the Directed rooted Connected Budgeted maximum Coverage problem ( DCBC ), we are given a collection of subsets 𝒮 \mathcal{S} , defined over a ground set X X , and a directed graph G = ( V , E ) G=(V,E) , where each node is associated with a set of 𝒮 \mathcal{S} . Each set in 𝒮 \mathcal{S} has a different cost and each element of X X gives a different prize. The goal is to find a subcollection 𝒮 ′ ⊆ 𝒮 \mathcal{S}^{\prime}\subseteq\mathcal{S} such that 𝒮 ′ \mathcal{S}^{\prime} induces an out-tree rooted at a given node, the total cost of the sets in 𝒮 ′ \mathcal{S}^{\prime} does not exceed a budget B B , and the total prize of the elements covered by 𝒮 ′ \mathcal{S}^{\prime} is maximized. In this paper, we provide an algorithm for DCBC that guarantees an approximation ratio of O ( | V | log 2 | X | ϵ 2 ) O\left(\frac{\sqrt{|V|}\log^{2}|X|}{\epsilon^{2}}\right) , with a budget violation of a factor 1 + ϵ 1+\epsilon , where ϵ ∈ ( 0 , 1 ] \epsilon\in(0,1] . Our algorithm also implies an improved approximation factor for the budgeted node-weighted Steiner problem in directed graphs, a particular case of DCBC where the prize function is additive, for which we improve from O ( 1 ϵ 2 | V | 2 / 3 log | V | ) O\left(\frac{1}{\epsilon^{2}}|V|^{2/3}\log|V|\right) to O ( 1 ϵ 2 | V | 1 / 2 log 2 | V | ) O\left(\frac{1}{\epsilon^{2}}|V|^{1/2}\log^{2}|V|\right) . 1 Introduction In the budgeted maximum coverage problem, we are given a ground set X of elements with associated prizes, a collection \mathcal{S} of subsets of X with associated costs, and a budget B . The aim is to find a subcollection \mathcal{S}^{\prime}\subseteq\mathcal{S} such that the total cost of the sets in \mathcal{S}^{\prime} does not exceed B and the total prize of the elements covered by \mathcal{S}^{\prime} (i.e., \bigcup_{S\in\mathcal{S}^{\prime}}S ) is maximized [ 25 ] . The Connected Budgeted maximum Coverage problem ( CBC ) is a generalization of the budgeted maximum coverage problem in which the sets in \mathcal{S} are associated with the nodes of a graph G=(V,A) and the subcollection \mathcal{S}^{\prime} must induce a connected subgraph T in G . The CBC problem is motivated by several applications in multi-agent path planning, wireless sensor networks, and bioinformatics. Consider, for example, the exploration of a region through an Unmanned Aerial Vehicle that can take pictures of an area close to its current location. In this scenario, the areas to be explored correspond to the elements in X , and the nodes of the graph correspond to the locations that the vehicle can reach. Computing a connected maximum coverage corresponds to finding a small set of connected locations that allow the exploration of the largest possible area [ 5 , 42 ] . Another application is the deployment of wireless sensor networks in a scenario where each sensor is able to detect a set of target points in its sensing range, and one wants to deploy a bounded set of connected sensors that detects the largest number of target points [ 44 ] . Here, the sensor network corresponds to the graph G , and the target points to the elements X . Vandin et al. [ 41 ] studied CBC motivated by the detection of driver mutations in protein-to-protein interaction networks. In these networks, a node represents a protein, and an edge represents an interaction between two proteins. Each protein is associated with a gene mutation and a set of cancer patients who are affected by such mutation. It is widely believed that cancer is associated with a connected series of mutations in these networks, called pathways [ 20 ] . Therefore, finding a connected set of B nodes with maximum coverage corresponds to finding the B connected mutations that affect the largest number of cancer patients. Variants of CBC find application in network surveillance [ 32 ] , recovery of power networks [ 19 ] , and data acquisition [ 43 ] . The Directed rooted Connected Budgeted maximum Coverage problem ( DCBC ) is a generalization of CBC to directed graphs, where the aim is to find a rooted out-tree maximizing the prizes of covered elements and respecting a budget constraint. Besides the same applications as CBC in the cases where the underlying network is directed, the DCBC problem has specific motivating application scenarios in facility location, epidemiology, and computational social choice. Consider a large warehouse from which goods are delivered through a road network to smaller warehouses or retail shops that serve a set of customers. Here, the graph models the (directed) road network; the ground set represents the set of customers; and shops, represented as nodes in the graph, are associated with the set of customers that they may serve. In order to maximize the number of customers that can be served at a given delivery cost, one needs to compute an out-tree, rooted at the node representing the warehouse, that maximizes the overall number of covered customers and satisfies the budget constraint. Connectivity is required because goods are distributed from the main warehouse to the open shops via a directed road network. Vehicles departing from the warehouse (root) reach the retail shops (selected nodes) via directed paths. Other applications require computing rooted out-trees in directed graphs in order to reconstruct epidemic outbreaks [ 33 , 39 ] or to maximize the voting power of a voter in liquid democracy [ 9 ] . Related work Problems CBC and DCBC have already been studied under the lens of approximation algorithms. However, the state-of-the-art algorithms achieve approximation ratios that are, in the worst case, linear in |V| [ 23 , 36 , 41 ] or depend on the budget B [ 23 , 8 ] , and, in some cases, only work under specific assumptions [ 41 , 23 , 36 ] . Vandin et al. [ 41 ] considered the special case of CBC where the cost is equal for all nodes and provided a c\rho -approximation, where c=(2e-1)/(e-1) and \rho is the radius of the connected subgraph induced by an optimal solution. Hochbaum and Rao [ 23 ] improved this bound to \min\{((1-1/e)(1/\rho-1/B))^{-1},B\} . This latter result also holds true in the more general case in which the prize function is a monotone submodular function of the set of nodes in the graph. Still, the cost function is assumed to be constant for all nodes. Ran et al. [ 36 ] considered CBC without restrictions on the cost function but under the assumption that if two sets in \mathcal{S} have a non-empty intersection, then the corresponding nodes in G must be adjacent. In this setting, they provided an O(\Delta\log{|V|}) -approximation algorithm, where \Delta is the maximum degree of G . D’Angelo et al. [ 8 ] improved this result to O(\log{|V|}) under the same assumption. Moreover, they gave an O(\sqrt{B}) -approximation algorithm for DCBC . In the worst case, \rho=\Omega(|V|) and \Delta=\Omega(|V|) ,