Many practical graph selection tasks ask for a set of $k$ nodes that covers as much of the graph as possible while forming one connected group. Examples include placing monitors on a network that must talk to each other and seeding a campaign in one contiguous community. Without the connectivity requirement, the textbook greedy algorithm is the right tool: adding the node with the largest gain each round gets within a factor $1-1/e$ of optimal. With the requirement, single-node greedy breaks. It cannot cross a stretch of low-value nodes to reach a high-value region, because each individual step along the way looks worthless.
This proposal keeps the greedy loop but lets each greedy step add a whole connected piece of up to $b$ nodes. It finds the best such piece exactly using dynamic programming over a tree decomposition. A tree decomposition arranges the graph into a tree of small overlapping vertex groups, called bags, so that each bag separates the graph above it from the graph below it. Large real graphs usually have huge treewidth, meaning no decomposition with small bags exists for the whole graph. Many of them still have a sparse, tree-like periphery hanging off a small core of hubs. The method runs the exact search on that periphery and handles the hubs with ordinary greedy steps. The step size $b$ then becomes a single dial between plain greedy ($b=1$) and exact optimization on the periphery ($b=k$).
Core Claim
The objective is weighted neighborhood coverage, $f(S)=\sum_{v} w_v\,[N[v]\cap S\neq\emptyset]$. Here $N[v]$ is $v$ together with its neighbors, and $w_v\ge 0$ is the value of covering $v$. We maximize $f$ subject to $|S|\le k$ and the requirement that $S$ induce a connected subgraph. This $f$ is monotone submodular: adding nodes never hurts, and each added node helps less as the set grows. The objective has one property that general submodular functions lack. Whether a vertex is covered depends only on its neighbors, and every edge lies inside some bag. The marginal gain of a candidate piece $A$ given the current set $S$ can therefore be computed exactly inside a tree-decomposition dynamic program with a few states per bag vertex (in $A$, already covered, not yet covered).
Connectivity to $S$ adds one more requirement. We contract $S$ into a single root vertex placed in every bag, which raises the width by one. We then track connectivity with partition states when width is small, or with the Cut & Count parity technique of Nederlof et al., which reduces the cost of global connectivity constraints to single-exponential in width. Each round selects
$$A_i=\arg\max_{A:\ |A|\le b,\ S_{i-1}\cup A \text{ connected}} \frac{f(S_{i-1}\cup A)-f(S_{i-1})}{|A|},$$
computed exactly by indexing the dynamic-programming table by piece size.
The claim is that this block-greedy method finds substantially better connected solutions than single-node greedy with shortest-path connectors on graphs with a low-width periphery. It should also run at a cost close to linear in the periphery size, because each periphery component is solved independently and only recomputed when a new selection touches it.
On the theory side, we follow the error recurrence used in Maximizing the spread of influence through a social network. If every round admits a piece whose ratio is at least $\frac{1}{\gamma_b k}\,(f(S^*)-f(S_{i-1}))$, where $S^*$ is the optimum, then $f(S_k)\ge(1-e^{-1/\gamma_b})f(S^*)$. The parameter $\gamma_b\ge 1$ measures how poorly the optimum splits into attached connected pieces of size at most $b$. We aim to bound $\gamma_b$ structurally, for example by the distance between the optimum and the current set relative to $b$. We will also report it as a per-instance certificate. We do not claim a constant factor for all graphs.
Relation to Prior Work
Three papers use tree-decomposition dynamic programming inside iterative improvement. They supply the method but not the setting.
Local Search: Is Brute-Force Avoidable? finds improving $k$-swaps by dynamic programming on low-treewidth balls in planar-like graphs. It proves the search is W[1]-hard on 3-degenerate graphs, which rules out running its approach on general large graphs. Our approach instead restricts the dynamic program to the part of the graph that is actually low-width.
Improving TSP Tours Using Dynamic Programming over Tree Decompositions decomposes a small dependence graph of a tour move rather than the input graph. It targets permutations rather than coverage and reports no experiments.
On Approximate Non-submodular Minimization via Tree-Structured Supermodularity pairs exact dynamic programming on trees (width 1) with greedy scheduling for minimization on image grids. It finds this more robust than continuous relaxation, which it reports was slower and sometimes failed to converge on larger instances. We generalize to width above 1, to maximization under cardinality, and to non-grid networks.
Prize-collecting Network Design on Planar Graphs uses exact bounded-treewidth dynamic programming with submodular penalties. It depends on planarity, and it shows prize-collecting Steiner forest is APX-hard even at treewidth 2. That result warns that connectivity plus penalties can stay hard at tiny width. Our objective avoids the forest-demand structure behind that hardness.
Two scalability works motivate the core/periphery split. Core-Fringe GNN separates hubs from their local neighborhoods for message passing but never bounds the width of the fringe. RWDISK treats hubs specially to make random walks disk-friendly. We borrow the split and turn it into a width guarantee for the dynamic program.
SGPO cuts greedy evaluation cost by pruning a learned submodularity graph. It settles for logarithmic guarantees and has a heavy polynomial bound. We reduce evaluation cost through structure instead of pruning.
Research Program
The pipeline has three stages.
First, the core/periphery split. Peel off the $c$ highest-degree vertices, or a small separator found by a greedy degree/fill heuristic, and split the remainder into components. For each component $C$, compute a heuristic tree decomposition (min-degree or min-fill). The dynamic program needs only a valid decomposition, not an optimal one, so NP-hardness of exact treewidth does not matter. The few unselected core vertices adjacent to $C$ are added to every bag of $C$, so their coverage is counted exactly rather than double-counted across components. We measure the resulting widths.
Second, the outer loop. Each round considers two kinds of candidates: single core vertices, scored by ordinary greedy with lazy evaluation, and the best piece in each periphery component, from that component's dynamic program. It keeps the best ratio overall. Pieces within one component interact with other components only through the core. So after a selection we recompute only components adjacent to newly selected or newly covered core vertices. This is the structural analogue of lazy greedy, and it is embarrassingly parallel across components.
Third, the analysis. We prove correctness of the exact-gain dynamic program. We derive the $\gamma_b$ bound and characterize when $\gamma_b$ is small, for instance when the optimum lies within distance $b$ of the growing set. We also report per-instance empirical $\gamma_b$ against exact optima on small graphs.
Baselines
The naive reference is connectivity-aware single-node greedy: repeatedly add the adjacent node with the largest coverage gain. This is exactly our method at $b=1$, so it also serves as the ablation for step size.
The strongest practical competitor is greedy with shortest-path connectors. Each round it picks the node with the best gain divided by the cost of the shortest path from $S$ to that node, and adds the whole path. This is the standard way practitioners add connectivity to greedy, and on small-diameter graphs it may be hard to beat. We run it with the same lazy-evaluation machinery, on the same machine, under the same wall-clock budget.
We also run connector greedy followed by 1-swap and 2-swap local search, in the spirit of Fellows et al., for a matched amount of extra time. This tests whether post-hoc improvement closes the gap.
Exact optima come from an integer-programming formulation with flow-based connectivity constraints, solved by a commercial or open solver on graphs up to a few thousand nodes with a fixed time limit.
A coarsening baseline follows the same protocol as Dynamic Coarsening: coarsen, run connector greedy on the coarse graph, then lift the solution and repair connectivity.
The key-ingredient ablation replaces the exact joint gain inside the dynamic program with the sum of singleton gains. That surrogate overcounts overlap, so the ablation isolates whether exact accounting of overlap within a piece matters.
No reported result was found on Lacuna for connected coverage maximization on any benchmark in the file. The numbers the file does report, such as SGPO's 2636 coverage units on MuJoCo Ant and SubMix's 82.26% on ogbn-arxiv, are for different tasks and are not comparable.
Beating the baselines means two things. The method should reach higher covered weight than connector greedy plus local search at matched time on a majority of (graph, $k$) pairs. On small graphs it should also cut the gap to the integer-programming optimum by at least half.
Why not just…?
Why not just use greedy with shortest-path connectors? This is the real threat. On graphs where every high-value region lies one or two hops from the current set, connector paths are nearly optimal pieces, and our dynamic program would add cost without gain. Connectors fail when value sits in regions reached through several low-value nodes, or when the best piece is a small branching cluster rather than a path. We will stratify results by periphery width and by how far value lies from the core. If connector greedy matches us everywhere, the conclusion is that exact piece search is unnecessary, and we will report that.
Why not just solve the integer program? It is exact and simple to state. However, flow-based connectivity formulations grow with edges times commodities, and solver time is unpredictable. We use the integer program as ground truth on Cora, Citeseer, and AS-733 snapshots, and we report where it stops finishing within the time limit as graph size grows toward ogbn-arxiv and ogbn-products.
Why not just run tree-decomposition dynamic programming on the whole graph, or on a coarsened one? The direct measurement settles the first option. We report heuristic widths of the full graphs, which we expect to be far beyond what any dynamic program can handle. Coarsening, per the dynamic coarsening work, preserves spectral similarity but merges vertices. Coverage counts and connectivity on the coarse graph therefore do not correspond exactly to the original graph, and the coarsening baseline measures how much this repair loses.
Proposed Experiments
The first check is a go/no-go test of the structural premise. On Cora, Citeseer, Pubmed, ogbn-arxiv, ogbn-products, DBLP, ACM, Kindle, and AS-733 snapshots, we plot the heuristic width of periphery components against the core size $c$. We also record the fraction of total weight that lies in components of width at most about 15.
If the high-weight periphery on the citation graphs and AS-733 does not fall below a width the dynamic program can handle once a small core is removed, the method has no regime. We then stop and report the negative result. We expect the internet topology to pass and the dense co-purchase graph to possibly fail, and both outcomes are informative.
The main comparison covers $k$ from 10 to 500 and $b$ from 1 to 16. We use uniform weights and degree-based weights, and we measure covered weight and wall-clock time against all baselines above.
The decisive check has two parts. At matched time, block greedy must beat connector greedy plus local search precisely on graphs and budgets where value is distant from the core. On small graphs, the empirical $\gamma_b$ computed against integer-programming optima must shrink as $b$ grows. If the gain over connector greedy is flat in $b$, the step-size dial is not doing work, and the proposal's central claim fails.
For scalability, we report how runtime grows with periphery size on ogbn-products and the fraction of components recomputed per round. That fraction should stay small if the locality of recomputation holds.
References
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Maximizing the spread of influence through a social network
- Local Search: Is Brute-Force Avoidable?
- Improving TSP Tours Using Dynamic Programming over Tree Decompositions
- On Approximate Non-submodular Minimization via Tree-Structured Supermodularity
- Prize-collecting Network Design on Planar Graphs
- Bridging Indexing Structure and Graph Learning: Expressive and Scalable Graph Neural Network via Core-Fringe
- Fast nearest-neighbor search in disk-resident graphs
- Scalable Submodular Policy Optimization via Pruned Submodularity Graph
- Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening