A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization

Connected Submodular Maximization (CSM) is a graph problem with important applications to wireless network deployment, path planning, epidemic outbreaks, and cancer genome studies. In CSM, we are given a graph 𝐺, a non-negative monotone submodular function 𝑓 on subsets of the vertex set of 𝐺, and an integer 𝑘. The goal is to select a tree in 𝐺, with 𝑘 edges, whose vertex set maximizes 𝑓. We also study the more general Directed and Directed Rooted variants of CSM (DCSM and DRCSM respectively). In both variants, 𝐺 is directed and the solution must be an out-tree in 𝐺, with 𝑘 edges, whose vertex set maximizes 𝑓; DRCSM further specifies a vertex to be the root of the selected out-tree. For CSM, several previous works have proposed polynomial time approximation algorithms; the state-of-the-art polynomial time algorithm achieves a Ω( 1 √ 𝑘 )-approximation. We can also parameterize the approximation factor by the radius of the optimal solution, denoted by 𝑟; the state-of-the-art polynomial time algorithm achieves a Ω(1 𝑟 )-approximation. In this paper, we improve on the state-of-the-art approximation factor for CSM with respect to 𝑟 as well as 𝑘, noting that 𝑟 ≤ 𝑘. We propose a polynomial time framework that, for (Directed) CSM, achieves a Ω(𝜀3 𝑟𝜀 )-approximation for every constant 𝜀 ∈ (0, 1]. For DRCSM, our framework achieves a Ω(𝛿𝜀3 𝑟𝜀 )-approximation that violates the size constraint by at most a factor of 1 + 𝛿 for every 𝛿 ∈ [1 𝑘, 1]. A key component of our framework is GreedyRadius, an algorithm for DRCSM that outputs a bicriteria approximation, i. e. , an approximate solution that violates the size constraint by at most some factor. GreedyRadius takes an algorithm with a bicriteria approximation factor in terms of𝑘 and outputs a solution This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), C. Amato, L. Dennis, V. Mascardi, J. Thangarajah (eds.), May 25 – 29, 2026, Paphos, Cyprus. © 2026 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). https: //doi. org/10. 65109/IPZQ7320 with the same bicriteria approximation factor (up to constants) in termsof𝑟. Moreover, touseasasubroutineforDRCSM, wepropose the algorithm RecApprox-𝑑, which achieves a 1 𝑑+1-approximation that violates the size constraint by at most a factor of (𝑑 + 1)2𝑘 1 𝑑. RecApprox-𝑑 uses a recursive greedy strategy, with𝑑 denoting the number of levels of recursion used. This enables the dependence on 𝜀 in the approximation factors of our overall framework.

Authors

• Philip Cervenjak School of Computing and Information Systems, University of Melbourne
• Junhao Gan School of Computing and Information Systems, University of Melbourne
• Naonori Kakimura Department of Mathematics, Keio University
• Seeun William Umboh School of Computing and Information Systems, The University of Melbourne & ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)
• Anthony Wirth School of Computer Science, The University of Sydney & School of Computing and Information Systems, The University of Melbourne

Keywords

• Combinatorial Optimization
• Submodular Maximization
• Network Design
• Approximation Algorithms
• Graph Algorithms