EdgeCollapse

Flag-complex edge collapse (Boissonnat-Pritam, "Edge Collapse and Persistence of Flag Complexes," SoCG 2020; Glisse-Pritam, "Swap, Shift and Trim to Edge Collapse a Filtration," SoCG 2022): reduces a Vietoris-Rips filtration's own 1-skeleton to a smaller weighted graph whose flag complex has the SAME persistent homology at every filtration level, using only the graph itself (no higher simplices ever built). .claude/WORKLOG- mainstream-feature-gap-analysis.md item 5. Definitions verified directly against GUDHI's own edge-collapse module (Gudhi::collapse, the reference implementation, co-authored by the same Pritam/Glisse -- fetched and read directly via a throwaway clone of GUDHI/gudhi-devel, not recalled from memory, matching this codebase's own io-module verification ethos; the actual arXiv/Dagstuhl PDFs were unreachable from this session's network policy), not the mainstream-feature-gap-analysis worklog's own first-draft phrasing -- see this file's own worklog for the one correction that came out of that (the operation removes dominated EDGES, not dominated VERTICES; vertex domination is a different construction, "strong collapse," arXiv:1809.10945).

'''Dominated edge''' (GUDHI's own definition, restated for a flag complex where it depends only on the graph): an edge e = {u, v} is dominated by a vertex w ∉ e iff every vertex adjacent to BOTH u and v is also adjacent to w -- equivalently, w's closed neighborhood contains every common neighbor of u and v. An elementary edge collapse removes a dominated edge (and, implicitly, every simplex containing it) from the flag complex; domination is a simple sufficient condition for this removal to be an elementary simplicial collapse (a strong deformation retraction, hence a simple-homotopy equivalence).

'''Across a whole filtration''' (not one fixed threshold): an edge dominated at its own birth may stop being dominated once the filtration admits more vertices -- so instead of an outright removal, its own entry time is pushed forward to the largest time at which it remains dominated (by, in general, a succession of different dominating vertices as new common neighbors arrive) -- GUDHI's own doc states this plainly: "an edge collapse may translate into an increase of the filtration value of an edge, or its removal if it already had the largest filtration value." If no such largest time exists (the edge stays dominated all the way through the complex), it is removed outright. The resulting smaller weighted graph is, again, a flag complex, and its persistent homology (every bar, at every dimension) agrees with the original's exactly.

'''Representatives transfer for free through inclusion''' (this codebase's own design principle requires representatives from every engine, so this matters, and is not addressed by the papers' own barcode-only framing): at every filtration level t, the collapsed complex is a literal SUBCOMPLEX of the original (an edge collapse only ever removes cells or defers their entry to a later t, never adds or identifies any) -- so the inclusion of the collapsed complex into the original is a well-defined chain map at every level, and a cycle/cocycle representative computed on the SMALLER complex is automatically a valid representative of the SAME homology class in the ORIGINAL complex, simply by reinterpreting the same chain as living in the bigger complex. No separate lifting machinery is needed (contrast the MST-based simplicial-set collapse this same worklog item considered and declined -- see the worklog -- where the analogous complex is a QUOTIENT, not a subcomplex, and lifting a representative back is a real additional step).

'''This implementation IS a faithful port of GUDHI's own single-pass, descending-filtration-value sweep''' (process_edges/common_neighbors/is_dominated_by in Flag_complex_edge_collapser.h) -- a first attempt at an independently-designed "iterate a batch-scan resolution to a whole-graph fixed point" alternative was tried and CONFIRMED WRONG (WORKLOG-edge-collapse.md): it over-collapsed a 5-point fixture, permanently removing every chord of a pentagon whose flag complex genuinely has a persistent (non-zero-persistence) H¹ class, silently turning that class essential. The bug was letting an edge's own "dominated forever, remove" decision stand permanently even after a LATER decision (elsewhere in the graph) invalidated the very common-neighbor edge that removal decision had relied on -- a removed edge is never reconsidered, so nothing could ever correct it. GUDHI's own SPECIFIC processing order (descending by ORIGINAL filtration value, one pass, each edge decided exactly once against the live, progressively-mutating graph) is not an arbitrary implementation choice, as this class's own first (wrong) draft assumed -- it is what the published algorithm actually requires, and this port follows it exactly rather than re-deriving a substitute. This session could not fetch the actual proof (the arXiv/Dagstuhl hosts were unreachable from this session's network policy -- see the worklog) justifying WHY that specific order is sound; this implementation trusts the verified reference implementation's own structure on that point, the same way this codebase trusts a fetched GUDHI/DREiMac docstring or worked example elsewhere, and instead cross-validates the OUTPUT empirically (barcode agreement against plain, uncollapsed VR, across property-tested random point clouds, a tie-heavy fixture, and hand-built fixtures) rather than the algorithm's own internal reasoning -- see the spec.

GUDHI's own doc notes the single pass does not necessarily produce a MINIMAL filtration -- applying collapse again to its own output (this class's EdgeCollapsedMetricSpace is itself a FiniteMetricSpace[Int], so this needs no special support) may simplify it further; neither this class nor GUDHI's own promises idempotence in one application.