2025/10/22 by Xujin Chen, Chen, Xujin, Xiaodong Hu +5
Computer Science · Mathematics · #05C85 #68W25 #90C27 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2510.19191
openalex publication_date 2025/10/22 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Let V be a finite set of n elements, f: 2V → ℝ+ be a nonnegative monotone supermodular function, and k be a positive integer no greater than n. This paper addresses the problem of maximizing f(S) over all subsets S ⊆ V subject to the cardinality constraint |S| = k or |S|≤ k. Let r be a constant integer. The function f is assumed to be \em r-decomposable, meaning there exist m (≥1) subsets V1, …, Vm of V, each with a cardinality at most r, and a corresponding set of nonnegative supermodular functions fi : 2Vi → ℝ+, i=1,…,m such that f(S) =∑i=1m fi(S ∩ Vi) holds for each S ⊆ V. Given r as an input, we present a polynomial-time O(n(r-1)/2)-approximation algorithm for this maximization problem, which does not require prior knowledge of the specific decomposition. When the decomposition (Vi,fi)i=1m is known, an additional connectivity requirement is introduced to the problem. Let G be the graph with vertex set V and edge set ∪i=1m \uv:u,v∈ Vi,u≠ v\. The cardinality constrained solution set S is required to induce a connected subgraph in G. This model generalizes the well-known problem of finding the densest connected k-subgraph. We propose a polynomial time O(n(r-1)/2)-approximation algorithm for this generalization. Notably, this algorithm gives an O(n1/2)-approximation for the densest connected k-subgraph problem, improving upon the previous best-known approximation ratio of O(n2/3).