Data sharing is not applicable to this article as no datasets were generated
or analysed during the current study.

## References

  * (1) Barbuy, B., Bawden Macanhan, V., Bristow, P. et al.: CUBES: Cassegrain U-Band Brasil-ESO Spectrograph, Ap&SS, 354, 191 (2014)
  * (2) Zanutta, A., Cristiani, S., Atkinson, D. et al.: CUBES Phase A design overview, ExA, arXiv:2203.15352, in press as part of the Special Issue
  * (3) Opitom, C., Snodgrass, C., La Forgia, F. et al.: Cometary Science with CUBES, ExA, arXiv:2203.15579, in press as part of the Special Issue
  * (4) Alcalá, J. M., Cupani, G., Evans, C. et al.: Accretion and outflows in young stars with CUBES, ExA, arXiv:2203.15581, in press as part of the Special Issue
  * (5) Smiljanic, R., da Silva, A. R. & Giribaldi, R. E.: Detecting weak beryllium lines with CUBES, ExA, arXiv:2203.16158, in press as part of the Special Issue
  * (6) Giribaldi, R. E. & Smiljanic, R.: Beryllium abundances in turn-off stars of globular clusters with the CUBES spectrograph, ExA, arXiv:2203.15604, in press as part of the Special Issue
  * (7) Bonifacio, P.: Metal-poor stars: The role of cubes, ExA, in press as part of the Special Issue
  * (8) Hansen, C. J.: Heavy elements – they came out of the blue, ExA, in press as part of the Special Issue
  * (9) Ernandes, H., Barbuy, B., Castilho, B. et al.: Simulated observations of heavy elements with CUBES, ExA, arXiv:2203.15693, in press as part of the Special Issue
  * (10) Evans, C., Marcolino, W., Bouret, J.-C. & Garcia, M.: A near-UV reconnaissance of metal-poor massive stars, ExA, in press as part of the Special Issue
  * (11) D’Odorico, V.: Portraying the missing baryonic mass at the cosmic noon: the contribution of CUBES, ExA, in press as part of the Special Issue
  * (12) Balashev, S. & Noterdaeme, P.: ”Molecular hydrogen in absorption at high redshifts – Science cases for CUBES”, ExA, in press as part of the Special Issue
  * (13) Snodgrass, C., Agarwal, J., Combi, M. et al.: The Main Belt Comets and ice in the Solar System, A&ARv, 25, 5 (2017)
  * (14) Kramer, T., Läuter, M., Rubin, M. & Altwegg, K.: Seasonal changes of the volatile density in the coma and on the surface of comet 67P/Churyumov-Gerasimenko, MNRAS, 469, S20
  * (15) Snodgrass, C., Yang, B. & Fitzsimmons, A.: X-shooter search for outgassing from main belt comet P/2012 T1 (Pan-STARRS), A&A, 605, A56 (2017)
  * (16) O’Brien, D. P., Izidoro, A., Jacobson, S. A., Raymond, S. N. & Rubie, D. C.: The Delivery of Water During Terrestrial Planet Formation, SSRv, 214, 47 (2018)
  * (17) Snodgrass, C. & Jones, G. H.: The European Space Agency’s Comet Interceptor lies in wait, Nat. Comms., 10, 5418 (2019)
  * (18) Lane, A. L., Nelson, R. M. & Matson, D. L.: Evidence for sulphur implantation in Europa’s UV absorption band, Nature, 292, 38 (1981)
  * (19) Johnson, T. V. & McCord, T. B.: Galilean Satellites. The Spectral Reflectivity 0. 30-1.10 Micron, Icar, 13, 37 (1970)
  * (20) Wamsteker, W.: Narrow-band photometry of the Galilean satellites. Comm. Lunar Planet. Lab. 9 (No. 167), 171 (1972)
  * (21) McFadden, L. A., Bell, J. F. & McCord, T. B.: Visible spectral reflectance measurements (0.33-1.1 $\mu$m) of the Galilean satellites at many orbital phase angles, Icar, 44, 410 (1980)
  * (22) Nelson, R. M., Lane, A. L., Matson, D. L. et al.L Spectral geometric albedos of the Galilean satellites from 0.24 to 0.34 micrometers: Observations with the international ultraviolet explorer, Icar, 72, 358 (1987)
  * (23) Noll, K. S., Weaver, H. A. & Gonnella, A. M.: The albedo spectrum of Europa from 2200 Å to 3300 Å, JGR, 100, 19057 (1995)
  * (24) Spencer, J. R., Calvin, W. M. & Person, M. J.: CCD Spectra of the Galilean Satellites: Molecular Oxygen on Ganymede, JGR, 100, 19049 (1995)
  * (25) Hendrix, A. R. & Johnson, R. E.: Callisto: New Insights from Galileo Disk-resolved UV Measurements, ApJ, 687, 706 (2008)
  * (26) Hendrix, A. R., Vilas, F. & Li, J.-Y.: The UV signature of carbon in the solar system, M&PS, 51, 105 (2016)
  * (27) McGrath, M. A., Jia, X., Retherford, K. et al.: Aurora on Ganymede, JGR, 118, 2043 (2004)
  * (28) Bida, T. & Killen, R. M.: Observations of the minor species Al and Fe in Mercury’s exosphere, Icar, 289, 227 (2017)
  * (29) Giannini, T., Antoniucci, S., Nisini, B., Bacciotti, F. & Podio, L.: Solving the Excitation and Chemical Abundances in Shocks: The Case of HH 1, ApJ, 814, 52 (2015)
  * (30) Alcalá, J. M., Manara, C. F., Natta, A. et al.: X-shooter spectroscopy of young stellar objects in Lupus. Accretion properties of class II and transitional objects, A&A, 600, A20 (2017)
  * (31) Manara, C. F., Testi, L., Herczeg, G. J. et al.: X-shooter study of accretion in Chamaeleon I. II. A steeper increase of accretion with stellar mass for very low-mass stars? A&A, 604, A127 (2017)
  * (32) Nisini, B., Antoniucci, S., Alcalá, J. M. et al.: Connection between jets, winds and accretion in T Tauri stars. The X-shooter view, A&A, 609, A87 (2018)
  * (33) Alencar, S. H. P., Bouvier, J., Walter, F. M. et al.: Accretion dynamics in the classical T Tauri star V2129 Ophiuchi, A&A, 541, A116 (2012)
  * (34) Alcalá, J. M., Manara, C. F., France, K., et al.: HST spectra reveal accretion in MY Lupi, A&A, 629, A108 (2019)
  * (35) Fang, M., Pascucci, I., Edwards, S. et al.: A New Look at T Tauri Star Forbidden Lines: MHD-driven Winds from the Inner Disk, ApJ, 868, 28 (2018)
  * (36) Liu, C.-F., Shang, H., Walter, F. M. & Herczeg, G. J.: Velocity-resolved [Ne III] from X-Ray Irradiated Sz 102 Microjets, ApJ, 786, 99 (2014)
  * (37) Rogers, L. A. & Seager, S.: A Framework for Quantifying the Degeneracies of Exoplanet Interior Compositions, ApJ, 712, 974 (2010)
  * (38) Zuckerman, B., Koester, D., Melis, C., Hansen, B. M., Jura, M.: The Chemical Composition of an Extrasolar Minor Planet, ApJ, 671, 872 (2007)
  * (39) Jura, M.: A Tidally Disrupted Asteroid around the White Dwarf G29-38, ApJ, 594, L91 (2003)
  * (40) Klein, B., Jura, M., Koester, D., Zuckerman, B. & Melis, C.: Chemical Abundances in the Externally Polluted White Dwarf GD 40: Evidence of a Rocky Extrasolar Minor Planet, ApJ, 709, 950 (2010)
  * (41) Gentile Fusillo, N. P, Tremblay, P.-E., Gänsicke, B. T. et al.: A Gaia Data Release 2 catalogue of white dwarfs and a comparison with SDSS, MNRAS, 482, 4570
  * (42) Testa, P., Saar, S. H. & Drake, J. J. Stellar activity and coronal heating: an overview of recent results, RSPTA, 373, 40259 (2015)
  * (43) Klocová, T., Czesla, S., Khalafinejad, S., Wolter, U. & Schmitt, J. H. M. M.: Time-resolved UVES observations of a stellar flare on the planet host HD 189733 during primary transit, A&A, 607, A66 (2017)
  * (44) Kowalski, A. F., Cauzzi, G. & Fletcher, L.: Optical Spectral Observations of a Flickering White-light Kernel in a C1 Solar Flare, ApJ, 798, 107 (2015)
  * (45) Kowalski, A. F., Hawley, S. L., Wisniewski, J. P. et al.: Time-resolved Properties and Global Trends in dMe Flares from Simultaneous Photometry and Spectra, ApJS, 207, 15 (2013)
  * (46) Yu, L., Donati, J.-F., Hébrard, E. M. et al.: A hot Jupiter around the very active weak-line T Tauri star TAP 26, MNRAS, 467, 1342 (2017)
  * (47) Donati, J.-F., Semel, M., Carter, B. D. et al. Spectropolarimetric observations of active stars, MNRAS, 291, 658 (1997)
  * (48) Donati, J. F., Moutou,C., Malo, L. et al.: A hot Jupiter orbiting a 2-million-year-old solar-mass T Tauri star, Nature, 534, 662 (2016)
  * (49) Spite, M., Bonifacio, P., Spite, F. et al.: Be and O in the ultra metal-poor dwarf 2MASS J18082002-5104378: the Be-O correlation, A&A, 624, A44 (2019)
  * (50) Smiljanic, R.: Stellar abundances of beryllium and CUBES, Ap&SS, 354, 55 (2014)
  * (51) Reeves, H., Fowler, W. A. & Hoyle, F.: Galactic Cosmic Ray Origin of Li, Be and B in Stars, Nature, 226, 727 (1970)
  * (52) Beers, T. C., Chiba, M., Yoshii, Y. et al.: Kinematics of Metal-poor Stars in the Galaxy. II. Proper Motions for a Large Nonkinematically Selected Sample, AJ, 119, 2866 (2000)
  * (53) Suzuki, T. K. & Yoshii, Y.: A New Model for the Evolution of Light Elements in an Inhomogeneous Galactic Halo, ApJ, 549, 303 (2001)
  * (54) Pasquini, L., Bonifacio, P., Molaro, P., et al.: Li in NGC 6752 and the formation of globular clusters, A&A, 441, 549 (2005)
  * (55) Pasquini, L., Bonifacio, P., Randich, S. et al.: Beryllium abundance in turn-off stars of NGC 6752, A&A, 464, 601 (2007)
  * (56) Smiljanic, R., Pasquini, L., Bonifacio, P. et al.: Beryllium abundances and star formation in the halo and in the thick disk, A&A, 499, 103 (2009)
  * (57) Molaro, P., Cescutti, G., Fu, X.: Lithium and beryllium in the Gaia-Enceladus galaxy, MNRAS, 496, 2902 (2020)
  * (58) Smiljanic, R., Zych, M. G. & Pasquini, L.: Inhomogeneity in the early Galactic chemical enrichment exposed by beryllium abundances in extremely metal-poor stars, A&A, 646, A70 (2021)
  * (59) Smiljanic, R., Pasquini, L., Charbonnel, C., Lagarde, N.: Beryllium abundances along the evolutionary sequence of the open cluster IC 4651 - A new test for hydrodynamical stellar models, A&A, 510, A50 (2010)
  * (60) Smiljanic, R., Randich, S., Pasquini, L.: Mixing at young ages: beryllium abundances in cool main-sequence stars of the open clusters IC 2391 and IC 2602, A&A, 535, A75 (2011)
  * (61) Boesgaard, A. M., Lum, M. G., Deliyannis, C. P.: Correlated Depletion and Dilution of Lithium and Beryllium Revealed by Subgiants in M67, ApJ, 888, 28 (2020)
  * (62) Boesgaard, A. M., Lum, M. G., Chontos, A., Deliyannis, C. P.: Lithium and Beryllium in NGC 752 - an Open Cluster Twice the Age of the Hyades, ApJ, 927, 118 (2022)
  * (63) Boesgaard, A. M., Deliyannis, C. P., King, J. R. et al.: Beryllium Abundances in Halo Stars from Keck/HIRES Observations, AJ, 117, 1549 (1999)
  * (64) Primas, F., Molaro, P., Bonifacio, P. & Hill, V.: First UVES observations of beryllium in very metal-poor stars, A&A, 362, 666 (2000)
  * (65) Primas, F., Asplud, M., Nissen, P. E. & Hill, V.: The beryllium abundance in the very metal-poor halo star G 64-12 from VLT/UVES observations, A&A, 364, L42 (2000)
  * (66) Boesgaard, A. M., Rich, J. A., Levesque, E. M. & Bowler, B. P.: Beryllium and Alpha-element Abundances in a Large Sample of Metal-poor Stars, ApJ, 743, 140 (2011)
  * (67) Starkenburg, E., Martin, N., Youakim, K. et al.: The Pristine survey - I. Mining the Galaxy for the most metal-poor stars, MNRAS, 471, 2587 (2017)
  * (68) Wolf, C., Onken, C. A., Luvaul, L. C. et al.: SkyMapper Southern Survey: First Data Release (DR1), PASA, 35, 10 (2018)
  * (69) Gratton, R. G., Carretta, E. & Bragaglia, A.: Multiple populations in globular clusters. Lessons learned from the Milky Way globular clusters, A&ARv, 20, 50 (2012)
  * (70) Yong, D., Meléndez, J., Cunha, K. et al.: Chemical Abundances in Giant Stars of the Tidally Disrupted Globular Cluster NGC 6712 from High-Resolution Infrared Spectroscopy, ApJ, 689, 1020 (2008)
  * (71) Guerço, R., Cunha, K, Smith, V. et al.: Fluorine Abundances in the Globular Cluster M4, ApJ, 876, 43 (2019)
  * (72) Tajitsu, A., Sadakane, K., Naito, H., Arai, A. & Aoki, W.: Explosive lithium production in the classical nova V339 Del (Nova Delphini 2013), Nature, 518, 381 (2015)
  * (73) Izzo, L. , Molaro, P., Bonifcaio, P. et al.: Classical Novae with CUBES, ExA, in press as part of the CUBES Special Issue
  * (74) Beers, T. C. & Christlieb, N.: The Discovery and Analysis of Very Metal-Poor Stars in the Galaxy, ARA&A, 43, 531 (2005)
  * (75) Plez, B.: Turbospectrum: Code for spectral synthesis, ASCL:1205.004, (2012)
  * (76) Cayrel, R., Hill, V., Beers, T. C. et al.: Measurement of stellar age from uranium decay, Nature, 409, 691 (2001)
  * (77) Hill, V., Plez, B., Cayrel, R. et al.: First stars. I. The extreme r-element rich, iron-poor halo giant CS 31082-001. Implications for the r-process site(s) and radioactive cosmochronology, A&A, 387, 560 (2002)
  * (78) Chiappini, C.: First stars and reionization: Spinstars, AN, 334, 595 (2013)
  * (79) Choplin, A., Maeder, A., Meynet, G. & Chiappini, C.: Constraints on CEMP-no progenitors from nuclear astrophysics, A&A, 593, A36 (2016)
  * (80) Umeda, H. & Nomoto, K.: Nucleosynthesis of Zinc and Iron Peak Elements in Population III Type II Supernovae: Comparison with Abundances of Very Metal Poor Halo Stars, ApJ, 565, 385 (2002)
  * (81) Umeda, H. & Nomoto, K.: Variations in the Abundance Pattern of Extremely Metal-Poor Stars and Nucleosynthesis in Population III Supernovae, ApJ, 619, 427 (2005)
  * (82) Tominaga, N., Iwamoto, N. & Nomoto, K.: Abundance Profiling of Extremely Metal-poor Stars and Supernova Properties in the Early Universe, ApJ, 785, 98 (2014)
  * (83) Abate, C., Pols, O., Izzard, R. G. & Karakas, A. I.: Modelling the observed properties of carbon-enhanced metal-poor stars using binary population synthesis, A&A, 581, A62
  * (84) Placco, V., Frebel, A., Lee, Y. S. et al.: Metal-poor Stars Observed with the Magellan Telescope. III. New Extremely and Ultra Metal-poor Stars from SDSS/SEGUE and Insights on the Formation of Ultra Metal-poor Stars, ApJ, 809, 136 (2015)
  * (85) Hansen, T. T., Andersen, J., Nordström, B. et al.: The role of binaries in the enrichment of the early Galactic halo. I. r-process-enhanced metal-poor stars, A&A, 583, A49 (2015)
  * (86) Hansen, C. J., Hansen, T. T., Koch, A. et al.: Abundances and kinematics of carbon-enhanced metal-poor stars in the Galactic halo. A new classification scheme based on Sr and Ba, A&A, 623, A128 (2019)
  * (87) Lodders, K.: Solar System Abundances and Condensation Temperatures of the Elements, ApJ, 591, 1220 (2003)
  * (88) Busso, M., Gallino, R. & Wasserburg, G. J.: Nucleosynthesis in Asymptotic Giant Branch Stars: Relevance for Galactic Enrichment and Solar System Formation, ARA&A, 37, 239 (1999)
  * (89) Pignatari, M., Gallino, R., Heil, M. et al.: The Weak s-Process in Massive Stars and its Dependence on the Neutron Capture Cross Sections, ApJ, 710, 1557 (2010)
  * (90) Pian, E., D’Avanzo, P., Benetti, S. et al.: Spectroscopic identification of r-process nucleosynthesis in a double neutron-star merger, Nature, 551, 67 (2017)
  * (91) Smartt, S. J., Chen, T.-W., Jerkstrand, A. et al.: A kilonova as the electromagnetic counterpart to a gravitational-wave source, Nature, 551, 75 (2017)
  * (92) Watson, D., Hansen, C. J., Selsing, J. et al.: Identification of strontium in the merger of two neutron stars, Nature, 574, 497 (2019)
  * (93) Bovard, L., Martin, D., Guercilena, F., Arcones, A. et al.: r-process nucleosynthesis from matter ejected in binary neutron star mergers PhRvD, 96, 124005 (2017)
  * (94) Matteucci, F., Romano, D., Arcones, A., Korobkin, O. & Rosswog, S.: Europium production: neutron star mergers versus core-collapse supernovae MNRAS, 438, 2177 (2014)
  * (95) Cescutti, G., Romano, D., Matteucci, F., Chiappini, C. & Hirschi, R.: The role of neutron star mergers in the chemical evolution of the Galactic halo, A&A, 577, A139 (2015)
  * (96) Mathews, G. J. & Cowan, J. J.: New insights into the astrophysical r-process, Nature, 345, 491 (1990)
  * (97) Ishimaru, Y. & Wanajo, S.: Enrichment of the R-Process Element Europium in the Galactic Halo, ApJ, 511, L33 (1999)
  * (98) Arcones, A., Janka, J.-Th. & Scheck, L.: Nucleosynthesis-relevant conditions in neutrino-driven supernova outflows. I. Spherically symmetric hydrodynamic simulations, A&A, 467, 1227 (2007)
  * (99) Winteler, C., Käppeli, R., Perego, A. et al.: Magnetorotationally Driven Supernovae as the Origin of Early Galaxy r-process Elements? ApJ, 750, L22 (2012)
  * (100) Nishimura, N., Takiwaki, T. & Thielemann, F.-K.: The r-process Nucleosynthesis in the Various Jet-like Explosions of Magnetorotational Core-collapse Supernovae, ApJ, 810, 109 (2015)
  * (101) Roederer, I. U., Sakari, C. M., Placco, V. M. et al.: The R-Process Alliance: A Comprehensive Abundance Analysis of HD 222925, a Metal-poor Star with an Extreme R-process Enhancement of [Eu/H] $=$ $-$0.14, ApJ, 865, 129 (2018)
  * (102) Ernandes, H., Evans, C. J., Barbuy, B. et al.: Stellar astrophysics in the near-UV with VLT-CUBES, Proc. SPIE, 11447, E60 (2020)
  * (103) Sandford, N. R., Weisz, D. R. & Ting, Y.-S.: Forecasting Chemical Abundance Precision for Extragalactic Stellar Archaeology, ApJS, 249, 24 (2020)
  * (104) Riess, A., Casertano, S., Yuan, W., Macri, L. & Scolnic, D.: Large Magellanic Cloud Cepheid Standards Provide a 1% Foundation for the Determination of the Hubble Constant and Stronger Evidence for Physics beyond $\Lambda$CDM, ApJ, 876, 85 (2019)
  * (105) Verde, L., Treu, T. & Riess, A. G.: Tensions between the early and late Universe, NatAs, 3, 891 (2019)
  * (106) Marconi, M., Musella, I. & Fiorentino, G.: Cepheid Pulsation Models at Varying Metallicity and $\Delta$Y/$\Delta$Z, ApJ, 632, 590 (2005)
  * (107) Marconi, M., Musella, I., Fiorentino, G. et al.: Pulsation Models for Ultra-low (Z = 0.0004) Metallicity Classical Cepheids, ApJ, 713, 615 (2010)
  * (108) Ripepi, V., Moretti, M. I., Marconi, M. et al.: The VMC survey - V. First results for classical Cepheids, MNRAS, 424, 1807 (2012)
  * (109) Fiorentino, G., Musella, I. & Marconi, M.: Cepheid theoretical models and observations in HST/WFC3 filters: the effect on the Hubble constant H0, MNRAS, 434 2866 (2013)
  * (110) Ripepi, V., Cioni, M.-R., Moretti, M. I. et al.: The VMC survey - XXV. The 3D structure of the Small Magellanic Cloud from Classical Cepheids, MNRAS, 472, 808 (2017)
  * (111) Ripepi, V., Molinaro, R., Musella, I. et al.: Reclassification of Cepheids in the Gaia Data Release 2. Period-luminosity and period-Wesenheit relations in the Gaia passbands, A&A, 625, A14 (2019)
  * (112) Romaniello, M., Primas, F., Mottini, M. et al.: The influence of chemical composition on the properties of Cepheid stars. II. The iron content, A&A, 488, 731 (2008)
  * (113) Bono, G., Caputo, F., Marconi, M. & Musella, I.: Insights into the Cepheid Distance Scale, ApJ, 715, 277 (2010)
  * (114) Bono, G., Caputo, F., Castellani, V., Marconi, M. & Storm, J.: Theoretical insights into the RR Lyrae K-band period-luminosity relation, MNRAS, 326, 1183
  * (115) Bono, G., Caputo, F., Castellani, V. et al.: A pulsational approach to near-infrared and visual magnitudes of RR Lyr stars, MNRAS, 344, 1097 (2003)
  * (116) Sollima, A., Cacciari, C. & Valenti, E.: The RR Lyrae period-K-luminosity relation for globular clusters: an observational approach, MNRAS, 372, 1675 (2006)
  * (117) Marconi, M., Coppola, G., Bono, G. et al.: On a New Theoretical Framework for RR Lyrae Stars. I. The Metallicity Dependence, ApJ, 808, 50 (2015)
  * (118) Piotto, G., Bedin, L. R., Anderson, J. et al.: A Triple Main Sequence in the Globular Cluster NGC 2808, ApJ, 661, L53 (2007)
  * (119) Bragaglia, A., Carretta, E., Gratton, R. G. et al.: X-shooter Observations of Main-sequence Stars in the Globular Cluster NGC 2808: First Chemical Tagging of a He-normal and a He-rich Dwarf, ApJ, 720, L41 (2010)
  * (120) D’Ercole, A., Vesperini, E., D’Antona, F., McMilan, S. L. W. & Recchi, S.: Formation and dynamical evolution of multiple stellar generations in globular clusters, MNRAS, 391, 825 (2008)
  * (121) Decressin, T., Charbonnel, C. & Meynet, G.: Origin of the abundance patterns in Galactic globular clusters: constraints on dynamical and chemical properties of globular clusters, A&A, 475, 859 (2007)
  * (122) Denissenkov, P. A. & Hartwick, F. D. A.: Supermassive stars as a source of abundance anomalies of proton-capture elements in globular clusters, MNRAS, 437, L21 (2014)
  * (123) de Mink, S. E., Pols, O. R., Langer, N. & Izzard, R.: Massive binaries as the source of abundance anomalies in globular clusters, A&A, 507, L1 (2009)
  * (124) Renzini, A., D’Antona, F., Cassisi, S. et al.: The Hubble Space Telescope UV Legacy Survey of Galactic Globular Clusters - V. Constraints on formation scenarios, MNRAS, 454, 4197 (2015)
  * (125) Sarajedini, A., Bedin, L. R., Chaboyer, B. et al.: The ACS Survey of Galactic Globular Clusters. I. Overview and Clusters without Previous Hubble Space Telescope Photometry, AJ, 133, 1658 (2007)
  * (126) Bedin, L. R., Piotto, G., Zoccali, M. et al.: The anomalous Galactic globular cluster NGC 2808. Mosaic wide-field multi-band photometry, A&A, 363, 159 (2000)
  * (127) Di Criscienzo, M., Tailo, M., Milone, A. P. et al.: An HST/WFC3 view of stellar populations on the horizontal branch of NGC 2419, MNRAS, 446, 1469 (2015)
  * (128) Piotto, G., King, I. R., Djorgovski, S. G. et al.: HST color-magnitude diagrams of 74 Galactic globular clusters in the HST F439W and F555W bands, A&A, 391, 945 (2002)
  * (129) D’Antona, F., Caloi, V., Montalbán, J., Ventura, P. & Gratton, R.: Helium variation due to self-pollution among Globular Cluster stars. Consequences on the horizontal branch morphology, A&A, 395, 69 (2002)
  * (130) Caloi, V. & D’Antona,F.: NGC 6441: another indication of very high helium content in globular cluster stars, A&A, 463, 959 (2007)
  * (131) Pilecki, B., Pietrzyński, G., Anderson, R. I. et al.: Cepheids with Giant Companions. I. Revealing a Numerous Population of Double-lined Binary Cepheids, ApJ, 910, 118 (2021)
  * (132) Abbott, D. C.: The return of mass and energy to the interstellar medium by winds from early-type stars, ApJ, 273, 723 (1982)
  * (133) Agertz, O., Kravtsov, A. V., Leitner, S. N. & Gnedin, N. Y.: Toward a Complete Accounting of Energy and Momentum from Stellar Feedback in Galaxy Formation Simulations, ApJ, 770, 25 (2013)
  * (134) Emerick, A., Bryan, G. L. & Mac Low, M.-M.: Stellar Radiation Is Critical for Regulating Star Formation and Driving Outflows in Low-mass Dwarf Galaxies, ApJ, 865, L22 (2018)
  * (135) Evans, C. J., Bresolin, F., Urbaneja, M. A. et al.: The ARAUCARIA Project: VLT-FORS Spectroscopy of Blue Supergiants in NGC 3109 – Classifications, First Abundances, and Kinematics. ApJ, 659, 1198 (2007)
  * (136) Castro, N., Urbanejea, M. A., Herrero, A. et al.: The ARAUCARIA project: Grid-based quantitative spectroscopic study of massive blue stars in NGC 55. A&A, 542, A79 (2012)
  * (137) Lamers, H. J.: The spectrum of the supergiant $\epsilon$ Orionis (BO Ia). I. Identifications, equivalent-widths, line profiles. A&AS, 7, 113 (1972)
  * (138) Dufton, P. L. & McKeith, C. D.: Copernicus observations of neutral helium lines in early-type stars. A&A, 81, 8 (1980)
  * (139) Drissen, L., Moffat, A. F. J., Walborn, N. R. & Shara, M. M.: The Dense Galactic Starburst NGC 3603. I. HST/FOS Spectroscopy of Individual Stars in the Core and the source of Ionization and Kinetic Energy. AJ, 110, 2235 (1995)
  * (140) Martins, F., Hervé, A., Bouret, J.-C. et al.: The MiMeS survey of magnetism in massive stars: CNO surface abundances of Galactic O stars. A&A, 575, A34 (2015)
  * (141) Cooke, R., Pettini, M. & Steidel, C. C.: One Percent Determination of the Primordial Deuterium Abundance, ApJ, 855, 102 (2018)
  * (142) Marcucci, L. E., Mangano, G., Kievsky, A. & Viviani, M.: Implication of the Proton-Deuteron Radiative Capture for Big Bang Nucleosynthesis, PhRvL, 116, 102501 (2016)
  * (143) Planck Collaboration, Ade, P. A. R., Aghanim, N. et al.: Planck 2015 results. XIII. Cosmological parameters, A&A, 594, A13 (2016)
  * (144) McGaugh, S., S., Schombert, J. M., de Blok, W. J. G. & Zagursky, M. J.: The Baryon Content of Cosmic Structures, ApJ, 708, L14 (2010)
  * (145) Werk, J. K., Prochaska, J. X., Tumlinson, J. et al.: The COS-Halos Survey: Physical Conditions and Baryonic Mass in the Low-redshift Circumgalactic Medium, ApJ, 792, 8 (2014)
  * (146) Nicastro, F., Kaastra, J., Krongold, Y. et al.: Observations of the missing baryons in the warm-hot intergalactic medium, Nature, 558, 406 (2018)
  * (147) Chatterjee, S., Law, C. J., Wharton, R. S. et al.: A direct localization of a fast radio burst and its host, Nature, 541, 58 (2017)
  * (148) Macquart, J.-P., Prochaska, J. X., McQuinn, M. et al.: A census of baryons in the Universe from localized fast radio bursts, Nature, 581, 391 (2020)
  * (149) Morrissey, P., Matuszewki, M., Martin, C. D. et al.: The Keck Cosmic Web Imager Integral Field Spectrograph, ApJ, 864, 93 (2018)
  * (150) Puech, M., Evans, C. J., Disseau, K. et al.: Simulating surveys for ELT-MOSAIC: status of the MOSAIC science case after phase A, Proc. SPIE, 10702, 8R (2018)
  * (151) Japelj, J., Laigle, C., Puech, M. et al.: Simulating MOS science on the ELT: Ly$\alpha$ forest tomography, A&A, 632, A94 (2019)
  * (152) Madau, P. & Dickinson, M.: Cosmic Star-Formation History, ARA&A, 52, 415 (2014)
  * (153) Tumlinson, J., Thom, C., Werk, J. K. et al.: The Large, Oxygen-Rich Halos of Star-Forming Galaxies Are a Major Reservoir of Galactic Metals, Sci, 334, 948 (2011)
  * (154) D’Odorico, V., Cristiani, S., Pomante, E. et al.: Metals in the z $\sim$ 3 intergalactic medium: results from an ultra-high signal-to-noise ratio UVES quasar spectrum, MNRAS, 463, 2690 (2016)
  * (155) Calderone, G., Boutsia, K., Cristiani, S. et al.: Finding the Brightest Cosmic Beacons in the Southern Hemisphere, ApJ, 887, 268 (2019)
  * (156) Boutsia, K., Grazian, A., Fontanot, F. et al.: The Luminosity Function of Bright QSOs at z $\sim 4$ 4 and Implications for the Cosmic Ionizing Background, ApJ, 912, 111 (2021)
  * (157) Noterdaeme, P., Petitjean, P., Ledoux, C., Srianand, R. & Ivanchik, A.: HD molecules at high redshift. A low astration factor of deuterium in a solar-metallicity DLA system at z = 2.418, A&A, 491, 397 (2008) (2008)
  * (158) Balashev, S., Klimenko, V. V., Noterdaeme, P. et al.: X-shooter observations of strong H2-bearing DLAs at high redshift, MNRAS, 490, 2668 (2019)
  * (159) Bolmer, J, Ledoux, C., Wiseman, P. et al.: Evidence for diffuse molecular gas and dust in the hearts of gamma-ray burst host galaxies. Unveiling the nature of high-redshift damped Lyman-$\alpha$ systems, A&A, 623, A43 (2019)
  * (160) Noterdaeme, P., Balashev, S., Krogager, J.-K. et al.: Proximate molecular quasar absorbers. Excess of damped H2 systems at $z_{\rm abs}$ $\approx$ zQSO in SDSS DR14, A&A, 627, A32 (2019)
  * (161) Noterdaeme, P., Balashev, S., Krogager, J.-K. et al.: Down-the-barrel observations of a multi-phase quasar outflow at high redshift. VLT/X-shooter spectroscopy of the proximate molecular absorber at $z$ $=$ 2.631 towards SDSS J001514$+$184212, A&A, 646, A108 (2021)
  * (162) Klimenko, V.V., Balashev, S.A.: Physical conditions in the diffuse interstellar medium of local and high-redshift galaxies: measurements based on the excitation of H2 rotational and CI fine-structure levels, MNRAS, 498, 1531, (2020)
  * (163) Kosenko, D.N., Balashev, S.A., Noterdaeme, P. et al.: HD molecules at high redshift: cosmic ray ionization rate in the diffuse interstellar medium, MNRAS, 505, 3810, (2021)
  * (164) Noterdaeme, P., Krogager, J.-K., Balashev, S. et al.: Discovery of a Perseus-like cloud in the early Universe. H I-to-H2 transition, carbon monoxide and small dust grains at $z_{\rm abs}$ $\approx$ 2.53 towards the quasar J0000$+$0048, A&A, 597, A82 (2017)
  * (165) Balashev, S. A., Noterdeame, P., Rahmani, H. et al.: CO-dark molecular gas at high redshift: very large H2 content and high pressure in a low-metallicity damped Lyman alpha system, MNRAS, 470, 2890 (2017)
  * (166) Finkelstein, S. L., D’Aloisio, A., Paardekooper, J.-P. et al.: Conditions for Reionizing the Universe with a Low Galaxy Ionizing Photon Escape Fraction, ApJ, 879, 36 (2019)
  * (167) Robertson, B. E., Ellis, R. S., Furlanetto, S. R. & Dunlop, J. S.: Cosmic Reionization and Early Star-forming Galaxies: A Joint Analysis of New Constraints from Planck and the Hubble Space Telescope, ApJ, 802, L19
  * (168) Giallongo, E., Grazian, A., Fiore, F. et al.: Space Densities and Emissivities of Active Galactic Nuclei at $z$ $>$ 4, ApJ, 884, 19 (2019)
  * (169) Fontanot, F., Cristiani, S. & Vanzella, E.: On the relative contribution of high-redshift galaxies and active galactic nuclei to reionization, MNRAS, 425, 1413 (2012)
  * (170) Haardt, F. & Salvaterra, R.: High-redshift active galactic nuclei and H I reionisation: limits from the unresolved X-ray background, A&A, 575, L16 (2015)
  * (171) Poulin, V., Serpico, P. D. & Lesgourgues, J.: Dark Matter annihilations in halos and high-redshift sources of reionization of the universe, JCAP, 12, 41 (2015)
  * (172) Worseck, G., Prochaska, J. X., O’Meara, J. M. et al.: The Giant Gemini GMOS survey of zem ¿ 4.4 quasars - I. Measuring the mean free path across cosmic time, MNRAS, 445, 1745 (2014)
  * (173) Cristiani, S., Serrano, L. M., Fontanot, F., Vanzella, E. & Monaco, P.: The spectral slope and escape fraction of bright quasars at $z$ $\sim$ 3.8: the contribution to the cosmic UV background, MNRAS, 462, 2478 (2016)
  * (174) Grazian, A., Giallongo, E., Boutsia, K. et al.: The contribution of faint AGNs to the ionizing background at $z$ $\sim$ 4, A&A, 613, A44 (2018)
  * (175) Izotov, Y. I., Orlitová, I., Schaerer, D. et al.: Eight per cent leakage of Lyman continuum photons from a compact, star-forming dwarf galaxy, Nature, 529, 178 (2016)
  * (176) Izotov, Y. I., Schaerer, D., Thuan, T. X. et al.: Detection of high Lyman continuum leakage from four low-redshift compact star-forming galaxies, MNRAS, 461, 3683 (2016)
  * (177) Izotov, Y. I., Schaerer, D., Worseck, G. et al.: J1154$+$2443: a low-redshift compact star-forming galaxy with a 46 per cent leakage of Lyman continuum photons, MNRAS, 474, 4514 (2018)
  * (178) Shapley, A. E., Steidel, C. C., Strom, A. L. et al.: Q1549-C25: A Clean Source of Lyman-Continuum Emission at $z$ $=$ 3.15, ApJ, 826, L24 (2016)
  * (179) Vanzella, E., de Barros, S., Vasei, K. et al.: Hubble Imaging of the Ionizing Radiation from a Star-forming Galaxy at $z$ $=$ 3.2 with fesc $>$ 50%, ApJ, 825, 41 (2016)
  * (180) Bian, F., Fan, X., McGreer, I., Cai, Z. & Jiang, L.: High Lyman Continuum Escape Fraction in a Lensed Young Compact Dwarf Galaxy at $z$ $=$ 2.5, ApJ, 837, L12 (2017)
  * (181) Vanzella, E., Nonino, M., Cupani, G. et al.: Direct Lyman continuum and Ly $\alpha$ escape observed at redshift 4, MNRAS, 476, L15 (2018)
  * (182) Saha, K., Tandon, S. N., Simmonds, C. et al.: AstroSat detection of Lyman continuum emission from a $z$ $=$ 1.42 galaxy, NatAs, 4, 1185 (2020)
  * (183) Rivera-Thorsen, T., Emil, D., Håkon, C. et al.: Gravitational lensing reveals ionizing ultraviolet photons escaping from a distant galaxy, Sci, 366, 738 (2019)
  * (184) Bik, A., Östlin, G., Menacho, V. et al.: Super star cluster feedback driving ionization, shocks and outflows in the halo of the nearby starburst ESO 338-IG04, A&A, 619, A131 (2018)
  * (185) Micheva,G., Christian Herenz, E., Roth, M. M., Östlin, G. & Girichidis, P.: IFU investigation of possible Lyman continuum escape from Mrk 71/NGC 2366, A&A, 623, A145 (2019)
  * (186) Heckman, T. M., Borthakur, S., Overzier, R. et al.: Extreme Feedback and the Epoch of Reionization: Clues in the Local Universe, ApJ, 730, 5 (2011)
  * (187) Vanzella, E., Caminha, G. B., Calura, F. et al.: Ionizing the intergalactic medium by star clusters: the first empirical evidence, MNRAS, 491, 1093 (2020)
  * (188) Steidel, C. C., Bogosavljević, M., Shapley, A. E. et al.: The Keck Lyman Continuum Spectroscopic Survey (KLCS): The Emergent Ionizing Spectrum of Galaxies at $z$ $\sim$ 3, ApJ, 869, 123 (2018)
  * (189) Piran, T., Bromberg, O., Nakar, E. & Sari, R.: The long, the short and the weak: the origin of gamma-ray bursts, RSPTA, 371, 0273 (2013)
  * (190) Zhang, B.: Gamma-ray burst afterglows, AdSpR, 40, 1186 (2007)
  * (191) Gehrels, N., Chincarini, G., Giommi, P. et al.: The Swift Gamma-Ray Burst Mission, ApJ, 611, 1005 (2004)
  * (192) Fox, A. J., Ledoux, C., Vreeswijk, P. M., Smette, A. & Jaunsen, A. O.: High-ion absorption in seven GRB host galaxies at z = 2-4. Evidence for both circumburst plasma and outflowing interstellar gas, A&A, 2008, 491, 189 (2008)
  * (193) D’Elia, V., Fiore, F., Perna, R. et al.: The Prompt, High-Resolution Spectroscopic View of the ‘Naked-Eye’ GRB080319B, ApJ, 694, 332 (2009)
  * (194) Vreeswijk P. M., Ledoux C., Smette A., et al.: Rapid-response mode VLT/UVES spectroscopy of GRB 060418. Conclusive evidence for UV pumping from the time evolution of Fe II and Ni II excited- and metastable-level populations, A&A, 468, 83 (2007)
  * (195) Li, L.-X. & Paczy nski, B.: Transient Events from Neutron Star Mergers, ApJ, 507, L59 (1998)
  * (196) Abbott, B. P., Abbott, R., Abbott, T. D. et al.: GW170814: A Three-Detector Observation of Gravitational Waves from a Binary Black Hole Coalescence, PhRvL, 119, 1101 (2017)
  * (197) Tanvir, N., Levan, A. J., González-Fernández, C. et al.: The Emergence of a Lanthanide-rich Kilonova Following the Merger of Two Neutron Stars, ApJ, 848, L27 (2017)
  * (198) Barnes, J. & Kasen, D.: Effect of a High Opacity on the Light Curves of Radioactively Powered Transients from Compact Object Mergers, ApJ, 775, 18 (2013)
  * (199) Evans, P. A., Cenko, S. B., Kennea, J. A. et al.: Swift and NuSTAR observations of GW170817: Detection of a blue kilonova, Sci, 358, 1565 (2017)
  * (200) Arcavi, I.: The First Hours of the GW170817 Kilonova and the Importance of Early Optical and Ultraviolet Observations for Constraining Emission Models, ApJ, 855, L23 (2018)
  * (201) Quimby R. M., Aldering G., Wheeler J. C., et al.: SN 2005ap: A Most Brilliant Explosion, ApJL, 668, L99 (2007)
  * (202) Gal-Yam, A.: Luminous Supernovae, Sci, 337, 927 (2012)
  * (203) Gal-Yam, A.: The Most Luminous Supernovae, ARA&A, 57, 305 (2019a)
  * (204) De Cia A., Gal-Yam A., Rubin A., et al.: Light Curves of Hydrogen-poor Superluminous Supernovae from the Palomar Transient Factory, ApJ, 860, 100 (2018)
  * (205) Lunnan R., Chornock R., Berger E., et al.: Hydrogen-poor Superluminous Supernovae from the Pan-STARRS1 Medium Deep Survey, ApJ, 852, 81 (2018)
  * (206) Angus C. R., Smith M., Sullivan M., et al.: Superluminous supernovae from the Dark Energy Survey, MNRAS, 487, 2215 (2019)
  * (207) Chen Z. H., Yan L., Kangas T., et al.: The Hydrogen-Poor Superluminous Supernovae from the Zwicky Transient Facility Phase-I Survey: I. Data, arXiv:2202.02059 (2022a)
  * (208) Chen Z. H., Yan L., Kangas T., et al.: The Hydrogen-Poor Superluminous Supernovae from the Zwicky Transient Facility Phase-I Survey: II. Light Curve Modeling and Analysis, arXiv:2202.02060 (2022b)
  * (209) Cooke J., Sullivan M., Gal-Yam A., et al.: Superluminous supernovae at redshifts of 2.05 and 3.90, Nature, 491, 228 (2012)
  * (210) Heger & Woosley: The Nucleosynthetic Signature of Population III, ApJ, 567, 532 (2002)
  * (211) Gal-Yam A., Mazzali P., Ofek E. O., et al.: Supernova 2007bi as a pair-instability explosion, Nature, 462, 624 (2009)
  * (212) Nicholl M., Smartt S. J., Jerkstrand A., et al.: Slowly fading super-luminous supernovae that are not pair-instability explosions, Nature, 502, 346 (2013)
  * (213) Inserra C., Nicholl M., Chen T.-W., et al.: Complexity in the light curves and spectra of slow-evolving superluminous supernovae, MNRAS, 468, 4642 (2017)
  * (214) Neill J. D., Sullivan M., Gal-Yam A., et al.: The Extreme Hosts of Extreme Supernovae, ApJ, 727, 15 (2011)
  * (215) Vreeswijk P. M., Savaglio S., Gal-Yam A., et al.: The Hydrogen-poor Superluminous Supernova iPTF 13ajg and its Host Galaxy in Absorption and Emission, ApJ, 797, 24 (2014)
  * (216) Leloudas G., Schulze S., Krühler T., et al.: Spectroscopy of superluminous supernova host galaxies. A preference of hydrogen-poor events for extreme emission line galaxies, MNRAS, 449, 917 (2015)
  * (217) Lunnan R., Chornock R., Berger E., Rest A., Fong W., Scolnic D., Jones D. O., et al.: Zooming In on the Progenitors of Superluminous Supernovae With the HST, ApJ, 804, 90 (2015)
  * (218) Perley D. A., Quimby R. M., Yan L., et al.: Host-galaxy Properties of 32 Low-redshift Superluminous Supernovae from the Palomar Transient Factory, ApJ, 830, 13 (2016)
  * (219) Chen T.-W., Smartt S. J., Yates R. M., et al.: Superluminous supernova progenitors have a half-solar metallicity threshold, MNRAS, 470, 3566 (2017)
  * (220) Schulze S., Krühler T., Leloudas G., et al.: Cosmic evolution and metal aversion in superluminous supernova host galaxies, MNRAS, 473, 1258 (2018)
  * (221) Inserra C., Smartt S. J., Jerkstrand A., et al.: Super-luminous Type Ic Supernovae: Catching a Magnetar by the Tail, 2013, ApJ, 770, 128 (2013)
  * (222) Scovacricchi D., Nichol R. C., Bacon D., et al..: Cosmology with superluminous supernovae, MNRAS, 456, 1700 (2016)
  * (223) Quimby R. M., De Cia A., Gal-Yam A., et al.: Spectra of Hydrogen-poor Superluminous Supernovae from the Palomar Transient Factory, ApJ, 855, 2 (2018)
  * (224) Gal-Yam A.: A Simple Analysis of Type I Superluminous Supernova Peak Spectra: Composition, Expansion Velocities, and Dynamics, ApJ, 882, 102 (2019b)
  * (225) Graham M. J., Kulkarni S. R., Bellm E. C., et al.: The Zwicky Transient Facility: Science Objectives, PASP, 131, 078001 (2019)
  * (226) Yan L., Perley D. A., De Cia A., et al.: Far-UV HST Spectroscopy of an Unusual Hydrogen-poor Superluminous Supernova: SN2017egm, ApJ, 858, 91 (2018)
  * (227) Ledoux C., Petitjean P., Fynbo J. P. U., et al.: Velocity-metallicity correlation for high-z DLA galaxies: evidence of a mass-metallicity relation?, A&A, 457, 71 (2006)
  * (228) De Cia A., Ledoux C., Fox A. J., et al.: Rapid-response mode VLT/UVES spectroscopy of super iron-rich gas exposed to GRB 080310. Evidence of ionization in action and episodic star formation in the host, A&A, 545, A64 (2012)
  * (229) Lunnan R., Fransson C., Vreeswijk P. M., et al.: A UV resonance line echo from a shell around a hydrogen-poor superluminous supernova, NatAs, 2, 887 (2018)
  * (230) Rigaut, F., McDermid, R., Cresci, G. et al.: MAVIS on the VLT: A Powerful, Synergistic ELT Complement in the Visible, Msngr, 185, 7 (2021)
  * (231) Marconi, A., Abreu, M., Adibekyan, V. et al.: HIRES, the High-resolution Spectrograph for the ELT, Msngr, 192, 27 (2021)
  * (232) Barbuy, B., Spite, M., Hill, V. et al. A&A, 435, A60 (2011)
  * (233) Steidel, C. C., Shapley, A. E., Pettini, M. et al. ”A Survey of Star-forming Galaxies in the 1.4 $\lesssim$ $z$ $\lesssim$ 2.5 Redshift Desert: Overview”, ApJ, 604, 534 (2004)
  * (234) Genoni, M., Landoni, M., Cupani, G. et al.: The CUBES Instrument model and simulation tools, ExA, arXiv:2203.15477, in press as part of the CUBES Special Issue.
  * (235) Calcines, A., Wells, M., O’Brien, K. et al., ”Design of the VLT-CUBES image slicers”, ExA, in press as part of the CUBES Special Issue.


The space $Y_t$ consists of many components which we believe might be easier to understand visually. We therefore recommend that the reader study <ref> and <ref> in order to get a better understanding of the role of the different components. The induction hypothesis we will use in our construction is as follows.

Existence of components of $\aspace{t}$:

* the 2-simplices of $\aspace{t}$ are partitioned into two families of subcomplexes:

* for every edge $uv$ with $u,v\in F_t\cup X_t$ and where $u$ and/or $v$ in $F_t$, $Y_t$ contains a cylinder shaped subcomplex $\aspace{t}^{uv}$. The two boundary components of $\aspace{t}^{uv}$ are denoted $IN(\aspace{t}^{uv})$ and $OUT(\aspace{t}^{uv})$. [Intuitively, this is the edge gadget for $uv$ described in <ref>.]

* for every vertex $v \in F_t \cup X_t$, $\aspace{t}$ contains a cylinder shaped subcomplex $\aspace{t}^v$.[Essentially, $Y_t^v$ is the vertex gadget described in <ref> for all $v\in F_t$. Technically, the two simplicial complexes are slightly different as the gadget constructed in this induction contains some extra cylinders added for cosmetic reasons, but they are still homeomorphic.]

* the 2-simplices of $\aspace{t}^v$ are in turn partitioned by into the two subcomplexes $\mathcal{A}_t^v$ and $\mathcal{B}_t^v$. [The subcomplex $\mathcal{A}_t^v$ is the subcomplex of the vertex gadget that is attached to outgoing edge gadgets, and $\mathcal{B}_t^v$ is the subcomplex of the vertex gadget attached to incoming edge gadgets.] The complexes $\mathcal{A}_t^v$ and $\mathcal{B}_t^v$ satisfy the following properties:

* $\mathcal{A}_t^v$ contains a boundary component $\overline{\mathcal{A}_t^v}$ with a cylinder neighbourhood.

* $\mathcal{B}_t^v$ contains a boundary component $\overline{\mathcal{B}_t^v}$ with a cylinder neighbourhood.

* if $v \in X_t$ then $\mathcal{A}_t^v$ and $\mathcal{B}_t^v$ are disjoint.

* if $v \in F_t$ then $\mathcal{A}_t^v$ intersects $\mathcal{B}_t^v$ at $\overline{\mathcal{A}_t^v} = \overline{\mathcal{B}_t^v}$.

* for every edge $uv$ with $u,v\in F_t\cup X_t$ and where $u$ and/or $v$ in $F_t$:

* $\mathcal{B}_t^u$ intersects $\aspace{t}^{uv}$ at $IN(\aspace{t}^{uv})$.

* $\mathcal{A}_t^v$ intersects $\aspace{t}^{uv}$ at $OUT(\aspace{t}^{uv})$.

An example of the different components of $Y_t$. In particular, we have zoomed in on the construction of the space from <ref> at node $t=6$. We followed the construction presented in <ref> to make this space.

Conditions on the path decomposition $\tdspace{t}$ of $Y_t$:

* $\tdspace{t}$ is a path decomposition of the Hasse diagram of $Y_t$

* $\tdspace{t}$ contains a bag $R_t$ with degree $\leq 1$ that is precisely equal to set of the (cylindrical) neighbourhoods of $\overline{\mathcal{A}_t^v}$ and $\overline{\mathcal{B}_t^v}$ for every $v\in X_t$.

* The width of $\tdspace{t} \leq c\cdot \operatorname{npd}(D)$ for some fixed constant $c$.

Properties of $Y_t$ used in the proof of correctness:

* For every edge $uv$ with $u,v\in F_t\cup X_t$ where $u$ and/or $v$ in $F_t$ there is a...

* cylinder in $\mathcal{B}_t^u$ with boundary components $OUT(\aspace{t}^{uv})$ and $\overline{\mathcal{B}_t^u}$

* cylinder in $\mathcal{A}_t^v$ with boundary components $IN(\aspace{t}^{uv})$ and $\overline{\mathcal{A}_t^v}$

* If $M$ is a (non-empty) $2$-manifold in $\mathcal{B}_t^u$ having a boundary that a) intersects some other component and b) has a boundary on the boundary of $\mathcal{B}_t^u$ then $M$ is a cylinder having $OUT(\aspace{t}^{uv})$ as one boundary component and $\overline{\mathcal{B}_t^u}$ as the other. Furthermore, any two such $2$-manifolds in $\mathcal{B}_t^u$ intersect and $M\cup\aspace{t}^{uv}$ is a cylinder.

* If $M$ is a (non-empty) $2$-manifold in $\mathcal{A}_t^v$ having a boundary that a) intersects some other component and b) has a boundary on the boundary of $\mathcal{A}_t^v$ then $M$ is a cylinder having $IN(\aspace{t}^{uv})$ as one boundary component and $\overline{\mathcal{A}_t^v}$ as the other. Furthermore, any two such $2$-manifolds in $\mathcal{A}_t^v$ intersect and $M\cup\aspace{t}^{uv}$ is a cylinder.

§.§.§ Reduction by Structural Induction on Path Decompositions

There are three kinds of bags in a path decomposition of a graph, each of which requires special attention. We need to prove that for every kind of node $t$ we can construct a space $\aspace{t}$ and a path decomposition $\tdspace{t}$ (in polynomial time) satisfying the induction hypothesis. If $t$ has a child node $t'$ we may assume by induction that we have access to a space $\aspace{t'}$ and a path decomposition $\tdspace{t'}$ that satisfies the induction hypothesis at the child node.
The Leaf Node is particularly easy to deal with. In particular, the empty simplicial complex and the “empty” path decomposition (containing a single empty bag) satisfies the criteria of the induction hypothesis.

Let $D$ be a directed graph, $\ntd{D}$ be a nice path decomposition of $D$ and $t$ be an leaf node in $\ntd{D}$. Then we can construct a space $\tdspace{t}$ and a path decomposition $\tdspace{t}$ satisfying the induction hypothesis for the node $t$ in constant time.

The leaf node $t$ is the base case of the inductive construction. By definition there are no explored/forgotten nodes. This means that setting $\aspace{t}=\emptyset$ is a valid construction. The path decomposition is also easily defined, as it consists of a single bag, $R_t$, which is empty. It is trivial to verify that this construction satisfies the induction hypothesis.

The Introduce Bag is a bit more complicated than the leaf bag. Here we need to extend the space and path decomposition we have constructed inductively by adding the space $Y_t^{v}$ for the new vertex. We have decided to add edge gadgets when vertices are forgotten, so this procedure is not too complicated. The space representing the new vertex is just the disjoint union of two cylinders.

Let $D$ be a directed graph, $\ntd{D}$ be a nice path decomposition of $D$ and $t$ be an introduce node in $\ntd{D}$ with a child node $t'$. Given a space $\aspace{t'}$ together with a path decomposition $\tdspace{t'}$ satisfying the induction hypothesis for the node $t'$, we can construct a space $\tdspace{t}$ and a path decomposition $\tdspace{t}$ satisfying the induction hypothesis for the node $t$ in polynomial time.

An overview of how to construct the space $\aspace{t}$ and the path decomposition $\ntd{Y_t}$ from $\aspace{t'}$ and $\ntd{Y_{t'}}$ at an introduce bag. In particular, the top left figure shows the contents of the bags of the input path decomposition at node $t$ and $t'$. The lower left figure shows how to extend the space $Y_{t'}$ to $Y_t$ and the rightmost figure shows how to extend the path decomposition $\ntd{Y_{t'}}$ by adding two bags to $R_{t'}$. The correspondence between nodes and spaces is given by color coding.

Let $t$ be an introduce bag with a child bag $t'$ and let $w$ be the newly introduced vertex. By induction, we can assume that we have already constructed the space $\aspace{t'}$ and that it's $2$-simplices are partitioned by subcomplexes in the way specified by the induction hypothesis. We also assume that we have a path decomposition $\tdspace{t'}$ and that contains the bag $R_t$. The new space we construct, $\aspace{t}$, is defined by <ref>. Note that we extend each space $Y_t^{u}$ for each existing vertex $u$ with a cylinder and that we add components $\mathcal{A}_t^w$ and $\mathcal{B}_t^w$ for the newly introduced vertex $w$. The path decomposition $\tdspace{t}$ of $\aspace{t}$ is similarly defined as an extension of the path decomposition of $\tdspace{t'}$ where we add one bag attached to $R_{t'}$ containing the simplices of $R_{t'}$ together with the new simplices. Then we attach $R_t$ to this intermediate bag, which contains the new boundaries and their cylindrical neighbourhoods, see <ref> above for details on the path decomposition.

We are now ready to prove the statements of the induction hypothesis for the new space and path decomposition. The two first groups of statements are rather trivial to prove, as they generally hold by construction and an elementary induction argument. We first discuss the statements regarding the properties of the components of $Y_t$

We added a component $Y_t^w$ for the vertex introduced to the bag. This component is in turn partitioned into $\mathcal{A}_t^w$ and $\mathcal{B}_t^w$, each containing precisely one cylinder, with one of the boundaries of each cylinder set to be equal to $\overline{\mathcal{A}_t^w}$ (respectively $\overline{\mathcal{B}_t^w}$). We also add two cylinders for each vertex $x$ in the bag and we attached these to the boundaries $\overline{\mathcal{A}_{t'}^x}$ and $\overline{\mathcal{B}_{t'}^x}$. The boundaries of these components are now set to be the other end of these cylinders (see <ref>) and they now belong to the component they are attached to. The other $2$-simplices of the space are partitioned in the same way they where in $Y_{t'}$. Since the newly added component is not adjacent to any forgotten vertex (by basic properties of path decompositions) and since no new nodes have been forgotten moving from bag $t'$ to bag $t$, the rest of the properties about the components of the space remain true.

A more detailed description of how to construct the space $\aspace{t}$ from $\aspace{t'}$. In particular, the figure includes some additional labels naming some of the components of the space that where not clearly marked in <ref>.

To check that the properties of the path decomposition $\ntd{Y_t}$ holds is equally elementary. First, the proposed set of bags is a path decomposition because every simplex is in some bag, every face/coface pair is contained in some bag and the bags containing any given simplex forms a connected sub path. A proof of each statement follows from construction and together with a simple proof by induction. The bag $R_t$ exists purely by construction and the proof that the width of the path decomposition $\ntd{Y_t}$ is linearly bounded by the $\ntd{D}$ again only requires a simple induction proof (combined with the observation that neither of the bags we added are too large).

Finally, the properties required for the correctness proof are equally simple at the introduce nodes. First, the existence of cylinders with boundaries $IN(Y_t^{uv})$ and $\overline{\mathcal{A}_t^v}$ follows by construction and an elementary inductive proof.

Properties 2 and 3 have similar proofs so we will only argue for property 3. In the case of components corresponding to the newly introduced vertex this is trivially true by construction, as this component contains no such manifolds. For the components corresponding to the other vertices in the bag these properties can be proved by induction. More concretely, let $M$ be a manifold contained in $\mathcal{A}_t^v$ and assume it has a boundary that a) intersects some other component of the space and b) has a boundary on the boundary of $\mathcal{A}_t^v$. Then $M$ cannot be contained entirely in $\mathcal{A}_{t'}^v$ because by induction this means that $M$ must have $\overline{\mathcal{A}_{t'}^v}$ as a boundary component which is not a boundary of $\mathcal{A}_t^v$ nor is part of another component. By construction, if $M$ contains one of the newly added simplices it must contain all to satisfy a) and b) and hence one boundary component of $M$ is $\overline{\mathcal{A}_t^v}$. Furthermore, $M \cap \mathcal{A}_{t'}^v$, is now a manifold and must therefore be a cylinder with boundary components $\overline{\mathcal{A}_{t'}^v}$ and some $IN(\aspace{t}^{uv})$.

The Forget Bag is the most complicated, but we have been building up to it gradually. It is in many ways similar to the introduce bag in that we we need to extend the space and path decomposition we have constructed inductively. Here, instead of beginning to encode a vertex we need to finish it. In particular, we need to encode the edges between the forgotten vertex and its neighbours in the bag. This guarantees that every edge is encoded precisely once, since every edge there is precisely one bag containing both ends of the edge and where one end is forgotten. After these edges have been encoded, we just have to connect the two components $\mathcal{A}_t^v$ and $\mathcal{B}_t^v$ for the forgotten vertex.

Let $D$ be a directed graph, $\ntd{D}$ be a nice path decomposition of $D$ and $t$ be an forget node in $\ntd{D}$ with a child node $t'$. Given a space $\aspace{t'}$ together with a path decomposition $\tdspace{t'}$ satisfying the induction hypothesis for the node $t'$, we can construct a space $\tdspace{t}$ and a path decomposition $\tdspace{t}$ satisfying the induction hypothesis for the node $t$ in polynomial time.

An overview of how to construct the space $\aspace{t}$ and the path decomposition $\ntd{Y_t}$ from $\aspace{t'}$ and $\ntd{Y_{t'}}$ at a forget bag. In particular, the top left figure shows the contents of the bags of the input path decomposition at node $t$ and $t'$. The lower left figure shows how to extend the space $Y_{t'}$ to $Y_t$ and the rightmost figure shows how to extend the path decomposition $\ntd{Y_{t'}}$ by adding two bags to $R_{t'}$. The correspondence between nodes and spaces is given by color coding. Each of the black components are edge gadgets.

Let $t$ be an forget bag with a child bag $t'$ and let $v$ be the newly introduced vertex. By induction, we can assume that we have already constructed the space $\aspace{t'}$ and that it is partitioned as specified in the induction hypothesis. We also assume that we have a path decomposition $\tdspace{t'}$ containing a bag $R_t$. The construction of the new space, $\aspace{t}$, and its path decomposition is sketched in <ref>. The partitioning of the simplicies in the new space is shown in <ref>.

A more detailed description of how to construct the space $\aspace{t}$ from $\aspace{t'}$. In particular, the figure includes some additional labels indicating some of the components of the space that were not clearly marked in <ref>.

We use the same partitioning of the $2$-simplices contained in $Y_{t'}$ that we have constructed inductively. The newly added simplices to the space are partitioned into new and existing components in the way that is indicated by <ref>. In particular, there are simplices added because of edges going to (resp. from) vertices in the bag from (resp. to) the vertex that is forgotten. The $2$-simplices of such an edge, $yv$ (resp. $vz$), make up a new component denoted $Y_t^{yv}$ (resp. $Y_t^{vz}$). The distinguished boundaries of the various components are updated as illustrated in the figures above. We do not discuss the first groups two of statements involved in the induction hypothesis this time around, because a) these “proofs” are essentially just observations and b) they are very similar to those we saw at the introduce bag.

We will now prove the properties required to show the correctness of the reduction.

First, we prove the existence of cylinders in $\mathcal{A}_t^x$ with boundaries $IN(Y_t^{xy})$ and $\overline{\mathcal{A}_t^v}$ if at least one of the vertices $x$ or $y$ has been forgotten. The exact argument here depends on the vertex $x$. The only interesting case is if $x$ is in the bag at node $t'$. If the component $IN(Y_t^{xy})$ was added when we moved from bag $t'$ to $t$ then it is clear that such a cylinder exists by construction. If $IN(Y_t^{xy})$ was added earlier, then there is a cylinder from this boundary to $\overline{\mathcal{A}_{t'}^x}$ by the induction hypothesis. This cylinder can then be composed with the cylinder from $\overline{\mathcal{A}_{t'}^x}$ to $\overline{\mathcal{A}_{t}^x}$. An analogous argument can be used for the cylinders in $\mathcal{B}_{t}^x$.

Properties 2 and 3 have similar proofs, so we will only present the argument for property 3. Furthermore, we will only consider the case where the component is $\mathcal{A}_{t}^v$, where $v$ is the node that is being forgotten. The proofs for the other cases (in the case of different component and spaces corresponding to different vertices) the arguments are analogous.

By the same argument we saw at the introduce node, we can show that any manifold $M$ in $\mathcal{A}_{t}^v$ must intersect the newly added simplices. There are now two cases: either $M$  intersects $\mathcal{A}_{t'}^v$ or it does not. If $M$ intersects $\mathcal{A}_{t'}^v$ then we can make the argument that $M\cap \mathcal{A}_{t'}^v$ is a cylinder with one boundary component equal to some $IN(Y_{t}^{yv})$ for some previously forgotten node $y$ adjacent to $v$ and the other boundary component equal to $\overline{\mathcal{A}_{t'}^v}$. The latter is not a boundary of $\mathcal{A}_{t}^v$, so $M$ must contain some of the newly added $2$-simplices in $\mathcal{A}_{t}^v$. Because of the singularities, we can never add simplices so that our manifold $M$ have one of the $IN(Y_{t}^{u''v})$ as boundaries. Indeed, our only option is to move towards $\overline{\mathcal{A}_{t}^v}$. A similar argument works in the case when $M$ is entirely contained as a submanifold of the newly added simplices. If you assume $M$ to have some $IN(Y_{t}^{u''v})$ as one of its boundary components, then you are forced by the singularites to add $2$-simplices to $M$ until you end at $\overline{\mathcal{A}_{t}^v}$.

§.§ Proof of Correctness

Having done most of the work in the previous section, the actual proof that the reduction works is a simple lemma.

The directed graph $D$ contains $\ell$ disjoint directed cycles if and only if $Y_D = Y_{root}$ contain $\ell$ disjoint manifolds. Furthermore, every manifold without a boundary contained in $Y_D$ is a torus.

We prove the forward direction first. Let $C_1,\dots, C_\ell$ be disjoint directed cycles in $D$. Then we know there are $\ell$ disjoint tori $T(C_1),\dots, T(C_\ell)$ in $Y_D$. These are obtained in the obvious way: Let $C_1$ be the cycle on the directed edges $(v_1v_2,v_2v_3,\dots, v_{p-1}v_p, v_{p}v_1)$. Then by Property 1 we know that $Y_D$ contains a cylinder in $\mathcal{B}^{v_1}$ attaching $\overline{\mathcal{B}^{v_1}}$ to $IN(Y^{v_1v_2})$ and a cylinder in $\mathcal{A}^{v_2}$ attaching $OUT(Y^{v_1v_2})$ to $\overline{\mathcal{A}^{v_2}}$. There is also a cylinder $Y^{v_1v_2}$ attaching $IN(Y^{v_1v_2})$ to $OUT(Y^{v_1v_2})$ by construction. By Properties 2 and 3, we know that the unions of these intersecting cylinders form a new cylinder (or potentially a torus if it's two boundary components are identified). The same is true for all edges in $C_1$.

Since $C_1$ is a cycle, every vertex is unique, so there are by construction no intersection of these cylinders beyond those described in the above paragraph. Hence, if we let $T(C_1)$ be the union of all these cylinders, we have constructed our first torus. The other tori are constructed in the same way. Again, since the cycles are all disjoint, the tori constructed in this way can not intersect at any point. This concludes the forward direction.

For the other direction, we assume that $Y_D$ contains $\ell$ disjoint tori, $T_1,\dots, T_\ell$. Let us consider $T_1$. Since $T_1$ is a torus it must contain some $2$-simplex. This $2$-simplex must be contained in one of the three types of components of $Y_D$: $\mathcal{A}^v_2$, $\mathcal{B}^v_1$ or $Y^{v_1v_2}$.

Let us assume that the $2$-simplex belongs to $Y^{v_1v_2}$ (the other cases have similar arguments). We know from construction that $Y^{v_1v_2}$ is a cylinder and that only the boundary components of this cylinder are attached to other components of the space.
Since $T_1$ is a torus it should not have a boundary, which means that if one of the $2$-simplices of $Y^{v_1v_2}$ are in $T_1$ then all of $Y^{v_1v_2}$ must be contained in $T_1$. Moreover, the boundary component $IN(Y^{v_1v_2})$ intersects $\overline{\mathcal{A}{^v_2}}$. Since this cannot be a boundary in $T_1$, $T_1$ must itself intersect $\mathcal{A}^{v_2}$ in such a way that one of the boundaries of $T_1\cap \mathcal{A}^{v_2}$ is $IN(Y^{v_1v_2})$. By Property 3, $T_1$ intersects $\mathcal{A}^{v_2}$ as a cylinder with the other boundary equal to $\overline{\mathcal{A}^{v_2}}$.

Again, we have that $\overline{\mathcal{A}^{v_2}}$ cannot be a boundary of $T_1$, so $T_1$ must intersect $\overline{\mathcal{B}^{v_2}}$ in such a way that one of the boundaries of $T_1\cap \overline{\mathcal{B}^{v_2}}$ is $\overline{\mathcal{A}^{v_2}}=\overline{\mathcal{B}^{v_2}}$ This means (by Property 2) that the other boundary is some $OUT(Y^{v_2v_3})$. This argument is then repeated until we eventually have that $T_1$ intersects some component with one boundary equal to $OUT(Y^{v_1v_2})$. The edge gadgets the tori contain, $v_1v_2, v_2v_3 \dots, v_{p-1}v_p, v_{p}v_1$ will then by definition be our first cycle $C(T_1)$. Note that these vertices cannot have been repeated, since we assumed that $T_1$ was a torus. We construct the other cycles from the tori in similar ways. Again, the cycles will be vertex disjoint since intersecting cycles would imply intersecting tori.

This argument also proves that the only connected submanifolds without a boundary contained in $Y_D$ are tori.

As an immediate corollary we get the following results:

* Sending an instance $(D,\ell)$ of the problem to the instance $(Y_D,\ell)$ of the problem (where $Y_D$ is the input space and $\ell$ is the number of connected submanifolds) is a reduction.

* Sending an instance $(D,\ell)$ of the problem to the instance $(Y_D,\ell,\ell)$ of the problem (where $Y_D$ is the input space and $\ell$ is the number of connected submanifolds and the total genus) is a reduction.

* Sending an instance $(D,\ell)$ of the problem to the instance $(Y_D,(1: \ell))$ of the Subsurface Recognition problem (where $Y_D$ is the input space and $\ell$ is the number of connected submanifolds of genus $1$ we want to find) is a reduction.

Combine these results with the fact that the space $Y_D$ has a pathwidth that is linearly bounded by the pathwidth of $D$ and the ETH-lower bound for the problem parameterized by pathwidth, and we get <ref> as an immediate consequence. In particular, this theorem also implies the same ETH-lower bounds for simplicial complexes of bounded treewidth, matching our algorithmic upper bounds for the problem and the problem.

§ CONCLUSION

In this paper, we consider the parameterized complexity of several variants of the problem of finding surfaces in 2-dimensional simplicial complexes with respect to the treewidth of the Hasse diagram. We give ETH-optimal algorithms for the and problems. We also give an ETH-based lower bound for Subsurface Recognition and an FPT algorithm for . Several questions surrounding subsurface recognition remain open, such as

* whether the algorithm presented in this paper for is ETH-optimal;

* whether or not the Subsurface Recognition Problem is W[1]-hard when parameterized by the treewidth of the Hasse diagram.

Future work could either attempt to find better parameterized algorithms or prove stronger lower bounds for these problems.

§ PROOFS OF LEMMA <REF>, <REF>, AND <REF>

We will use our equivalence-preserving moves to show $(\overbar{aba^{-1}b^{-1}XY})=(\overbar{efe^{-1}f^{-1}YX})$.

\begin{align*}
(\overbar{aba^{-1}b^{-1}XY})&=(\overbar{a^{-1}b^{-1}XYab})&\hfill\text{by (4)}\\
&=(\overbar{a^{-1}cYaXc^{-1}})&\hfill\text{by Lemma \ref{lem:cell_multiple_boundaries}}\\
&=(\overbar{Xc^{-1}a^{-1}cYa})&\hfill\text{by (4)}\\
&=(\overbar{Xc^{-1}d^{-1}Ycd})&\hfill\text{by Lemma \ref{lem:cell_multiple_boundaries}}\\
&=(\overbar{dXc^{-1}d^{-1}Yc})&\hfill\text{by (4)}\\
&=(\overbar{dXeYd^{-1}e^{-1}})&\hfill\text{by Lemma \ref{lem:cell_multiple_boundaries}}\\
&=(\overbar{e^{-1}dXeYd^{-1}})&\hfill\text{by (4)}\\
&=(\overbar{e^{-1}f^{-1}YXef})&\hfill\text{by Lemma \ref{lem:cell_multiple_boundaries}}\\
&=(\overbar{efe^{-1}f^{-1}YX})&\hfill\text{by (4)}
\end{align*}

We first prove the sub-lemma that $(\overbar{aaXY})=(\overbar{bYbX^{-1}})$.

\begin{align*}
(\overbar{aaXY})&=(\overbar{YaaX})&\hfill\text{by (4)}\\
&=(\overbar{Yab})+(\overbar{b^{-1}aX})&\hfill\text{by (2)}\\
&=(\overbar{Yab})+(\overbar{X^{-1}a^{-1}b})&\hfill\text{by (3)}\\
&=(\overbar{bYa})+(\overbar{a^{-1}bX^{-1}})&\hfill\text{by (4)}\\
&=(\overbar{bYbX^{-1}})&\hfill\text{by (2)}
\end{align*}

We now use this sub-lemma to prove that $(\overbar{aaXY})=(\overbar{ddYX})$.

\begin{align*}
(\overbar{aaXY})&=(\overbar{bYbX^{-1}})&\hfill\text{by the sub-lemma}\\
&=(\overbar{XcY^{-1}c})&\hfill\text{by (3), where $c=b^{-1}$}\\
&=(\overbar{cXcY^{-1}})&\hfill\text{by (4)}\\
&=(\overbar{ddYX})&\hfill\text{by the sub-lemma}
\end{align*}

Rearranging $XY$ to $YX$ follows immediately from move (6). As $a$ appears only in the boundary of $a$, we can replace $a$ with new edges edges $ef$ by move (1) without changing the boundary of any other faces. We can then replace $ef$ with a new edge $d$ by move (1).

§ CHECKING THE LINK CONDITIONS OF SIMPLICES

In this section, we prove that if $\Sigma$ is a candidate solution at $t$ and $\Tilde\Sigma$ is the corresponding candidate solution at $t$, then we can verify that the link of a simplex $\sigma\in X_t$ is admissible or complete if we only have access to $\Tilde\Sigma$.

§.§ Checking the Link Condition of Edges

There is a simple and natural condition to verify that the link of an edge is admissible or complete. In a candidate solution $\Sigma$, the link of an edge $e$ is a set of vertices, one for each triangle incident to $e$. In the corresponding cell complex $\Tilde\Sigma$, the number of times $e$ appears in the boundary of a face equals the number of triangles incident to $e$ in $\Sigma$.

Let $\Sigma$ be a candidate solution at $t$, and let $\Tilde\Sigma$ be the corresponding cell complex at $t$. Let $e\in X_t$ be an edge. The number of times the real edge $e$ appears in the boundary of a face in $\Tilde\Sigma$ is the number of triangles in $\Sigma$ with $e$ in their boundary.

This is vacuously true for the simplicial complex $\Sigma$. Moreover, the only real edges that have been removed from $\Tilde\Sigma$ are those in $\Sigma\setminus X_t$, so no appearance of $e$ has been removed from $\Tilde\Sigma$. Therefore, the number of times $e$ appears in faces of $\Tilde\Sigma$ is the number of triangles in $\Sigma$ with $e$ in their boundary.

With this lemma in mind, the algorithm to check if the link of an edge is admissible or complete is simple: just count the number of times it appears in the cell complex. We can do this in $\OO(k)$ time by iterating through the edges in $\Tilde\Sigma$. The following lemmas are immediate.

Let $t$ be a node in the tree decomposition. Let $\Sigma$ be a candidate solution at $t$, and let $\Tilde\Sigma$ be the corresponding cell complex at $t$. Let $e\in S\cap X_t$ be an edge. The link of $e$ in $\Sigma$ is admissible if and only if

* $e\in B$ and the real edge $e$ appears at most once in the boundary of a face in $\Tilde{\Sigma}$, or

* $e\notin B$ and the real edge $e$ appears at most twice in the boundary of faces in $\Tilde{\Sigma}$.

Moreover, this condition can be checked on $\Tilde\Sigma$ in $\OO(k)$ time.

§.§ Checking the Link Conditions of Vertices

The key idea for checking the candidacy of vertices is that we can deduce information on the link of the vertex $v$ in a candidate solution $\Sigma$ based on the set of edges that enter $v$ in the corresponding cell complex $\Tilde\Sigma$. In particular, a path in the link of $v$ in $\Sigma$ exactly corresponds to a sequence of edges in the cell complex, and a cycle in the link of $v$ exactly corresponds to a cyclic sequence of successors in $\Tilde\Sigma$.

We will prove the following two lemmas in this section.

Let $\Sigma$ be a candidate solution at $t$, and let $\Tilde\Sigma$ be the corresponding cell complex at $t$. Let $v\in X_t$ be a vertex. The link $\lk_{\Sigma}{v}$ is admissible if and only if one of the following conditions hold.

* $v\in B$ and the edges entering $v$ in $\Tilde{\Sigma}$ form a cyclic sequence of successors, or

* the edges entering $v$ in $\Tilde{\Sigma}$ form a (possibly empty) collection of (non-cyclic) sequences of successors.

We will use the criteria in these lemmas to determine link admissibility and completeness in our algorithm. In particular, if there is a cell complex corresponding to a candidate solution with a vertex that does not satisfy the conditions of Lemma <ref>, we assume this algorithm is discarded.
We begin with a simple but helpful observation.

Let $\Sigma$ be a candidate solution at $t$, and let $\Tilde\Sigma$ be the corresponding cell complex at $t$. If a vertex $v\in X_t\cap\Sigma$, there is an edge incident to $v$ in $\Tilde{\Sigma}$.

A vertex $v$ is first added to $\Sigma$ when a triangle is added; in this case, $v$ is incident to one of the real edges of the triangle and the lemma is true. Moreover, while there is a real edge incident to $v$, the lemma remains true. We only need to verify that $v$ is incident to an edge after all real edges have been removed.
If $v\notin B$, then each real edge $e$ incident to $v$ is not in $B$ either, so $e$ would have been incident to two faces when it was removed by Lemma <ref>. In particular, when the last real edge $a$ incident to $v$ was removed, it must have had the form $(aa^{-1}X)$ in the cell complex. (If $a$ did not have this form, then $v$ would have to be incident to another edge. As this edge is not a real edge or a boundary dummy edge, it must be an interior dummy edge. However, as mentioned in Section <ref>, if a vertex is incident to an interior dummy edge, it can be incident to no other edges, including $a$.) Thus, removing $a$ adds an interior dummy edge incident to $v$ and the lemma is true.
If $v\in B$, then we claim $v$ must have been incident to at least one edge in $\Sigma\cap B$. If $v$ was only incident to edges in not in $B$, each of these edges would have been incident to two faces when it was removed. Therefore, $v$ would be incident to an interior dummy edge, which cannot be the case as it would make the link of $v$ inadmissible. Therefore, $v$ was incident to an edge in $\Sigma\cap B$, and this edge was replaced with a boundary dummy edge when it was removed. If this boundary dummy edge was ever replaced with a merge boundary dummy edge, then this would have been when the other endpoint was forgotten, and one of this new edge's endpoint would still be $v$.

Our goal in this section is to use sequences of successors in the cell complex $\Tilde\Sigma$ to deduce information on the links of vertices in the simplicial complex $\Sigma$. The following lemma shows what happens to the successors of a single edge when it is removed.

Let $a$ be an edge in $\Tilde{\Sigma}$ with a pair of successors $b^{-1}\neq a^{-1}$ and $c^{-1}\neq a^{-1}$. After removing the edge $a$ with the rules in Section <ref>, the edges $b$ and $c^{-1}$ will be successors to one another.

We verify this in each of the cases for removing the edge $a$. We start with the rules in Section <ref> for removing a forgotten edge. We do not need to verify cases 6 and 7 in this section; in case 6, $a^{-1}$ is a successor to $a$, and in case 7, $a$ has a single successor. We also do not need to verify the cases in Section <ref>. In case 1, $d$ is a successor to $d$. In case 2, both $d_1$ and $d_2$ have a single successor.
We can verify the remaining cases directly, namely

* $(\overbar{Xa})+(\overbar{a^{-1}Y})=(\overbar{b^{-1}X'a})+(\overbar{a^{-1}Y'^{-1}c})=(\overbar{b^{-1}X'Y'^{-1}c})$,

* $(\overbar{XaYa^{-1}})=(\overbar{Xab^{-1}Y'ca^{-1}})=(\overbar{X})(\overbar{b^{-1}Y'c})$,

* $(\overbar{XaYa})=(\overbar{c^{-1}X'ab^{-1}Y'a})=(\overbar{Y'^{-1}bc^{-1}X'})$,

* $(\overbar{Xa})(\overbar{Ya^{-1}})=(\overbar{c^{-1}X'a})(\overbar{Y'ba^{-1}})=(\overbar{Y'bc^{-1}X'})$,

* $(\overbar{Xa})(\overbar{Ya})=(\overbar{c^{-1}X'a})(\overbar{b^{-1}Y'a})=(\overbar{c^{-1}X'Y^{-1}b})$.

In case 2 above, note that this holds even if $Y$ only contains a single edge $c$. In this case, $c$ and $c^{-1}$ are a pair of successors to $a$. After removing $a$, then $(c^{-1})^{-1}=c$ is a successor to $c$ in the boundary component $(\overbar{c})$.

Recall that the goal of this section is to show that sequence of successors in $\Tilde\Sigma$ corresponds to a simple path in $\lk_{\Sigma}v$ and a cyclic sequence of successors in $\Tilde\Sigma$ corresponds to a simple cycle in $\lk_{\Sigma}v$. As a first step, Lemma <ref> shows that two consecutive edges $(w_1,v)$ and $(v,w_2)$ on a face in $\Tilde\Sigma$ correspond to a simple path or cycle in $\lk_{\Sigma}{v}$, and moreover, that these paths are pairwise disjoint except possibly at their endpoints. The proof of the main lemmas of this section will then show that a sequence of successors corresponds to the concatenation of these individual paths.
Before we can prove Lemma <ref>, we need to prove two other lemmas. Lemma <ref> proves that a boundary dummy edge replaces a path in the input boundary $B$. This lemma should not be surprising, as each boundary dummy edge either replaces an edge in $B$, or replaces two boundary dummy edges, each of which replaced a path in $B$.

Let $\Sigma$ be a candidate solution at $t$, and let $\Tilde\Sigma$ be the corresponding cell complex at $t$. If $\{w_1,w_2\}\in\Tilde\Sigma$ is a boundary dummy edge, then a simple segment $(w_1,u_1,\ldots,u_{l-1},w_2)$ of $B$ is a subcomplex of $\Sigma$. Moreover, if $\{w_1,w_2\}$ and $\{w_3,w_4\}$ are distinct boundary dummy edges, then the corresponding paths $(w_1,\ldots,w_2)$ and $(w_3,\ldots,w_4)$ are disjoint except possibly at their endpoints.

We can prove this induction on the length $l$ of the segment. Initially, a dummy edge $\{w_1,w_2\}$ replaces a real edge $\{w_1,w_2\}\in B$ when it is forgotten, so the statement is true for paths of length $l=1$.
Now assume the statement is true for paths of length less than $l$. The only other time a boundary dummy edge is added is when two dummy edges $\{w_1,v\}$ and $\{w_2,v\}$ sharing a common vertex $v$ are merged. The dummy edges replace paths $B_1=(w_1,\ldots,v)$ and $B_2=(v,\ldots,w_2)$ of $B$. As these paths are disjoint except at $v$, then $(w_1\ldots v\ldots w_2)$ is still a segment of $B$. Moreover, the path $(w_1,\ldots,w_2)$ is disjoint from the other paths corresponding to boundary dummy edges except possibly at $v$. If another path $(u_1,\ldots,u_2)$ intersected $(w_1,\ldots,v)$ at $v$, then $v$ would be incident to three edges in $B$, which cannot be the case as $B$ is a collection of simple cycles.

Let $A$ be a face in a cell complex $\Tilde\Sigma$. Lemma <ref> tells us that $A$ corresponds to a set of triangles.

Let $\Sigma$ be a candidate solution at $t$, and let $\Tilde\Sigma$ be the corresponding cell complex at $t$. Each face $A$ in $\Tilde{\Sigma}$ corresponds to a set of triangles in $\Sigma$.

We can see this by induction. If $A$ is a triangle in $K$, then this is obviously true. If $A\notin K$, then $A$ is the merge of two smaller faces that shared an edge, each of which corresponds to a set of triangles.

For a vertex $w$, let $\lk_{A}{w}$ denote the link of $w$ in $\cl A$, the closure of the set of triangles corresponding to $A$. We would like to say that $\lk_{A}{w}$ is a collection of simple paths or a simple cycle. We prove a lemma in this direction.

Let $A_1$ be a face in an annotated cell complex $\Tilde{\Sigma}$. Let $(w_1,w,w_2)$ be a segment on the boundary of $A_1$. There is a simple path $P_1$ in $\lk_{A_1}{w}$ such that

* if $\{w_1,w\}$ is a real edge, then one endpoint of $P_1$ is $w_1$;

* if $\{w_1,w\}$ is an interior dummy edge, the endpoints of $P_1$ are equal;

* if $\{w_1,w\}$ is a boundary dummy edge that replaces a segment $B_1=\{w_1,u_{l-1}\ldots,u_{1},w\}$ of $B$, then one endpoint of $P_1$ is $u_1$;

* if $w$ appears in another segment $(w_3,w,w_4)$ on the boundary of a face $A_2$ in $\Tilde{\Sigma}$, then the path $P_2$ in $\lk_{A_2}{v}$ and $P_1$ are disjoint.

We prove that if the lemma is true on an annotated cell complex $\Tilde{\Sigma}$, then it is true after removing an edge from $\Tilde{\Sigma}$. The condition of the lemma is defined facewise, so adding together two triangle-disjoint annotated cell complexes won't violate the condition.
An annotated cell complex defined by our algorithm is initially a simplicial complex before any edges are removed. The base case of our proof is therefore a face $A_1$ that is a single triangle $\{w_1,w,w_2\}\in K$. The link of $w$ in $\{w_1,w,w_2\}$ is the simple path $(w_1,w_2)$. If $w$ appears in a distinct triangle $\{w_3,w,w_4\}$, the link of $w$ in $\{w_3,w,w_4\}$ is the simple path $(w_3,w_4)$. As the triangles are distinct, the paths $(w_1,w_2)$ and $(w_3,w_4)$ can share at most one endpoint.
Now assume the lemma is true for an annotated cell complex $\Tilde{\Sigma}$. We will show the lemma is true after removing a real edge $\{w,u\}$ from two (possibly the same) faces. Let $(w_1,w,u)$ and $(u,w,w_2)$ be segments on the boundary of faces $A_1$ and $A_2$. By the lemma, there is a path $P_1$ in $\lk_{A_1}{w}$ with $u$ as an endpoint. Likewise, there is a path $P_2$ in $\lk_{A_2}{w}$ with $u$ as an endpoint. Merging the faces $A_1$ and $A_2$ at $\{w,v\}$ will create a face $A_3$ with $(w_1,w,w_2)$ on its boundary. The paths $P_1$ and $P_2$ are disjoint except possibly at their endpoints, so the concatenation of $P_1$ and $P_2$ is a simple path with endpoints $w_1$ and $w_2$. Merging $P_1$ and $P_2$ creates a new path with $u$ in its interior. The vertex $u$ does not appear in any other path $P_3$ in $\lk_{\Sigma}{w}$. If it did, it would have to be the endpoint of $P_3$ as $\Tilde{\Sigma}$ satisfied the condition of the lemma before removing $\{w,u\}$; however, such an annotated cell complex would be discarded by our algorithm as $\{w,u\}$ appears three times. The lemma is true for any other segment $(x,y,z)$ of the boundary of $A_1$ (say) because $x$ and $z$ were connected by a path $P\subset\lk_{A_1}{y}\subset\lk_{A}{y}$.
We now verify this is true after replacing a real edge with an interior dummy edges. If the segment of the boundary with the interior dummy edges is $(w_1,w,w_1)$, then previously $w$ was on a segment of the boundary $(u,w,u)$ where $(w,u)$ is a real edge. So by assumption, there was a path $P_1$ in $\lk_{A}{w}$ with both endpoints equal to $u$.
We now verify this is true for boundary dummy edges. We will prove this by induction on the length of the segment of $B$ in $\Sigma$. If $\{w_1,w\}$ replaces the real edge $\{w_1,w\}$, then this is true by condition 1 of this lemma. We now show this is true after merging two edges into a boundary dummy edge. Let $(w_1,w,u)$ and $(w,u,w_2)$ be segments of a face $A$. We replace the boundary dummy edges $\{w,u\}$ and $\{u,w_2\}$ with a merge boundary dummy edge $\{w,w_2\}$. This replacement does not change the triangles that compose $A$ so $\lk_{A}{w}$ is the same before and after the replacement. If $\{w,u\}$ replaced a segment $(w,u_1,\ldots,u)$ of $B$, then $\{w,w_2\}$ replaces some segment of the boundary $(w,u_1,\ldots,u,\ldots,w_2)$ and the lemma holds.

We are now ready to prove the main lemmas of this section.

We begin with the case that $v\notin B$. In the first subcase, we claim no edges enter $v$ in $\Tilde\Sigma$ if and only if $\lk_{\Sigma}{v}$ is empty. If no edges enter $v$ in $\Tilde\Sigma$, then by Lemma <ref>, $v\notin\Sigma$ and $\lk_{\Sigma}{v}$ is empty. Conversely, if $\lk_{\Sigma}{v}=\emptyset$, then obviously no edges in $\Tilde{\Sigma}$ enter $v$.
Now assume the edges entering $v$ form a cyclic sequence of successors $(\overbar{a_1\ldots a_k})$ with $a_{i}=\{v,w_{i}\}$. A pair of consecutive edges $a_{i}$ and $a_{i+1}$ in the sequence of successors corresponds to a segment $(w_{i},v,w_{i+1})$ on the boundary of a face $A_{i}$ in $\Tilde\Sigma$. If $k=2$ and $a_1$ and $a_2$ are interior dummy edges, then the lemma is immediately true by Lemma <ref>. So assume instead that the edges $a_{i}$ and $a_{i+1}$ are real edges. By <ref>, the vertices $w_{i}$ and $w_{i+1}$ are connected by a path $P_i$ in $\lk_{A_i}{v}$. Moreover, each pair of paths $P_i$ and $P_j$ are disjoint for $1\leq i< j\leq k$, except possibly at their endpoints. The path $P_i$ shares one endpoint each with $P_{i-1}$ and $P_{i+1}$, so the concatenation of the paths forms a simple cycle. This simple cycle is exactly $\lk_{\Sigma}{v}$, so the lemma is true.
Now assume that $\lk_{\Sigma}{v}$ is a simple cycle. By Proposition <ref>, the edges entering $v$ in $\Sigma$ form a cyclic sequence of successors. The annotated cell complex $\Tilde{\Sigma}$ is obtained from $\Sigma$ by removing edges $e\notin K[X_t]$. We will show that each of these moves preserves the property of the lemma. Let $(a_1\ldots a_k)$ be the cyclic sequence of successors entering $v$. Removing an edge not incident to $v$ does not change $(\overbar{a_1\ldots a_k})$. If we do remove an edge $a_i$, by Lemma <ref> the edges entering $v$ form a cyclic sequence of successors $(\overbar{a_1\ldots a_{i-1}a_{i+1}\ldots a_k})$. If there is a single edge $a$ entering $v$, then forgetting $a$ results in the creation of an interior dummy edge $d$. As discussed above, an interior dummy edge forms a cyclic sequence of successors $(\overbar{d})$.
The proof is nearly identical if $v\in B$, except we use Lemma <ref> to show that $P_1$ and $P_k$ share a single endpoint with other paths and the other endpoints of these paths are $v$'s neighbors in $\beta.$ Likewise, the edges entering $v$ form a sequence of successors $(a_1\ldots a_k)$ in $\Sigma$, and forgetting an edge $a_i$ maintains this property. Forgetting the edges $a_1$ or $a_k$ creates a dummy edge $d$ entering $v$ that had the same successors as $a_1$ or $a_k$.
Finally, these conditions can be checked by building the sequence of successors of all those edges that enter $v$. We can define a graph where the vertices are the edges in $\Tilde\Sigma$ that enter $v$ and the edges of the graph connect two edges in $\Tilde\Sigma$ that are successors. For case 1i) of the lemma, we can check if the graph is empty. For case 1ii), we can check that the graph is a cycle. For case 2), we can check if the graph is a path. The graph can be built by iterating once over the $\OO(k)$ edges in $\Tilde\Sigma$, and the conditions can be checked in $\poly(k)$ time.

The proof of this lemma is almost identical to the proof of Lemma <ref>.

In the case that $v$ is about to be forgotten (i.e. $\Sigma$ is a candidate solution at $t'$, the child of the node $t$ that forget $v$), then we can say something stronger about the edges entering $v$. In particular, any real edge incident to $v$ must have already been forgotten, so there will only be dummy edges in $\Tilde\Sigma$ entering $v$.

We make two observations. First, as $\Sigma$ is a candidate solution at $t$, then we know that $\lk_{\Sigma}{v}$ is complete. Lemma <ref> gives a necessary and sufficient condition for how the edges in $\Tilde\Sigma$ that enter $v$ must behave, depending on whether or not $v\in B$. Second, there are no edges $e$ incident to $v$ in $X_{t'}$; otherwise, $X_t$ would not be a simplicial complex, as it would contain $e$ but not contain the face $v$ of $e$. This contradicts the assumption that the tree decomposition is closed. Therefore, the only edges incident to $v$ in $\Tilde\Sigma$ will be dummy edges.
The vertex $v$ can either be incident to no edges, two interior dummy edges, or two boundary dummy edges; this is because interior dummy edges form a cyclic sequence of successors, so $v$ cannot be incident to any other edges if it is incident to interior dummy edges.