infrastructure planners

Abstract: AI data center build-out is a multi-trillion-dollar, multi-decade infrastructure program. Yet siting, power procurement, and cooling decisions are still made with static, single-point scoring tools. These tools are evaluated once, on day-zero numbers. This is a poor fit. A site's water, power, and carbon profile drifts substantially over the 10 to 20 year asset life. The governing decisions are also irreversible, and they bind capital and physical plant for years. We formalize long-horizon build-out as a tiered multi-objective Markov decision process. Strategic commitments are gated to discrete windows, incur switching costs, and energize only after source-dependent lead times. Operational dispatch is restricted to capacity that physically exists. We solve the problem with a preference-conditioned multi-objective agent that has a semi-Markov manager and worker hierarchy. The agent recovers a family of policies that a planner can steer across cost, carbon, water, and reliability at inference time. We validate long-horizon dynamics with a lightweight counterfactual rollout model. Across three commitment regimes (irreversible, reversible, and commit-once) on real site data, preference conditioning yields a confirmed, steerable trade-off on both objective pairs in every regime. Imposing lock-in produces a more evenly covered frontier and a far more consistent rate of anticipatory retrofit ahead of a binding water-stress constraint than a freely reversible formulation. Finally, a compact counterfactual dynamics model tracks slow-moving state well. It is measurably outperformed by simple persistence on the water-stress axis. We report this limitation rather than obscure it. We release the environment, agents, baselines, and evaluation harness. All of them are grounded in real interconnection-queue, water-stress, and grid-emissions data.

Abstract: Internet path diversity is usually verified at the logical layer: two alternatives may share no AS or IP link yet traverse the same facility, conduit, or submarine landing zone. We call this gap illusory resilience and define the Illusory Resilience Index (IRI) as the latent hazard-weighted physical overlap of a logically disjoint path pair. To detect such hidden exposure without carrier underlay maps, we audit three public signals: correlated BGP withdrawals during documented physical incidents, operator interconnection-footprint overlap, and shared submarine landing zones. Two signals survive calibration; the 60-second BGP signal does not. Across 47 operators in ten regions, same-region pairs have substantially greater listed facility overlap than cross-region pairs, and one Marseille campus colocates 153 operator pairs. Across 68 cable systems in twelve corridors, 31-100% of candidate within-corridor pairs share a 25 km coastal hazard zone; two corridors are fully saturated, and the same rule recovers ten of eleven cable pairs documented as co-damaged in 2024. The rejected temporal predicate has a 0.444 null firing rate and no hits among twelve monitored positive pairs. Public data therefore expose substantial shared-risk structure behind nominal diversity and identify where stronger physical-path verification is warranted.

Abstract: Given an undirected weighted graph $G=(V,E)$ on $n$ vertices, the classical Gomory-Hu tree of $G$ is a structure that encodes an arbitrary minimum $s,t$-cut for every $s,t\in V$ using just $O(n)$ space. In this work, we ask whether the same compactness is achievable for the natural and structured family of all-pairs \textit{nearest minimum cuts}. The nearest minimum $(s,t)$-cut is the unique inclusion-wise minimal one among all minimum $s,t$-cuts containing $s$. This family has proven useful in a wide range of applications, including fault-tolerant reachability, minimum cut sensitivity oracles, cactus representations, and fast Gomory-Hu tree constructions. Despite its fundamental role, no subquadratic space representation is known for them to date. The $O(n)$ space representations are known only in single-source settings, where given a source $s$, one can report the nearest minimum $(t,s)$-cut for any $t\in V\setminus \{s\}$. We close this gap by presenting the first optimal space representation of all-pairs nearest minimum cuts, providing a natural analogue of the Gomory-Hu tree. Our main result is an $O(n)$ space structure that encodes the nearest minimum cut between every pair of vertices. Furthermore, given any pair $s,t\in V$, it can report the nearest minimum $s,t$-cut in $O(n)$ time. Both bounds match those of the Gomory-Hu tree and are worst-case optimal. As an application, we design an all-pairs minimum cut sensitivity oracle for edge insertion: a data structure that occupies $O(n)$ space and, given any edge $e$, can determine for all pairs $s,t\in V$ whether the minimum $s,t$-cut value increases upon insertion of $e$ in $O(n^2)$ total time. Existing insertion sensitivity oracles were either limited to the single-source setting or used $O(n^2)$ space for all-pairs [Baswana, Gupta, and Knollmann, Algorithmica'22; Baswana and Pandey, SODA'22].

Abstract: Zero Forcing (ZF) and Power Dominating Set (PDS) mark vertices in a graph based on a common forcing process starting from a problem-specific set of initially marked vertices. ZF initially marks the selected vertices while PDS additionally marks their neighbors. In the forcing process, a marked vertex with only one unmarked neighbor may force that neighbor which then becomes marked, too. A solution marks the entire graph by exhaustive application of this rule. One variant generalizes the forcing threshold; vertices may force when they have a fixed number of $k$ unmarked neighbors. Another variant limits propagation to a fixed number of rounds. We classify the parameterized complexity of the problem variants obtained by combining these choices of initialization, round limit and forcing threshold. We show that with appropriate choices, these variants range in parameterized complexity from fixed-parameter tractable to complete for every even layer $W[2\ell]$ of the $W$-hierarchy, and up to $W[P]$-complete. Our results demonstrate that small changes in any one of these three dimensions can lead to a sharp change in problem complexity.

Abstract: The Matching Augmentation Problem (MAP) asks for a minimum-cardinality set of unit-cost edges that, together with a zero-cost matching, forms a 2-edge-connected spanning multigraph. We study the standard cut relaxation. Bamas, Drygala, and Svensson proposed a particularly simple LP-guided algorithm: compute an extreme optimum, run a depth-first search that prioritizes large LP coordinates, and augment the resulting DFS tree optimally. We give a new structural analysis of the Bamas--Drygala--Svensson LP-guided DFS algorithm. The analysis combines an exact primal--dual identity for the residual uplink problem with a rank bound that measures fractional support relative to the unit-valued skeleton. The result is that for every root and every deterministic tie-breaking order consistent with the LP priorities, the algorithm returns a solution of cost at most $\frac{59}{33}c(x^*)-\frac{25}{33}=\left(2-\frac7{33}\right)c(x^*)-\frac{25}{33}\approx1.788c(x^*)-0.758$, where $x^*$ is an optimum of the cut LP. Consequently, the integrality gap of the relaxation is at most $59/33\approx1.788$. No new algorithmic step is required; the improvement is analytical. The exact packing certificate for the residual uplink problem yields a cost identity with a packing-slack term, while a rank theorem bounds fractional support relative to the unit-valued skeleton. A regional classification accounts for the non-tree edges, and a two-cut identity handles self-holes. As a direct corollary, the same $59/33\approx1.788$ bound holds for Forest Augmentation in the minimum-value regime. The proof is self-contained apart from one theorem on the dimension of minimum-cut vectors.

Abstract: In the $(p,q)$-Flexible Graph Connectivity problem, the input consists of non-negative integers $p$ and $q$ and a graph $G=(V, E)$ whose edges are classified into safe and unsafe edges with non-negative edge costs. A subgraph H of G is $(p,q)$-Flex-Connected if every non-empty proper subset of vertices has either at least $p$ safe edges or at least $p+q$ total edges crossing it. The goal is to find a minimum cost subset $F\subseteq E$ of edges such that the subgraph $(V, F)$ is $(p,q)$-Flex-Connected. We give a $(p+q)^{O(pq)}$-approximation for this problem, which in particular implies a constant approximation for every fixed constants $p$ and $q$. We achieve this by designing a $(p+q)^{O(pq)}$-approximation for the augmentation problem of finding a minimum cost subset of edges to add to make a (p,q-1)-Flex-Connected graph into a (p,q)-Flex-Connected graph. Underlying the augmentation algorithm is a structural result showing that all deficient cuts can be represented by min rooted-cuts in a $(p+q)^{pq}$-sized collection of digraphs. This structural result was discovered by ChatGPT Astra.