Which Station Failures Blind a Sparse Telescope Array? A Packing-versus-Hitting Certificate for Closure Loops

A very long baseline interferometer, such as the Event Horizon Telescope that imaged the black holes M87 and Sagittarius A, never photographs its target directly. Each pair of dishes measures one Fourier coefficient of the sky image, so a handful of stations samples the Fourier plane sparsely. Turbulent atmosphere scrambles each station's phase, which makes things worse. The standard defense is the closure phase: add the measured phases around a closed loop of baselines and the station errors cancel exactly (EHT Paper III; Bouman et al.). An array's ability to see fine structure in a given Fourier region therefore depends on how many independent loops cross that region. It also depends on how fragile those loops are: how few station failures, or weather-flagged scans, would wipe them all out.

We propose to measure that fragility with a minimax duality from combinatorics, the Erdős–Pósa property. Either a graph contains many nearly disjoint copies of some kind of cycle (a packing), or a small set of vertices meets every such cycle (a hitting set). For a target Fourier region we compute both sides on a time-expanded observation graph. The first is the largest set of informative closure loops that touch the region with no station-scan used more than twice. The second is the smallest set of station-scans whose loss destroys all such loops. The hitting set is directly useful to array designers and schedulers, because it names exactly which telescopes, at which times, the image of that region depends on. Our claim is that this certificate predicts how much reconstructions degrade under realistic dropouts, and that it does so better than the filling-fraction and point-source-sensitivity metrics now used for next-generation array design.

Core Claim and Why the Obvious Bridge Fails

The tempting intersection is to compute directed treewidth (a measure of how tree-like a directed graph's reachability structure is) of the station–baseline graph, or to pick closure triangles by cycle packing. At any instant, though, the station graph is close to complete. With 8 stations in 2017 and about 20 for the next-generation array, treewidth is trivially near $N$. Baseline orientation only flips the sign of the phase ($\phi_{ji}=-\phi_{ij}$), so it is a label on the edge, not a restriction on which direction you can travel. Triangles are also too short for the deep theory to matter. A maximal packing of $k$ vertex-disjoint triangles already yields a hitting set of $3k$ vertices, so the packing–hitting gap is at most 3, and an integer program solves everything instantly. We therefore set the station graph aside as the object of study.

The structure becomes nontrivial in the time-expanded graph. Its vertices are (station, scan) pairs. Baseline edges join stations observing simultaneously in a scan. Coherence edges join a station's consecutive scans when they fall within the atmospheric coherence time, so that its phase error drifts only slightly. In sparse, weather-thinned schedules, many scans contain too few simultaneous stations to form a triangle. A loop that goes A–B in one scan, B–C in a later scan, and C–A in a third, linked by coherence edges, still cancels station phases up to a small drift. These extended closure loops are long, there are many of them, and they live in graphs with thousands of vertices. That is the regime where packing and hitting can genuinely diverge.

Two constraints decide which loops count. Contract the coherence edges and a loop maps to a closed walk in the station graph. The loop carries closure information only if that walk is non-null in the cycle space; for example, A–B and then B–A later measures only temporal variability. The loop is relevant to region $R$ only if it uses at least one baseline whose Fourier-plane point lies in $R$. Both conditions can be written as "the cycle's label is nonzero" in an abelian group. The first group is the cycle space of the station graph. The second is the integers, counting how many of the loop's baselines fall in $R$. This matches the setting of the unified half-integral Erdős–Pósa theorem for cycles labelled by multiple abelian groups (A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups), which proves a packing/hitting duality for cycles that are nonzero in several groups at once, provided each vertex may be used by up to two packed cycles.

For a region $R$, let $\nu_2(R)$ be the maximum number of admissible loops such that every station-scan lies in at most two of them. Let $\tau(R)$ be the minimum number of station-scans meeting every admissible loop. The theorem guarantees

$$\nu_2(R) \le \tau(R) \le f\big(\nu_2(R)\big),$$

where $f$ is a function independent of the instance. The lower inequality holds because each hitting vertex can break at most two packed loops, which would give $\tau \ge \nu_2/2$. Strictly, then, the left side should read $\nu_2(R)/2 \le \tau(R)$; we will report the pair rather than rely on either bound. The congestion of two is not a convenience. For parity-like constrained cycle families, the vertex-disjoint version of the duality fails outright: wall-like constructions contain no two disjoint constrained cycles yet need arbitrarily large hitting sets. This is exactly why Kawarabayashi, Kreutzer, Kwon and Xie had to settle for half-integral packing of directed odd cycles. Our non-null condition is a cycle-space parity of the same kind, so an integral version of the certificate could behave erratically on real schedules. That is a prediction the experiments test.

The congestion bound also has a physical meaning. A loop's noise is correlated with every other loop that shares a station-scan. Capping reuse at two keeps the packed loops nearly independent pieces of evidence, which echoes the reasoning behind relaxed packing for directed cycles in Masarík et al..

Role of Each Direction

The polynomial Erdős–Pósa line is the core mechanism. It supplies the definition, the half-integral relaxation, and the reason relaxation is needed. Its main papers are the quarter- and half-integral directed cycle packing results (Masarík et al.), which show that allowing constant vertex congestion turns tower-sized bounds into polynomial ones. The fractional theory for circuits through prescribed vertices (Kawarabayashi et al. 2012) supplies the linear-programming side we compute alongside the integral one. Its "through prescribed vertices" condition is our region constraint once each region-$R$ baseline is subdivided into a vertex.

Sparse baseline coverage is the application regime and the source of ground truth.

Structural obstruction theory in directed graphs plays two narrower roles. First, it constrains the design: the directed odd-cycle and Escher-wall phenomena show where integral dualities break. Second, it gives a lens for diagnosis. When $\tau(R)$ is large but $\nu_2(R)$ is small, the theory says the cause is an entangled, mutually touching family of loops. That family is the analogue of a bramble, a collection of connected pieces that pairwise touch so that no small vertex set separates them. Constant congestion brambles shows that such families appear with only polynomial loss, and they are what we will look for in schedules with a large gap. The coherence and frequency-phase-transfer edges can be oriented in time or from 86 GHz to 230 GHz, but we treat orientation as a modeling option and not a premise. We will report whether the directed and undirected versions of the certificate ever disagree.

Research Program

We will first build the time-expanded graph from simulated and real schedules. Coherence edges are admissible only within a coherence window, and each loop is weighted by its accumulated drift so that long chains of coherence edges count as noisier. On these graphs we compute four quantities per Fourier region using exact integer programs: the integral packing number, $\nu_2(R)$, its linear-programming value, and $\tau(R)$. Regions come from partitioning the Fourier plane into annuli and position-angle sectors, with special attention to the annuli around the correlated-flux nulls at about 3.4 and 8.3 Gλ reported for M87* in EHT Paper I. The scale is small enough that exact solving should be feasible, which means the theory's role is to justify the quantity, not to approximate it. Where exact solving becomes slow, we use the polynomial-time packing-or-hitting algorithm from the odd-cycle work as a fallback.

We will then attach the certificate to reconstruction outcomes. For each array and schedule we draw dropout scenarios, either weather flags driven by the MERRA-2 opacity history in Doeleman et al. or single-station failures. We reconstruct images and measure error restricted to each region. The hypothesis is that $\tau(R)$, together with the gap between $\tau(R)$ and $\nu_2(R)$, predicts per-region degradation, and that removing the hitting set causes disproportionate damage.

Baselines

The naive reference point is to count closure triangles per region within single scans, the bookkeeping implicit in all-triangle bispectrum imaging such as CHIRP (Bouman et al.). It costs nothing, so the certificate must beat it to justify itself.

The strongest existing competitors are the array-design metrics in Doeleman et al.: filling fraction, the fraction of the Fourier plane sampled, and point-source sensitivity, both computed in ngehtsim and used to choose sites from 44 candidates. These are the metrics the community actually uses to rank arrays, so they are the right comparison. We will compute them on the same schedules and dropout scenarios through the same ngehtsim configuration, restricted to the same regions. Every predictor is scored against identical reconstructions, and no predictor gets tuning that the others do not. The file reports no numeric predictive accuracy for these metrics; no reported result found on Lacuna for filling fraction or point-source sensitivity as predictors of reconstruction degradation. The only anchoring figures are design-level: a dynamic range of about 10:1 for the 2017 array versus a target above 1000:1, from the same paper. We will therefore establish the baseline numbers ourselves.

Beating them means a higher rank correlation between predictor and per-region reconstruction error across dropout scenarios, with a bootstrap confidence interval that excludes the metrics' values. It also means higher precision when flagging which single-station loss causes the largest regional degradation.

Three ablations isolate the key ingredients. Dropping coherence edges reduces the certificate to instantaneous triangles. Dropping the non-null label lets trivial same-baseline loops inflate packing. Using integral packing instead of half-integral packing tests whether congestion relaxation stabilizes the certificate, as the odd-cycle theory predicts.

Why not just…?

Why not just compute directed treewidth or brambles of the baseline network, as the gap analysis suggests? On a near-complete station graph these parameters are essentially $N$ and say nothing about individual arrays. We will report them once, on the 2017 and next-generation arrays, to show this concretely, and then drop them. The obstruction theory earns its place only on the time-expanded graph, as a diagnostic for large-gap instances.

Why not just Monte Carlo the reconstructions under every dropout scenario? This is the real threat, because simulated reconstruction is the ground truth our certificate is trying to predict. The certificate is worth having only if it is far cheaper and comparably accurate, and if its hitting set explains failures that Monte Carlo merely detects. We will report wall-clock cost for both. We will also measure how many Monte Carlo draws are needed to match the certificate's ranking accuracy. If a small number of draws matches it, the certificate's remaining value is interpretability alone, and we will say so.

Why not just fit station gains jointly with the image under a smoothness prior? Such self-calibration already uses extended-loop information implicitly. We do not compete with it; we use regularized reconstruction as the engine whose failures we predict. The certificate answers a different question: before observing, which schedule leaves a region recoverable at all.

Why not just treat the graph as undirected and pack ordinary cycles? Without the non-null label, loops that measure only temporal variability on one baseline are counted as closure information. The label ablation measures how much this inflates the apparent robustness.

Proposed Experiments

The first test is on the Bouman et al. synthetic benchmark of over 5,000 simulated measurements, scored by mean squared error and structural similarity. The source text gives no numeric values for these, so we will rerun CHIRP and a regularized maximum-likelihood method ourselves.

The second test uses images from the EHT library of over 60,000 GRMHD simulations (EHT Paper I) as sky models. These are observed through the real 2017 eight-station schedule and through candidate next-generation layouts in ngehtsim, under MERRA-2-driven weather dropouts. We score region-restricted error and the recovered ring diameter, comparing against the reported 42 ± 3 μas for M87 and 51.8 ± 2.3 μas for Sgr A (Sgr A* Paper I).

The decisive checks are three. First, the certificate must beat filling fraction and point-source sensitivity in rank correlation with per-region error. Second, deleting the computed hitting set must hurt that region measurably more than deleting the same number of station-scans chosen at random or by sensitivity. Third, the integral certificate must be measurably noisier across bootstrap resamples of the schedule than the half-integral one. If the first check fails, the proposal reduces to a combinatorial curiosity, and we will report that outcome plainly.