TY - JOUR AB - Distant luminous Lyman-α emitters (LAEs) are excellent targets for spectroscopic observations of galaxies in the epoch of reionisation (EoR). We present deep high-resolution (R = 5000) VLT/X-shooter observations, along with an extensive collection of photometric data of COLA1, a proposed double peaked LAE at z = 6.6. We rule out the possibility that COLA1’s emission line is an [OII] doublet at z = 1.475 on the basis of i) the asymmetric red line-profile and flux ratio of the peaks (blue/red=0.31 ± 0.03) and ii) an unphysical [OII]/Hα ratio ([OII]/Hα >  22). We show that COLA1’s observed B-band flux is explained by a faint extended foreground LAE, for which we detect Lyα and [OIII] at z = 2.142. We thus conclude that COLA1 is a real double-peaked LAE at z = 6.593, the first discovered at z >  6. COLA1 is UV luminous (M1500 = −21.6 ± 0.3), has a high equivalent width (EW0,Lyα = 120−40+50 Å) and very compact Lyα emission (r50,Lyα = 0.33−0.04+0.07 kpc). Relatively weak inferred Hβ+[OIII] line-emission from Spitzer/IRAC indicates an extremely low metallicity of Z <  1/20 Z⊙ or reduced strength of nebular lines due to high escape of ionising photons. The small Lyα peak separation of 220 ± 20 km s−1 implies a low HI column density and an ionising photon escape fraction of ≈15 − 30%, providing the first direct evidence that such galaxies contribute actively to the reionisation of the Universe at z >  6. Based on simple estimates, we find that COLA1 could have provided just enough photons to reionise its own ≈0.3 pMpc (2.3 cMpc) bubble, allowing the blue Lyα line to be observed. However, we also discuss alternative scenarios explaining the detected double peaked nature of COLA1. Our results show that future high-resolution observations of statistical samples of double peaked LAEs at z >  5 are a promising probe of the occurrence of ionised regions around galaxies in the EoR. AU - Matthee, Jorryt J AU - Sobral, David AU - Gronke, Max AU - Paulino-Afonso, Ana AU - Stefanon, Mauro AU - Röttgering, Huub ID - 11508 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: high-redshift / galaxies: formation / dark ages / reionization / first stars / techniques: spectroscopic / intergalactic medium SN - 0004-6361 TI - Confirmation of double peaked Lyα emission at z = 6.593: Witnessing a galaxy directly contributing to the reionisation of the universe VL - 619 ER - TY - JOUR AB - We investigate the clustering properties of ∼7000 H β + [O III] and [O II] narrowband-selected emitters at z ∼ 0.8–4.7 from the High-z Emission Line Survey. We find clustering lengths, r0, of 1.5–4.0 h−1 Mpc and minimum dark matter halo masses of 1010.7–12.1 M⊙ for our z = 0.8–3.2 H β + [O III] emitters and r0 ∼ 2.0–8.3 h−1 Mpc and halo masses of 1011.5–12.6 M⊙ for our z = 1.5–4.7 [O II] emitters. We find r0 to strongly increase both with increasing line luminosity and redshift. By taking into account the evolution of the characteristic line luminosity, L⋆(z), and using our model predictions of halo mass given r0, we find a strong, redshift-independent increasing trend between L/L⋆(z) and minimum halo mass. The faintest H β + [O III] emitters are found to reside in 109.5 M⊙ haloes and the brightest emitters in 1013.0 M⊙ haloes. For [O II] emitters, the faintest emitters are found in 1010.5 M⊙ haloes and the brightest emitters in 1012.6 M⊙ haloes. A redshift-independent stellar mass dependency is also observed where the halo mass increases from 1011 to 1012.5 M⊙ for stellar masses of 108.5 to 1011.5 M⊙, respectively. We investigate the interdependencies of these trends by repeating our analysis in a Lline−Mstar grid space for our most populated samples (H β + [O III] z = 0.84 and [O II] z = 1.47) and find that the line luminosity dependency is stronger than the stellar mass dependency on halo mass. For L > L⋆ emitters at all epochs, we find a relatively flat trend with halo masses of 1012.5–13 M⊙, which may be due to quenching mechanisms in massive haloes that is consistent with a transitional halo mass predicted by models. AU - Khostovan, A A AU - Sobral, D AU - Mobasher, B AU - Best, P N AU - Smail, I AU - Matthee, Jorryt J AU - Darvish, B AU - Nayyeri, H AU - Hemmati, S AU - Stott, J P ID - 11549 IS - 3 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: evolution KW - galaxies: haloes KW - galaxies: high-redshift KW - galaxies: star formation KW - cosmology: observations KW - large-scale structure of Universe SN - 0035-8711 TI - The clustering of H β + [O III] and [O II] emitters since z ∼ 5: Dependencies with line luminosity and stellar mass VL - 478 ER - TY - JOUR AB - Deep narrow-band surveys have revealed a large population of faint Ly α emitters (LAEs) in the distant Universe, but relatively little is known about the most luminous sources (⁠LLyα≳1042.7 erg s−1; LLyα≳L∗Lyα⁠). Here we present the spectroscopic follow-up of 21 luminous LAEs at z ∼ 2–3 found with panoramic narrow-band surveys over five independent extragalactic fields (≈4 × 106 Mpc3 surveyed at z ∼ 2.2 and z ∼ 3.1). We use WHT/ISIS, Keck/DEIMOS, and VLT/X-SHOOTER to study these sources using high ionization UV lines. Luminous LAEs at z ∼ 2–3 have blue UV slopes (⁠β=−2.0+0.3−0.1⁠) and high Ly α escape fractions (⁠50+20−15 per cent) and span five orders of magnitude in UV luminosity (MUV ≈ −19 to −24). Many (70 per cent) show at least one high ionization rest-frame UV line such as C IV, N V, C III], He II or O III], typically blue-shifted by ≈100–200 km s−1 relative to Ly α. Their Ly α profiles reveal a wide variety of shapes, including significant blue-shifted components and widths from 200 to 4000 km s−1. Overall, 60 ± 11  per cent appear to be active galactic nucleus (AGN) dominated, and at LLyα > 1043.3 erg s−1 and/or MUV < −21.5 virtually all LAEs are AGNs with high ionization parameters (log U = 0.6 ± 0.5) and with metallicities of ≈0.5 − 1 Z⊙. Those lacking signatures of AGNs (40 ± 11  per cent) have lower ionization parameters (⁠logU=−3.0+1.6−0.9 and log ξion = 25.4 ± 0.2) and are apparently metal-poor sources likely powered by young, dust-poor ‘maximal’ starbursts. Our results show that luminous LAEs at z ∼ 2–3 are a diverse population and that 2×L∗Lyα and 2×M∗UV mark a sharp transition in the nature of LAEs, from star formation dominated to AGN dominated. AU - Sobral, David AU - Matthee, Jorryt J AU - Darvish, Behnam AU - Smail, Ian AU - Best, Philip N AU - Alegre, Lara AU - Röttgering, Huub AU - Mobasher, Bahram AU - Paulino-Afonso, Ana AU - Stroe, Andra AU - Oteo, Iván ID - 11557 IS - 2 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: active KW - galaxies: evolution KW - galaxies: high-redshift KW - galaxies: ISM KW - galaxies: starburst KW - cosmology: observations SN - 0035-8711 TI - The nature of luminous Ly α emitters at z ∼ 2–3: Maximal dust-poor starbursts and highly ionizing AGN VL - 477 ER - TY - JOUR AB - We present and explore deep narrow- and medium-band data obtained with the Subaru and the Isaac Newton Telescopes in the ∼2 deg2 COSMOS field. We use these data as an extremely wide, low-resolution (R ∼ 20–80) Integral Field Unit survey to slice through the COSMOS field and obtain a large sample of ∼4000 Ly α emitters (LAEs) from z ∼ 2 to 6 in 16 redshift slices (SC4K). We present new Ly α luminosity functions (LFs) covering a comoving volume of ∼108 Mpc3. SC4K extensively complements ultradeep surveys, jointly covering over 4 dex in Ly α luminosity and revealing a global (2.5 < z < 6) synergy LF with α=−1.93+0.12−0.12⁠, log10Φ∗Lyα=−3.45+0.22−0.29 Mpc−3, and log10L∗Lyα=42.93+0.15−0.11 erg s−1. The Schechter component of the Ly α LF reveals a factor ∼5 rise in L∗Lyα and a ∼7 × decline in Φ∗Lyα from z ∼ 2 to 6. The data reveal an extra power-law (or Schechter) component above LLy α ≈ 1043.3 erg s−1 at z ∼ 2.2–3.5 and we show that it is partially driven by X-ray and radio active galactic nucleus (AGN), as their Ly α LF resembles the excess. The power-law component vanishes and/or is below our detection limits above z > 3.5, likely linked with the evolution of the AGN population. The Ly α luminosity density rises by a factor ∼2 from z ∼ 2 to 3 but is then found to be roughly constant (⁠1.1+0.2−0.2×1040 erg s−1 Mpc−3) to z ∼ 6, despite the ∼0.7 dex drop in ultraviolet (UV) luminosity density. The Ly α/UV luminosity density ratio rises from 4 ± 1 per cent to 30 ± 6 per cent from z ∼ 2.2 to 6. Our results imply a rise of a factor of ≈2 in the global ionization efficiency (ξion) and a factor ≈4 ± 1 in the Ly α escape fraction from z ∼ 2 to 6, hinting for evolution in both the typical burstiness/stellar populations and even more so in the typical interstellar medium conditions allowing Ly α photons to escape. AU - Sobral, David AU - Santos, Sérgio AU - Matthee, Jorryt J AU - Paulino-Afonso, Ana AU - Ribeiro, Bruno AU - Calhau, João AU - Khostovan, Ali A ID - 11558 IS - 4 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: evolution KW - galaxies: formation KW - galaxies: high-redshift KW - galaxies: luminosity function KW - mass function KW - galaxies: statistics SN - 0035-8711 TI - Slicing COSMOS with SC4K: The evolution of typical Ly α emitters and the Ly α escape fraction from z ∼ 2 to 6 VL - 476 ER - TY - JOUR AB - We investigate the morphology of the [C II] emission in a sample of ‘normal’ star-forming galaxies at 5 < z < 7.2 in relation to their UV (rest-frame) counterpart. We use new Atacama Large Millimetre/submillimetre Array (ALMA) observations of galaxies at z ∼ 6–7, as well as a careful re-analysis of archival ALMA data. In total 29 galaxies were analysed, 21 of which are detected in [C II]. For several of the latter the [C II] emission breaks into multiple components. Only a fraction of these [C II] components, if any, is associated with the primary UV systems, while the bulk of the [C II] emission is associated either with fainter UV components, or not associated with any UV counterpart at the current limits. By taking into account the presence of all these components, we find that the L[CII]–SFR (star formation rate) relation at early epochs is fully consistent with the local relation, but it has a dispersion of 0.48 ± 0.07 dex, which is about two times larger than observed locally. We also find that the deviation from the local L[CII]–SFR relation has a weak anticorrelation with the EW(Ly α). The morphological analysis also reveals that [C II] emission is generally much more extended than the UV emission. As a consequence, these primordial galaxies are characterized by a [C II] surface brightness generally much lower than expected from the local Σ[CII]−ΣSFR relation. These properties are likely a consequence of a combination of different effects, namely gas metallicity, [C II] emission from obscured star-forming regions, strong variations of the ionization parameter, and circumgalactic gas in accretion or ejected by these primeval galaxies. AU - Carniani, S AU - Maiolino, R AU - Amorin, R AU - Pentericci, L AU - Pallottini, A AU - Ferrara, A AU - Willott, C J AU - Smit, R AU - Matthee, Jorryt J AU - Sobral, D AU - Santini, P AU - Castellano, M AU - De Barros, S AU - Fontana, A AU - Grazian, A AU - Guaita, L ID - 11555 IS - 1 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: evolution KW - galaxies: high-redshift KW - galaxies: ISM KW - galaxies: formation SN - 0035-8711 TI - Kiloparsec-scale gaseous clumps and star formation at z = 5–7 VL - 478 ER - TY - JOUR AB - Observations show that star-forming galaxies reside on a tight 3D plane between mass, gas-phase metallicity, and star formation rate (SFR), which can be explained by the interplay between metal-poor gas inflows, SFR and outflows. However, different metals are released on different time-scales, which may affect the slope of this relation. Here, we use central, star-forming galaxies with Mstar = 109.0–10.5 M⊙ from the EAGLE hydrodynamical simulation to examine 3D relations between mass, SFR, and chemical enrichment using absolute and relative C, N, O, and Fe abundances. We show that the scatter is smaller when gas-phase α-enhancement is used rather than metallicity. A similar plane also exists for stellar α-enhancement, implying that present-day specific SFRs are correlated with long time-scale star formation histories. Between z = 0 and 1, the α-enhancement plane is even more insensitive to redshift than the plane using metallicity. However, it evolves at z > 1 due to lagging iron yields. At fixed mass, galaxies with higher SFRs have star formation histories shifted towards late times, are more α-enhanced, and this α-enhancement increases with redshift as observed. These findings suggest that relations between physical properties inferred from observations may be affected by systematic variations in α-enhancements. AU - Matthee, Jorryt J AU - Schaye, Joop ID - 11584 IS - 1 JF - Monthly Notices of the Royal Astronomical Society: Letters KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: abundances KW - galaxies: evolution KW - galaxies: formation KW - galaxies: star formation SN - 1745-3925 TI - Star-forming galaxies are predicted to lie on a fundamental plane of mass, star formation rate, and α-enhancement VL - 479 ER - TY - JOUR AB - We report on the confirmation and mass determination of π Men c, the first transiting planet discovered by NASA’s TESS space mission. π Men is a naked-eye (V = 5.65 mag), quiet G0 V star that was previously known to host a sub-stellar companion (π Men b) on a longperiod (Porb = 2091 days), eccentric (e = 0.64) orbit. Using TESS time-series photometry, combined with Gaia data, published UCLES at AAT Doppler measurements, and archival HARPS at ESO-3.6m radial velocities, we found that π Men c is a close-in planet with an orbital period of Porb = 6.27 days, a mass of Mc = 4.52 ± 0.81 M⊕, and a radius of Rc = 2.06 ± 0.03 R⊕. Based on the planet’s orbital period and size, π Men c is a super-Earth located at, or close to, the radius gap, while its mass and bulk density suggest it may have held on to a significant atmosphere. Because of the brightness of the host star, this system is highly suitable for a wide range of further studies to characterize the planetary atmosphere and dynamical properties. We also performed an asteroseismic analysis of the TESS data and detected a hint of power excess consistent with the seismic values expected for this star, although this result depends on the photometric aperture used to extract the light curve. This marginal detection is expected from pre-launch simulations hinting at the asteroseismic potential of the TESS mission for longer, multi-sector observations and/or for more evolved bright stars. AU - Gandolfi, D. AU - Barragán, O. AU - Livingston, J. H. AU - Fridlund, M. AU - Justesen, A. B. AU - Redfield, S. AU - Fossati, L. AU - Mathur, S. AU - Grziwa, S. AU - Cabrera, J. AU - García, R. A. AU - Persson, C. M. AU - Van Eylen, V. AU - Hatzes, A. P. AU - Hidalgo, D. AU - Albrecht, S. AU - Bugnet, Lisa Annabelle AU - Cochran, W. D. AU - Csizmadia, Sz. AU - Deeg, H. AU - Eigmüller, Ph. AU - Endl, M. AU - Erikson, A. AU - Esposito, M. AU - Guenther, E. AU - Korth, J. AU - Luque, R. AU - Montañes Rodríguez, P. AU - Nespral, D. AU - Nowak, G. AU - Pätzold, M. AU - Prieto-Arranz, J. ID - 11619 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - planetary systems / planets and satellites KW - detection / planets and satellites KW - fundamental parameters / planets and satellites KW - terrestrial planets / stars KW - fundamental parameters SN - 0004-6361 TI - TESS’s first planet: A super-Earth transiting the naked-eye star π Mensae VL - 619 ER - TY - JOUR AB - Asteroseismology provides global stellar parameters such as masses, radii, or surface gravities using mean global seismic parameters and effective temperature for thousands of low-mass stars (0.8 M⊙ < M < 3 M⊙). This methodology has been successfully applied to stars in which acoustic modes excited by turbulent convection are measured. Other methods such as the Flicker technique can also be used to determine stellar surface gravities, but only works for log g above 2.5 dex. In this work, we present a new metric called FliPer (Flicker in spectral power density, in opposition to the standard Flicker measurement which is computed in the time domain); it is able to extend the range for which reliable surface gravities can be obtained (0.1 < log g < 4.6 dex) without performing any seismic analysis for stars brighter than Kp < 14. FliPer takes into account the average variability of a star measured in the power density spectrum in a given range of frequencies. However, FliPer values calculated on several ranges of frequency are required to better characterize a star. Using a large set of asteroseismic targets it is possible to calibrate the behavior of surface gravity with FliPer through machine learning. This calibration made with a random forest regressor covers a wide range of surface gravities from main-sequence stars to subgiants and red giants, with very small uncertainties from 0.04 to 0.1 dex. FliPer values can be inserted in automatic global seismic pipelines to either give an estimation of the stellar surface gravity or to assess the quality of the seismic results by detecting any outliers in the obtained νmax values. FliPer also constrains the surface gravities of main-sequence dwarfs using only long-cadence data for which the Nyquist frequency is too low to measure the acoustic-mode properties. AU - Bugnet, Lisa Annabelle AU - García, R. A. AU - Davies, G. R. AU - Mathur, S. AU - Corsaro, E. AU - Hall, O. J. AU - Rendle, B. M. ID - 11618 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - asteroseismology / methods KW - data analysis / stars KW - oscillations SN - 0004-6361 TI - FliPer: A global measure of power density to estimate surface gravities of main-sequence solar-like stars and red giants VL - 620 ER - TY - JOUR AB - We report the discovery and characterization of HD 89345b (K2-234b; EPIC 248777106b), a Saturn-sized planet orbiting a slightly evolved star. HD 89345 is a bright star (V = 9.3 mag) observed by the K2 mission with 1 min time sampling. It exhibits solar-like oscillations. We conducted asteroseismology to determine the parameters of the star, finding the mass and radius to be 1.12+0.04−0.01M⊙ and 1.657+0.020−0.004R⊙⁠, respectively. The star appears to have recently left the main sequence, based on the inferred age, 9.4+0.4−1.3Gyr⁠, and the non-detection of mixed modes. The star hosts a ‘warm Saturn’ (P = 11.8 d, Rp = 6.86 ± 0.14 R⊕). Radial-velocity follow-up observations performed with the FIbre-fed Echelle Spectrograph, HARPS, and HARPS-N spectrographs show that the planet has a mass of 35.7 ± 3.3 M⊕. The data also show that the planet’s orbit is eccentric (e ≈ 0.2). An investigation of the rotational splitting of the oscillation frequencies of the star yields no conclusive evidence on the stellar inclination angle. We further obtained Rossiter–McLaughlin observations, which result in a broad posterior of the stellar obliquity. The planet seems to confirm to the same patterns that have been observed for other sub-Saturns regarding planet mass and multiplicity, orbital eccentricity, and stellar metallicity. AU - Van Eylen, V AU - Dai, F AU - Mathur, S AU - Gandolfi, D AU - Albrecht, S AU - Fridlund, M AU - García, R A AU - Guenther, E AU - Hjorth, M AU - Justesen, A B AU - Livingston, J AU - Lund, M N AU - Pérez Hernández, F AU - Prieto-Arranz, J AU - Regulo, C AU - Bugnet, Lisa Annabelle AU - Everett, M E AU - Hirano, T AU - Nespral, D AU - Nowak, G AU - Palle, E AU - Silva Aguirre, V AU - Trifonov, T AU - Winn, J N AU - Barragán, O AU - Beck, P G AU - Chaplin, W J AU - Cochran, W D AU - Csizmadia, S AU - Deeg, H AU - Endl, M AU - Heeren, P AU - Grziwa, S AU - Hatzes, A P AU - Hidalgo, D AU - Korth, J AU - Mathis, S AU - Montañes Rodriguez, P AU - Narita, N AU - Patzold, M AU - Persson, C M AU - Rodler, F AU - Smith, A M S ID - 11620 IS - 4 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - asteroseismology KW - planets and satellites: composition KW - planets and satellites: formation KW - planets and satellites: fundamental parameters SN - 0035-8711 TI - HD 89345: A bright oscillating star hosting a transiting warm Saturn-sized planet observed by K2 VL - 478 ER - TY - GEN AB - The recently launched NASA Transiting Exoplanet Survey Satellite (TESS) mission is going to collect lightcurves for a few hundred million of stars and we expect to increase the number of pulsating stars to analyze compared to the few thousand stars observed by the CoRoT, Kepler and K2 missions. However, most of the TESS targets have not yet been properly classified and characterized. In order to improve the analysis of the TESS data, it is crucial to determine the type of stellar pulsations in a timely manner. We propose an automatic method to classify stars attending to their pulsation properties, in particular, to identify solar-like pulsators among all TESS targets. It relies on the use of the global amount of power contained in the power spectrum (already known as the FliPer method) as a key parameter, along with the effective temperature, to feed into a machine learning classifier. Our study, based on TESS simulated datasets, shows that we are able to classify pulsators with a 98% accuracy. AU - Bugnet, Lisa Annabelle AU - García, R. A. AU - Davies, G. R. AU - Mathur, S. AU - Hall, O. J. AU - Rendle, B. M. ID - 11631 KW - asteroseismology - methods KW - data analysis - stars KW - oscillations T2 - arXiv TI - FliPer: Classifying TESS pulsating stars ER - TY - JOUR AB - The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi’s contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm runs a factor 7.5× faster on average when using 32 threads. To further speed up computations, we also give a version of our algorithm that performs random edge contractions as preprocessing. This version achieves a lower running time and better parallel scalability at the expense of a higher error rate. AU - Henzinger, Monika H AU - Noe, Alexander AU - Schulz, Christian AU - Strash, Darren ID - 11657 JF - ACM Journal of Experimental Algorithmics KW - Theoretical Computer Science SN - 1084-6654 TI - Practical minimum cut algorithms VL - 23 ER - TY - JOUR AB - The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions, the truthful direct-revelation mechanism that maximizes social welfare is the Vickrey-Clarke-Groves mechanism. For many valuation spaces, computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that increased expressiveness can give rise to additional equilibria of poorer efficiency. AU - Dütting, Paul AU - Henzinger, Monika H AU - Starnberger, Martin ID - 11667 IS - 2 JF - ACM Transactions on Economics and Computation KW - Theory of computation KW - Algorithmic game theory and mechanism design KW - Applied computing KW - Economics KW - Simplified mechanisms KW - Combinatorial auctions with item bidding KW - Price of anarchy SN - 2167-8375 TI - Valuation compressions in VCG-based combinatorial auctions VL - 6 ER - TY - JOUR AB - We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with O(log3 n log log2 n) amortized time per edge insertion and O(1) query time. This result partially answers an open question posed by Thorup (2007). It also stays in sharp contrast to a polynomial conditional lower bound for the fully dynamic weighted minimum cut problem. Our algorithm is obtained by combining a sparsification technique of Kawarabayashi and Thorup (2015) or its recent improvement by Henzinger, Rao, and Wang (2017), and an exact incremental algorithm of Henzinger (1997). We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O(nlog n/ε2) space Monte Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a (1+ε)-approximation to the minimum cut. The algorithm has O((α (n) log3 n)/ε 2) amortized update time and constant query time, where α (n) stands for the inverse of Ackermann function. AU - Goranci, Gramoz AU - Henzinger, Monika H AU - Thorup, Mikkel ID - 11664 IS - 2 JF - ACM Transactions on Algorithms SN - 1549-6325 TI - Incremental exact min-cut in polylogarithmic amortized update time VL - 14 ER - TY - JOUR AB - We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O ( f 2)-approximately optimal solution in O ( f · log(m + n)) amortized update time, where f is the maximum “frequency” of an element, n is the number of sets, and m is the maximum number of elements in the universe at any point in time. (2) For the dynamic b-matching problem, we maintain an O (1)-approximately optimal solution in O (log3 n) amortized update time, where n is the number of nodes in the graph. AU - Bhattacharya, Sayan AU - Henzinger, Monika H AU - Italiano, Giuseppe ID - 11757 IS - 08 JF - Information and Computation SN - 0890-5401 TI - Dynamic algorithms via the primal-dual method VL - 261 ER - TY - CONF AB - We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an n^{c}-separator theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)-approximations of the all-pairs effective resistances of an n-vertex graph G undergoing edge insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and O~(sqrt{n}/epsilon^2) worst-case query time, if G is guaranteed to be sqrt{n}-separable (i.e., it is taken from a class satisfying a sqrt{n}-separator theorem) and its separator can be computed in O~(n) time. Our algorithm is built upon a dynamic algorithm for maintaining approximate Schur complement that approximately preserves pairwise effective resistances among a set of terminals for separable graphs, which might be of independent interest. We complement our result by proving that for any two fixed vertices s and t, no incremental or decremental algorithm can maintain the s-t effective resistance for sqrt{n}-separable graphs with worst-case update time O(n^{1/2-delta}) and query time O(n^{1-delta}) for any delta>0, unless the Online Matrix Vector Multiplication (OMv) conjecture is false. We further show that for general graphs, no incremental or decremental algorithm can maintain the s-t effective resistance problem with worst-case update time O(n^{1-delta}) and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false. AU - Goranci, Gramoz AU - Henzinger, Monika H AU - Peng, Pan ID - 11828 SN - 1868-8969 T2 - 26th Annual European Symposium on Algorithms TI - Dynamic effective resistances and approximate schur complement on separable graphs VL - 112 ER - TY - CONF AB - We study the metric facility location problem with client insertions and deletions. This setting differs from the classic dynamic facility location problem, where the set of clients remains the same, but the metric space can change over time. We show a deterministic algorithm that maintains a constant factor approximation to the optimal solution in worst-case time O~(2^{O(kappa^2)}) per client insertion or deletion in metric spaces while answering queries about the cost in O(1) time, where kappa denotes the doubling dimension of the metric. For metric spaces with bounded doubling dimension, the update time is polylogarithmic in the parameters of the problem. AU - Goranci, Gramoz AU - Henzinger, Monika H AU - Leniowski, Dariusz ID - 11827 SN - 1868-8969 T2 - 26th Annual European Symposium on Algorithms TI - A tree structure for dynamic facility location VL - 112 ER - TY - JOUR AB - In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary. In contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11768 IS - 6 JF - Journal of the ACM SN - 0004-5411 TI - Decremental single-source shortest paths on undirected graphs in near-linear total update time VL - 65 ER - TY - CONF AB - We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex coloring with O(log Δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o(1)Δ-vertex coloring with O(polylog Δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2Δ – 1)-edge coloring with O(log Δ) worst-case update time. This improves the recent O(Δ)-edge coloring algorithm with worst-case update time [4]. AU - Bhattacharya, Sayan AU - Chakrabarty, Deeparnab AU - Henzinger, Monika H AU - Nanongkai, Danupon ID - 11872 T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms TI - Dynamic algorithms for graph coloring ER - TY - CONF AB - The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability. AU - Henzinger, Monika H AU - Noe, Alexander AU - Schulz, Christian AU - Strash, Darren ID - 11882 T2 - 20th Workshop on Algorithm Engineering and Experiments TI - Practical minimum cut algorithms ER - TY - JOUR AB - We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph 𝐺=(𝑉,𝐸), with |𝑉|=𝑛 and |𝐸|=𝑚, in 𝑜(𝑚‾‾√) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+𝜖) approximation in 𝑂(log𝑛/𝜖2) amortized time per update. For maximum matching, we show how to maintain a (3+𝜖) approximation in 𝑂(min(𝑛√/𝜖,𝑚1/3/𝜖2) amortized time per update and a (4+𝜖) approximation in 𝑂(𝑚1/3/𝜖2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457--464]. AU - Bhattacharya, Sayan AU - Henzinger, Monika H AU - Italiano, Giuseppe F. ID - 11890 IS - 3 JF - SIAM Journal on Computing SN - 0097-5397 TI - Deterministic fully dynamic data structures for vertex cover and matching VL - 47 ER -