# Numerical relativity higher order gravitational waveforms of eccentric,
spinning, non-precessing binary black hole mergers

Abhishek V. Joshi<EMAIL_ADDRESS>NCSA, University of Illinois at
Urbana-Champaign, Urbana, Illinois 61801, USA  Department of Physics,
University of Illinois at Urbana-Champaign, Urbana, Illinois 61801, USA  Shawn
G. Rosofsky  NCSA, University of Illinois at Urbana-Champaign, Urbana,
Illinois 61801, USA  Department of Physics, University of Illinois at Urbana-
Champaign, Urbana, Illinois 61801, USA  Roland Haas  NCSA, University of
Illinois at Urbana-Champaign, Urbana, Illinois 61801, USA  Department of
Physics, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801,
USA  E. A. Huerta  Department of Physics, University of Illinois at Urbana-
Champaign, Urbana, Illinois 61801, USA  Data Science and Learning Division,
Argonne National Laboratory, Lemont, Illinois 60439, USA  Department of
Computer Science, University of Chicago, Chicago, Illinois 60637, USA

###### Abstract

We use the open source, community-driven, numerical relativity software, the
Einstein Toolkit to study the physics of eccentric, spinning, non-precessing
binary black hole mergers with mass-ratios $q=\\{2,4,6\\}$, individual
dimensionless spin parameters $s_{1}^{z}=\pm 0.6$, $s_{2}^{z}=\pm 0.3$, that
include higher order gravitational wave modes $\ell\leq 4$, except for memory
modes. Assuming stellar mass binary black hole mergers that may be detectable
by the advanced LIGO detectors, we find that including modes up to $\ell=4$
increases the signal-to-noise of compact binaries between $3.5\%$ to $35\%$,
compared to signals that only include the $\ell=|m|=2$ mode. We used the
SEOBNRE waveform model, which incorporates spin and eccentricity corrections
to the waveform dynamics, to quantify the impact of including higher order
wave modes to constrain the individual spins and eccentricity of black hole
mergers through fitting factor calculations. Our findings indicate that the
inclusion of higher order wave modes has a measurable effect in the recovery
of moderately and highly eccentric black hole mergers, and thus it is
essential to develop waveform models and signal processing tools that
accurately describe the physics of these astrophysical sources.

Suggested keywords

##  I Introduction

The modeling and detection of eccentric compact binary mergers has attracted
significant attention in recent years [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41]. A plethora of studies for the massive
stellar black hole merger named GW190521 [42] provide persuasive evidence for
the existence of eccentric compact binary mergers in dense stellar
environments [43, 44, 41]. In view of these developments, and the upcoming
deluge of gravitational wave observations to be enabled by advanced LIGO [45,
46] and its international counterparts [47, 19, 48], it is timely and relevant
to continue developing adequate tools for the identification of gravitational
wave signals that may be produced by eccentric compact binary mergers.

The best tool at hand to gain insights about the physics of eccentric binary
black hole mergers is numerical relativity, and thus we use the open source,
community-driven, numerical relativity software, the Einstein Toolkit [49] to
produce a suite of numerical relativity waveforms that describe eccentric,
spinning, non-precessing binary black hole mergers. These waveforms include
higher order modes up to $\ell\leq 4$, except for memory modes. We use these
numerical relativity waveforms to carry out the following studies:

  * •

Gravitational wave detection We construct two types of waveforms that include
either quadrupole modes, $\ell=|m|=2$, or modes up to $\ell\leq 4$. We assume
stellar mass binary black holes that may be observed by advanced LIGO-type
detectors and compute signal-to-noise ratio (SNR) calculations for a variety
of astrophysical scenarios, and explore whether the inclusion of higher order
wave modes leads to measurable SNR increases.

  * •

Gravitational wave modeling We used the SEOBNRE waveform model to estimate the
eccentricity of our numerical relativity waveforms [12]. This exercise was
useful to identify areas of improvement for next generation waveform models,
and to get a better understanding of signals that may be missed by state-of-
the art semi-analytical models used for gravitational wave searches.

  * •

Parameter space degeneracy We quantified the impact of including higher order
modes in terms of fitting factor calculations that aim to pinpoint an optimal
quasi-circular NRHybSur3dq8 waveform signal whose astrophysical parameters
best reproduce the complex morphology of moderately or highly eccentric
numerical relativity waveforms.

These three complementary studies underscore the importance of improving our
understanding of compact binary mergers in dense stellar environments. It is
not enough to hope for the best and expect that burst or machine learning
searches identify complex signals in gravitational wave data [50, 51]. It is
also necessary to develop a comprehensive toolkit that encompasses numerical
relativity waveforms, semi-analytical or machine learning based models, and
signal processing tools to detect and then infer the astrophysical properties
of eccentric compact binary mergers. Not doing so would be a disservice to the
proven detection capabilities of advanced gravitational wave detectors, and
would limit the science reach of gravitational wave astrophysics. To
contribute to this important endeavor, we release our catalog of numerical
relativity waveforms along with this article.

This article is organized as follows. We describe our approach to create a
catalog of eccentric numerical relativity waveforms in Section II. Section III
presents our waveform catalog, and a systematic study on the importance of
including higher order wave modes in terms of SNR calculations. In Section IV
we study whether surrogate models based on quasi-circular, spinning, non-
precessing binary black hole numerical relativity waveforms can capture the
physics of spinning, non-precessing eccentric mergers. We summarize our
findings and future directions of work in Section V.

##  II Numerical Setup and Simulation Details

We used the Einstein Toolkit to generate a catalog of numerical relativity
waveforms. Initial data for the binaries was computed using the TwoPunctures
code. The evolution was done with the CTGamma code implementing the 3+1 BSSN
formulation. The outer boundary of the simulation domain was placed far enough
(2500M) to avoid any contamination of the signal until 200M after the merger.
Each simulation was run at three resolutions to check for convergence (see
appendix A): $N=36,40,44$ where $N$ is the resolution across the finest grid
radius. The highest resolution simulations were used for all analyses. Further
details of the simulation setup are given in [7]. Waveforms extracted at
future null infinity were computed for $1<l\leq 4$ and $1\leq|m|\leq l$ modes
using POWER [52] by extrapolating the observed signals from 7 detectors
located 100–700M. A plot of all the $h_{+}$ simulation waveforms is shown in
Figure 1.

Figure 1: Numerical relativity waveform catalog Each column is associated with
a given mass-ratio $q=\\{2,4,6\\}$. From top to bottom, simulations are
ordered in $(\chi_{1z},\chi_{2z})$, and then in increasing eccentricity. Each
panel presents two types of waveforms: a $\ell=|m|=2$ signal (orange), and one
that includes higher order modes (blue). We have selected the inclination of
the binary that maximizes the contribution higher order modes.

Table 1 describes the properties of our simulation suite, including the mass-
ratio, individual spins and orbital eccentricity of each binary. The library
consists of 27 simulations across 3 mass ratios, $q=\\{2,4,6\\}$, and a
combination of non-precessing individual spins, namely $\pm 0.6$ and $\pm
0.3$, for the primary (heavier) and secondary (lighter) binary components,
respectively.

Since the orbital eccentricity of the binary systems we have considered to
create our numerical relativity waveform catalog is ill defined, as the
simulations are started very close to merger, we have used the method
described in [53] to estimate the eccentricity of our numerical relativity
waveform catalog. The key idea consists of using $\ell=|m|=2$ waveforms to
compute the fitting factor between a given numerical relativity waveform, and
an array of SEOBNRE templates, which describe spin-aligned eccentric binaries
[12]. To estimate the eccentricity of our numerical relativity waveforms, we
need to compute a few objects. The first of them is the inner product between
one of our numerical relativity waveforms, $h_{22}^{\text{NR}}$, and a SEOBNRE
template, $h_{22}^{\text{SEOBNRE}}$, given by:

$\langle
h_{22}^{\text{NR}}|h_{22}^{\text{SEOBNRE}}\rangle=\max_{t_{0},\phi_{0}}\mathcal{R}\left[\int_{t_{1}}^{t_{2}}h_{22}^{\text{NR}}h_{22}^{\text{*
SEOBNRE}}\right]\,.$ (1)

Note that the inner product is calculated by maximising over both the time and
phase of the two waveforms. $t_{1}$ represents an initial time at a point free
from initial junk radiation, and $t_{2}$ marks the end of the numerical
relativity simulation. The norm of either a numerical relativity template or a
SEOBNRE template is given by:

$||h||\equiv\sqrt{\langle h|h\rangle}\,.$ (2)

With these two quantities, we can compute the fitting factor between one of
our numerical relativity waveforms and a bank of SEOBNRE templates

$e_{0}=\operatorname*{arg\,max}_{e_{0}}\left(\mathrm{FF}\equiv\frac{\langle
h_{22}^{\text{NR}}|h_{22}^{\text{SEOBNRE}}\rangle}{||h_{22}^{\text{NR}}||\cdot||h_{22}^{\text{SEOBNRE}}||}\right)\,,$
(3)

where the eccentricity $e_{0}$ is defined at the lower frequency bound
$f_{\text{min}}$ which determines the length of the simulation prior to merger
for the template. This calculation basically corresponds to the inner product
of a numerical relativity waveform maximized over a bank of SEOBNRE templates.

To produce this bank of SEOBNRE templates, we set
$f_{\text{min}}=10\mathrm{Hz}$. To obtain stable SEOBNRE waveforms, we set the
total mass of the binary system $M=60M_{\odot}$ for $e\leq 0.5$ and
$M=30M_{\odot}$ for $e>0.5$. Higher mass binaries spend less cycles in the
detectable frequency band, and so for highly eccentric simulations, the code
does not have enough inspiral points to produce an accurate waveform,
requiring a smaller mass for stability.

As seen in Table 1, we find good fitting factors for roughly half of the
simulations. For some highly eccentric simulations, a suitable match was not
found. This is because some numerical relativity waveforms contain moderately
spinning binaries with highly eccentric orbits that are beyond the realm of
applicability of the SEOBNRE model. It is possible to quantify the reliability
of SEOBNRE signals with the “spin hang-up parameter”, $\chi_{\mathrm{up}}$
[53]

$\chi_{\mathrm{up}}=\frac{8\chi_{\mathrm{eff}}+3\sqrt{1-4\eta}\chi_{A}}{11}\,,$
(4)

where $\chi_{\mathrm{eff}}=(q\chi_{1z}+\chi_{2z})/(1+q)$,
$\chi_{A}=(q\chi_{1z}-\chi_{2z})/(1+q)$ and $\eta=m_{1}m_{2}/M^{2}$ for a
binary of masses $(m_{1},m_{2})$ and (orbit aligned) dimensionless spins
$(\chi_{1z},\chi_{2z})$ respectively. Furthermore, $M=m_{1}+m_{2}$ and
$q=m_{1}/m_{2}\geq 1$.

For simulations with poor matches, we find that $\chi_{\mathrm{up}}>0.35$, and
visual inspection of these waveforms suggest high eccentricity, $e_{0}>0.6$.
The SEOBNRE template waveform is inaccurate in producing reliable waveforms in
that region of parameter space [53]. Indeed, for the two simulations with
$\chi_{up}=-0.5$, we were unable to obtain a suitable waveform. Nevertheless,
in the valid regions, eccentricities are found to good accuracy. For
simulations with $\text{FF}<75\%$ the eccentricity is considered
unconstrained, and we simply report the best match for completeness.

Simulation | q | $\chi_{1z}$ | $\chi_{2z}$ |  $e_{0}$(FF) | $\chi_{\mathrm{up}}$
---|---|---|---|---|---
U1007 | 2 | 0.6 | 0.3 | 0.39 (94.8%) | 0.39
U1008 | 2 | -0.6 | -0.3 | 0.67 (94.0%) | -0.39
U0009 | 2 | 0.6 | 0.3 | 0.7 (29.3%) | 0.39
U0010 | 2 | -0.6 | -0.3 | 0.79 (99.3%) | -0.39
U0011 | 2 | 0.6 | 0.3 | 0.08 (45.7%) | 0.39
U0027 | 2 | 0.6 | -0.3 | 0.7 (90.3%) | 0.26
U0028 | 2 | -0.3 | -0.3 | 0.66 (96.7%) | -0.23
U0030 | 2 | -0.3 | -0.3 | 0.77 (84.0%) | -0.23
|  |  |  |  |
U0014 | 4 | -0.6 | -0.3 | 0.26 (99.8%) | -0.46
U1013 | 4 | 0.6 | 0.3 | 0.33 (61.2%) | 0.46
U1014 | 4 | -0.6 | -0.3 | 0.68 (95.0%) | -0.46
U0015 | 4 | 0.6 | 0.3 | 0.05 (28.7%) | 0.46
U0017 | 4 | 0.6 | 0.3 | 0.45 (30.2%) | 0.46
U0032 | 4 | -0.3 | -0.3 | 0.4 (87.2%) | -0.25
U0033 | 4 | 0.6 | -0.3 | 0.69 (18.6%) | 0.39
U0034 | 4 | -0.3 | -0.3 | 0.41 (93.1%) | -0.25
U0035 | 4 | 0.6 | -0.3 | 0.49 (25.7%) | 0.39
U0036 | 4 | -0.3 | -0.3 | 0.7 (79.7%) | -0.25
|  |  |  |  |
U0020 | 6 | -0.6 | -0.3 | N/A | -0.5
U1019 | 6 | 0.6 | 0.3 | 0.58 (12.7%) | 0.5
U1020 | 6 | -0.6 | -0.3 | N/A | -0.5
U0021 | 6 | 0.6 | 0.3 | 0.2 (15.6%) | 0.5
U0023 | 6 | 0.6 | 0.3 | 0.6 (13.1%) | 0.5
U0038 | 6 | -0.3 | -0.3 | 0.7 (94.1%) | -0.26
U0039 | 6 | 0.6 | -0.3 | 0.26 (29.8%) | 0.45
U0040 | 6 | -0.3 | -0.3 | 0.41 (96.2%) | -0.26
U0041 | 6 | 0.6 | -0.3 | 0.47 (13.6%) | 0.45
Table 1: Physical parameters of numerical relativity waveform catalog Mass-
ratio, $q$, individual spins, $(\chi_{1z},\chi_{2z})$, and estimated orbital
eccentricity, $e_{0}$, of our numerical relativity waveforms.

##  III Importance of higher order harmonics

Having computed higher order wave modes, $h^{lm}(t)$, we can construct the
full waveform

$h(t,\theta,\phi)=h_{+}+ih_{x}=\sum_{l\geq 2}\sum_{m\geq-l}^{m\leq
l}h^{lm}{}_{-2}Y_{lm}(\theta,\phi)\,,$ (5)

where ${}_{-2}Y_{lm}(\theta,\phi)$ are the spin-weight–2 spherical harmonics
computed at a particular inclination ($\theta$) and azimuth ($\phi$).
$\theta=0$ corresponds to observing the binary face-on i.e., with the orbital
angular momentum vector pointed towards the observer.

Since nearly eccentric waveforms resemble quasi-circular signals near merger
due to circularization, we compute the importance of including higher order
harmonics on the signal across the entire waveform evolution to better
quantify the effect of eccentricity. From the results of [50] section III, the
$\Delta\mathcal{B}$ metric is used. It involves integrating over the entire
numerical relativity waveform (after removing junk radiation)

$\mathcal{B}^{(l,|m|)}(\theta,\phi)=\int_{t=t_{0}}^{T}\sqrt{h(t,\theta,\phi)\tilde{h}(t,\theta,\phi)}\mathrm{d}t\,,$
(6)

$\Delta\mathcal{B}(\theta,\phi)=\frac{\mathcal{B}^{(\ell,|m|)}(\theta,\phi)-\mathcal{B}^{(\ell=|m|=2)}(\theta,\phi)}{\mathcal{B}^{(\ell=|m|=2)}(\hat{\theta},\hat{\phi})}\,,$
(7)

where $(\hat{\theta},\hat{\phi})$ represent the orientation that maximizes the
$(\ell=|m|=2)$ mode of $\mathcal{B}$. To find the $(\theta,\phi)$ combination
that maximizes the contribution of higher order modes in terms of SNR
calculations, we scan across $(\theta,\phi)$ space at a resolution of $0.01$
radians and select the orientation ($\theta^{*},\phi^{*}$) that maximizes
$\Delta\mathcal{B}$ in Equation 7. The resultant optimal orientation is
usually within 3 categories: one with the inclination close to the pole, one
with inclination close to the equator and one slightly apart from both these
angles.

To see the observational impact we focus on the optimal SNR response of a
waveform [$\mathbf{h}$] as [50]

$\mathrm{SNR}[\mathbf{h}]^{2}=4\mathcal{R}\int_{0}^{\infty}\frac{\tilde{h}(f)\tilde{h}^{*}(f)}{S_{n}(f)}\mathrm{d}f\,,$
(8)

where $S_{n}(f)$ is the one-sided power spectral density (PSD) for LIGO’s Zero
Detuned High Power configuration (ZDHP) [54]. We thus compute SNRs for both
$(\ell,|m|)$ and $(\ell=|m|=2)$ modes across all sky locations
$(\alpha,\beta)$ with the optimized orientation $(\theta^{*},\phi^{*})$. For
the following results we set the polarization angle to $\psi=\pi/4$, and
compute the effect of the higher order modes as

$\Delta\mathrm{SNR}=\frac{\mathrm{SNR}^{(\ell,|m|)}-\mathrm{SNR}^{(\ell=|m|=2)}}{\mathrm{\hat{SNR}}^{(\ell=|m|=2)}}\,,$
(9)

where $\mathrm{\hat{SNR}}^{(\ell=|m|=2)}$ is the maximum value of the
$\ell=|m|=2$ mode across the sky $(\hat{\alpha},\hat{\beta})$. The total mass
of the binary is set to $80M_{\odot}$.

The results can be categorized into three different categories depending on
what the optimal orientation of the binary is $(\theta^{*},\phi^{*})$. The
first category is that in which $\theta^{*}\rightarrow 0$, and the inclusion
of higher order modes has a marginal impact on the SNR of the signal,
typically no more than 4%, as shown in the top panel of Figure 2. The second
category is for $70^{\circ}<\theta^{*}<110^{\circ}$, in which case the
contribution of higher order modes to the SNR of the signal is rather
significant, with $\Delta\textrm{SNR}\sim 25\%$ as shown in the bottom panel
of Figure 2. The final category are the in-between values of $\theta^{*}$ for
which $\Delta\mathrm{SNR}$ will be intermediate to that of the first two
categories.

Figure 2: Importance of higher order modes for SNR calculations The panels
show the increase in SNR, $\Delta\textrm{SNR}$ in Equation (9), as a result of
including higher order modes in the modeling of eccentric, spinning, binary
black hole mergers. We assume an advanced LIGO-type detector, and binaries
with total mass $M=80M_{\odot}$ for numerical relativity waveform U0014 (top
panel) and U0023 (bottom panel).

These studies underscore the importance of including higher order modes in the
modeling and detection of eccentric compact binary mergers, since SNR
increases of order $\Delta\textrm{SNR}\sim 20\%$ mean that marginally
detectable signals [55] may then become easier to detect, or observable to
larger distances.

##  IV Comparisons with quasi-circular waveforms

Studies in the literature have shown that the morphology of non-spinning,
mildly eccentric binary black hole mergers may be captured by quasi-circular,
spinning, non-precessing binary black hole mergers [15]. Here we quantify
whether this parameter space degeneracy between orbital eccentricity and spin
corrections still remain when we directly compare our new set of eccentric,
spinning, non-precessing numerical relativity waveforms with the NRHybSur2dq8
surrogate model [56] that describes quasi-circular, spinning, non-precessing
mergers.

We carry out this study by computing fitting factor calculations, see Equation
3, between a given waveform in our numerical relativity catalog and an array
of NRHybSur2dq8 waveforms that scan the $(q,\chi_{1z},\chi_{2z})$ parameter
space using a simple grid search. We use an interval of size $\Delta q=2$
centered around the truth mass-ratio. So for numerical relativity waveforms of
mass-ratio $q=4$, we scan an interval that covers the range $2\leq q\leq 6$
(note for $q=2$ the interval is $1\leq q\leq 4$). For individual spins, we
consider the range $-0.7\leq\chi_{\\{1z,2z\\}}\leq 0.7$. The resolution of the
search is $\delta q=0.1$, and $\delta\chi=0.02$ for both spins. Following
these conventions, we consider two cases. In the first both numerical
relativity waveforms and NRHybSur2dq8 waveforms include only the $\ell=|m|=2$
mode, whereas in the second case both types of waveforms include higher order
modes. Results of this analysis for simulations U0014 and U0023 are presented
in Figure 3.

Figure 3: Non parameter space degeneracy between spin and eccentricity
corrections Fitting factor (FF) calculations between numerical relativity
waveform U0014 (top panels) and U0023 (bottom panels) and NRHybSur2dq8
waveform templates. In both cases, we show results for signals that include
only $\ell=|m|=2$ modes (left panels) and higher order modes (right panels).
We notice significant discrepancies between ground-truth and recovered values
for the mass-ratio and individual spins of the binary components through FF
calculations.

Additional results for other numerical simulations in our waveform catalog may
be found in Table 2. These findings, along with the results we presented in
Table 1 using the SEOBNRE waveform family, exhibit the importance of
developing waveform models that are informed by numerical relativity
simulations to accurately capture orbital eccentricity and spin corrections.
At this time, these results show that moderately or highly eccentric and
spinning signals may not be captured by template matching algorithms, unless
the signal is loud enough to be captured by unmodeled (burst) searches.

In summary, this study shows that it is not possible for quasi-circular,
spinning, non-precessing signals to capture the dynamics of moderately and
highly eccentric, spinning, non-precessing signals. We either develop the
required methods (waveforms & signal processing tools) to search for and find
these signals or we may miss an interesting population of compact binary
sources.

##  V Conclusions

We have presented a set of 27 eccentric, spin-aligned binary black hole
simulations that describe three different mass-ratios $q=\\{2,4,6\\}$. To
measure the eccentricity of the simulations, we computed fitting factors
against the spin-aligned eccentric effective-one-body model with eccentricity
(SEOBNRE). We were able to estimate eccentricities for roughly half of the
simulations, with eccentricities ranging from $e_{0}=0.26$ to $e=0.79$. The
remaining simulations appear to be of even higher eccentricity, though
producing such waveforms from templates proved to be difficult for the values
of spins used in our simulations. Current limitations to the existing SEOBNRE
library may be alleviated by including higher order eccentricity terms, which
become increasingly important at higher mass ratios as indicated by our
findings and those reported in [53]. For these simulations, we performed the
following analyses:

  1. 1.

Selecting the orientation of the binary that maximizes the contribution of
higher order modes, we computed the SNR observed for ground-based LIGO-type
detectors across the sky. In doing so, we observed that for simulations, the
inclusion of high order modes in the waveform increases the SNR between 5–35%.

  2. 2.

We do not find significant parameter space degeneracies between spinning,
eccentric waveforms and quasi-circular, spinning waveforms upon computing
fitting factor calculations assuming a coarse grid search across mass ratio,
and spins. In general the fitting factors are worse when comparing higher
order modes.

These analyses underscore the importance of using numerical relativity to
understand the physics of these compact binary systems, and then inform the
design of neural network models [50, 51, 57, 58], matched filtering approaches
[59, 60], or unmodeled searches [61, 62] to discover moderately and highly
eccentric spinning binaries in future discovery campaigns.

We also found that including higher order terms will enhance the detactability
as the results suggest that the $(\ell=|m|=2)$ modes do not faithfully capture
the dynamics of the system for asymmetric mass-ratio systems.

This set of simulations extends the library of open-source simulations
introduced in [7], stored in the DataVault repository maintained by NCSA at
the University of Illinois [63]. We intend to make this set of simulations
publicly available on the same repository soon and until then, any data can be
availed upon request to the authors of this paper.

###### Acknowledgements.

This material is based upon work supported by the National Science Foundation
under Grants No. NSF-2004879, NSF-1550514, ACI-1238993. Numerical simulations
used compute resources provided by XSEDE under allocation TG-PHY160053. EAH
gratefully acknowledges support from NSF award OAC-1931561. This material is
based upon work supported by Laboratory Directed Research and Development
(LDRD) funding from Argonne National Laboratory, provided by the Director,
Office of Science, of the U.S. Department of Energy under Contract No. DE-
AC02-06CH11357. Plots were produced using matplotlib [64, 65]. Part of the
analysis was parallelized using TACC’s launcher utility [66].

## References

  * Romero-Shaw  _et al._ [2022] I. M. Romero-Shaw, P. D. Lasky, and E. Thrane, Four eccentric mergers increase the evidence that LIGO–Virgo–KAGRA’s binary black holes form dynamically, arXiv e-prints , arXiv:2206.14695 (2022), arXiv:2206.14695 [astro-ph.HE] .
  * Moore  _et al._ [2018] B. Moore, T. Robson, N. Loutrel, and N. Yunes, A Fourier Domain Waveform for Non-Spinning Binaries with Arbitrary Eccentricity, ArXiv e-prints (2018), arXiv:1807.07163 [gr-qc] .
  * Rodriguez  _et al._ [2018] C. L. Rodriguez, P. Amaro-Seoane, S. Chatterjee, K. Kremer, F. A. Rasio, J. Samsing, C. S. Ye, and M. Zevin, Post-Newtonian dynamics in dense star clusters: Formation, masses, and merger rates of highly-eccentric black hole binaries, Phys. Rev. D 98, 123005 (2018), arXiv:1811.04926 [astro-ph.HE] .
  * Zevin  _et al._ [2018] M. Zevin, J. Samsing, C. Rodriguez, C.-J. Haster, and E. Ramirez-Ruiz, Eccentric Black Hole Mergers in Dense Star Clusters: The Role of Binary-Binary Encounters, arXiv e-prints , arXiv:1810.00901 (2018), arXiv:1810.00901 [astro-ph.HE] .
  * Samsing [2018] J. Samsing, Eccentric black hole mergers forming in globular clusters, Phys. Rev. D 97, 103014 (2018), arXiv:1711.07452 [astro-ph.HE] .
  * Ramos-Buades  _et al._ [2020] A. Ramos-Buades, S. Husa, G. Pratten, H. Estellés, C. García-Quirós, M. Mateu-Lucena, M. Colleoni, and R. Jaume, First survey of spinning eccentric black hole mergers: Numerical relativity simulations, hybrid waveforms, and parameter estimation, Phys. Rev. D 101, 083015 (2020), arXiv:1909.11011 [gr-qc] .
  * Huerta  _et al._ [2019] E. A. Huerta, R. Haas, S. Habib, A. Gupta, A. Rebei, V. Chavva, D. Johnson, S. Rosofsky, E. Wessel, B. Agarwal, D. Luo, and W. Ren, Physics of eccentric binary black hole mergers: A numerical relativity perspective, Phys. Rev. D 100, 064003 (2019), arXiv:1901.07038 [gr-qc] .
  * Hinder  _et al._ [2018] I. Hinder, L. E. Kidder, and H. P. Pfeiffer, Eccentric binary black hole inspiral-merger-ringdown gravitational waveform model from numerical relativity and post-Newtonian theory, Phys. Rev. D 98, 044015 (2018), arXiv:1709.02007 [gr-qc] .
  * Hoang  _et al._ [2018] B.-M. Hoang, S. Naoz, B. Kocsis, F. A. Rasio, and F. Dosopoulou, Black Hole Mergers in Galactic Nuclei Induced by the Eccentric Kozai-Lidov Effect, Astrophys. J.  856, 140 (2018), arXiv:1706.09896 [astro-ph.HE] .
  * Gondán and Kocsis [2018] L. Gondán and B. Kocsis, Measurement Accuracy of Inspiraling Eccentric Neutron Star and Black Hole Binaries Using Gravitational Waves, arXiv e-prints , arXiv:1809.00672 (2018), arXiv:1809.00672 [astro-ph.HE] .
  * Gondán  _et al._ [2018] L. Gondán, B. Kocsis, P. Raffai, and Z. Frei, Accuracy of Estimating Highly Eccentric Binary Black Hole Parameters with Gravitational-wave Detections, Astrophys. J.  855, 34 (2018), arXiv:1705.10781 [astro-ph.HE] .
  * Cao and Han [2017] Z. Cao and W.-B. Han, Waveform model for an eccentric binary black hole based on the effective-one-body-numerical-relativity formalism, Phys. Rev. D 96, 044028 (2017), arXiv:1708.00166 [gr-qc] .
  * Samsing [2018] J. Samsing, Eccentric black hole mergers forming in globular clusters, Phys. Rev. D 97, 103014 (2018).
  * Hinderer and Babak [2017] T. Hinderer and S. Babak, Foundations of an effective-one-body model for coalescing binaries on eccentric orbits, Phys. Rev. D 96, 104048 (2017), arXiv:1707.08426 [gr-qc] .
  * Huerta  _et al._ [2018] E. A. Huerta, C. J. Moore, P. Kumar, D. George, A. J. K. Chua, R. Haas, E. Wessel, D. Johnson, D. Glennon, A. Rebei, A. M. Holgado, J. R. Gair, and H. P. Pfeiffer, Eccentric, nonspinning, inspiral, Gaussian-process merger approximant for the detection and characterization of eccentric binary black hole mergers, Phys. Rev. D 97, 024031 (2018), arXiv:1711.06276 [gr-qc] .
  * Romero-Shaw  _et al._ [2019] I. M. Romero-Shaw, P. D. Lasky, and E. Thrane, Searching for Eccentricity: Signatures of Dynamical Formation in the First Gravitational-Wave Transient Catalogue of LIGO and Virgo, Mon. Not. Roy. Astron. Soc. 490, 5210 (2019), arXiv:1909.05466 [astro-ph.HE] .
  * Lower  _et al._ [2018] M. E. Lower, E. Thrane, P. D. Lasky, and R. Smith, Measuring eccentricity in binary black hole inspirals with gravitational waves, Phys. Rev. D 98, 083028 (2018).
  * Nitz  _et al._ [2019] A. H. Nitz, A. Lenon, and D. A. Brown, Search for Eccentric Binary Neutron Star Mergers in the first and second observing runs of Advanced LIGO, Astrophys. J. 890, 1 (2019), arXiv:1912.05464 [astro-ph.HE] .
  * Abbott  _et al._ [2019] B. Abbott _et al._ (LIGO Scientific, Virgo), Search for Eccentric Binary Black Hole Mergers with Advanced LIGO and Advanced Virgo during their First and Second Observing Runs, Astrophys. J. 883, 149 (2019), arXiv:1907.09384 [astro-ph.HE] .
  * Chen  _et al._ [2021] Z. Chen, E. A. Huerta, J. Adamo, R. Haas, E. O’Shea, P. Kumar, and C. Moore, Observation of eccentric binary black hole mergers with second and third generation gravitational wave detector networks, Phys. Rev. D 103, 084018 (2021), arXiv:2008.03313 [gr-qc] .
  * Huerta  _et al._ [2017] E. A. Huerta, P. Kumar, B. Agarwal, D. George, H.-Y. Schive, H. P. Pfeiffer, R. Haas, W. Ren, T. Chu, M. Boyle, D. A. Hemberger, L. E. Kidder, M. A. Scheel, and B. Szilagyi, Complete waveform model for compact binaries on eccentric orbits, Phys. Rev. D 95, 024038 (2017), arXiv:1609.05933 [gr-qc] .
  * Osburn  _et al._ [2016] T. Osburn, N. Warburton, and C. R. Evans, Highly eccentric inspirals into a black hole, Phys. Rev. D 93, 064024 (2016), arXiv:1511.01498 [gr-qc] .
  * Loutrel and Yunes [2017a] N. Loutrel and N. Yunes, Hereditary effects in eccentric compact binary inspirals to third post-Newtonian order, Classical and Quantum Gravity 34, 044003 (2017a), arXiv:1607.05409 [gr-qc] .
  * Loutrel and Yunes [2017b] N. Loutrel and N. Yunes, Eccentric gravitational wave bursts in the post-Newtonian formalism, Classical and Quantum Gravity 34, 135011 (2017b), arXiv:1702.01818 [gr-qc] .
  * Hinder  _et al._ [2008] I. Hinder, B. Vaishnav, F. Herrmann, D. M. Shoemaker, and P. Laguna, Circularization and final spin in eccentric binary-black-hole inspirals, Phys. Rev. D 77, 081502 (2008), arXiv:0710.5167 [gr-qc] .
  * Bini  _et al._ [2016] D. Bini, T. Damour, and A. Geralico, High post-Newtonian order gravitational self-force analytical results for eccentric equatorial orbits around a Kerr black hole, Phys. Rev. D 93, 124058 (2016), arXiv:1602.08282 [gr-qc] .
  * Kavanagh  _et al._ [2017] C. Kavanagh, D. Bini, T. Damour, S. Hopper, A. C. Ottewill, and B. Wardell, Spin-orbit precession along eccentric orbits for extreme mass ratio black hole binaries and its effective-one-body transcription, Phys. Rev. D 96, 064012 (2017), arXiv:1706.00459 [gr-qc] .
  * Levin  _et al._ [2011] J. Levin, S. T. McWilliams, and H. Contreras, Inspiral of generic black hole binaries: spin, precession and eccentricity, Classical and Quantum Gravity 28, 175001 (2011), arXiv:1009.2533 [gr-qc] .
  * Huerta  _et al._ [2014] E. A. Huerta, P. Kumar, S. T. McWilliams, R. O’Shaughnessy, and N. Yunes, Accurate and efficient waveforms for compact binaries on eccentric orbits, Phys. Rev. D 90, 084016 (2014), arXiv:1408.3406 [gr-qc] .
  * Habib and Huerta [2019] S. Habib and E. A. Huerta, Characterization of numerical relativity waveforms of eccentric binary black hole mergers, Phys. Rev. D 100, 044016 (2019), arXiv:1904.09295 [gr-qc] .
  * Huerta and Brown [2013] E. A. Huerta and D. A. Brown, Effect of eccentricity on binary neutron star searches in advanced LIGO, Phys. Rev. D 87, 127501 (2013), arXiv:1301.1895 [gr-qc] .
  * Yunes  _et al._ [2009] N. Yunes, K. G. Arun, E. Berti, and C. M. Will, Post-circular expansion of eccentric binary inspirals: Fourier-domain waveforms in the stationary phase approximation, Phys. Rev. D 80, 084001 (2009), arXiv:0906.0313 [gr-qc] .
  * Tiwari  _et al._ [2016] V. Tiwari, S. Klimenko, N. Christensen, E. A. Huerta, S. R. P. Mohapatra, A. Gopakumar, M. Haney, P. Ajith, S. T. McWilliams, G. Vedovato, M. Drago, F. Salemi, G. A. Prodi, C. Lazzaro, S. Tiwari, G. Mitselmakher, and F. Da Silva, Proposed search for the detection of gravitational waves from eccentric binary black holes, Phys. Rev. D 93, 043007 (2016), arXiv:1511.09240 [gr-qc] .
  * Habib  _et al._ [2021] S. Habib, A. Ramos-Buades, E. A. Huerta, S. Husa, R. Haas, and Z. Etienne, Initial Data and Eccentricity Reduction Toolkit for Binary Black Hole Numerical Relativity Waveforms, Class. Quant. Grav. 38, 125007 (2021), arXiv:2011.08878 [gr-qc] .
  * Coughlin  _et al._ [2015] M. Coughlin, P. Meyers, E. Thrane, J. Luo, and N. Christensen, Detectability of eccentric compact binary coalescences with advanced gravitational-wave detectors, Phys. Rev. D 91, 063004 (2015), arXiv:1412.4665 [gr-qc] .
  * Moore  _et al._ [2016] B. Moore, M. Favata, K. G. Arun, and C. Kant Mishra, Gravitational-wave phasing for low-eccentricity inspiralling compact binaries to 3PN order, ArXiv e-prints (2016), arXiv:1605.00304 [gr-qc] .
  * Tai  _et al._ [2014] K. S. Tai, S. T. McWilliams, and F. Pretorius, Detecting gravitational waves from highly eccentric compact binaries, Phys. Rev. D 90, 103001 (2014), arXiv:1403.7754 [gr-qc] .
  * Will [2012] C. M. Will, Capture of non-relativistic particles in eccentric orbits by a Kerr black hole, Classical and Quantum Gravity 29, 217001 (2012), arXiv:1208.3931 [astro-ph.GA] .
  * Tanay  _et al._ [2016] S. Tanay, M. Haney, and A. Gopakumar, Frequency and time-domain inspiral templates for comparable mass compact binaries in eccentric orbits, Phys. Rev. D 93, 064031 (2016), arXiv:1602.03081 [gr-qc] .
  * Samsing and Ramirez-Ruiz [2017] J. Samsing and E. Ramirez-Ruiz, On the Assembly Rate of Highly Eccentric Binary Black Hole Mergers, Astrophys. J. Lett.  840, L14 (2017), arXiv:1703.09703 [astro-ph.HE] .
  * Gayathri  _et al._ [2022] V. Gayathri, J. Healy, J. Lange, B. O’Brien, M. Szczepanczyk, I. Bartos, M. Campanelli, S. Klimenko, C. O. Lousto, and R. O’Shaughnessy, Eccentricity estimate for black hole mergers with numerical relativity simulations, Nature Astron. 6, 344 (2022), arXiv:2009.05461 [astro-ph.HE] .
  * Abbott  _et al._ [2020] R. Abbott _et al._ (LIGO Scientific, Virgo), GW190521: A Binary Black Hole Merger with a Total Mass of $150~{}M_{\odot}$, Phys. Rev. Lett. 125, 101102 (2020), arXiv:2009.01075 [gr-qc] .
  * Romero-Shaw  _et al._ [2020] I. Romero-Shaw, P. D. Lasky, E. Thrane, and J. Calderón Bustillo, GW190521: Orbital Eccentricity and Signatures of Dynamical Formation in a Binary Black Hole Merger Signal, Astrophys. J. Lett.  903, L5 (2020), arXiv:2009.04771 [astro-ph.HE] .
  * Samsing  _et al._ [2022] J. Samsing, I. Bartos, D. J. D’Orazio, Z. Haiman, B. Kocsis, N. W. C. Leigh, B. F. Liu, M. E. Pessah, and H. Tagawa, Agn as potential factories for eccentric black hole mergers., Nature 603 7900, 237 (2022).
  * The LIGO Scientific Collaboration  _et al._ [2015] The LIGO Scientific Collaboration, J. Aasi, _et al._ , Advanced LIGO, Classical and Quantum Gravity 32, 074001 (2015), arXiv:1411.4547 [gr-qc] .
  * Abbott  _et al._ [2016] B. P. Abbott _et al._ (LIGO Scientific, Virgo), Binary Black Hole Mergers in the first Advanced LIGO Observing Run, Phys. Rev. X 6, 041015 (2016), [Erratum: Phys.Rev.X 8, 039903 (2018)], arXiv:1606.04856 [gr-qc] .
  * Acernese  _et al._ [2015] F. Acernese _et al._ , for the Virgo Collaboration. Advanced Virgo: a second-generation interferometric gravitational wave detector, Classical and Quantum Gravity 32, 024001 (2015).
  * Akutsu  _et al._ [2020] T. Akutsu, M. Ando, K. Arai, _et al._ , Overview of KAGRA: Detector design and construction history, Progress of Theoretical and Experimental Physics 2021, 10.1093/ptep/ptaa125 (2020), 05A101, https://academic.oup.com/ptep/article-pdf/2021/5/05A101/37974994/ptaa125.pdf .
  * Löffler  _et al._ [2012] F. Löffler, J. Faber, E. Bentivegna, T. Bode, P. Diener, R. Haas, I. Hinder, B. C. Mundim, C. D. Ott, E. Schnetter, G. Allen, M. Campanelli, and P. Laguna, The Einstein Toolkit: a community computational infrastructure for relativistic astrophysics, Classical and Quantum Gravity 29, 115001 (2012), arXiv:1111.3344 [gr-qc] .
  * Rebei  _et al._ [2019] A. Rebei, E. A. Huerta, S. Wang, S. Habib, R. Haas, D. Johnson, and D. George, Fusing numerical relativity and deep learning to detect higher-order multipole waveforms from eccentric binary black hole mergers, Phys. Rev. D 100, 044025 (2019), arXiv:1807.09787 [gr-qc] .
  * Wei  _et al._ [2021] W. Wei, E. A. Huerta, M. Yun, N. Loutrel, M. A. Shaikh, P. Kumar, R. Haas, and V. Kindratenko, Deep Learning with Quantized Neural Networks for Gravitational-wave Forecasting of Eccentric Compact Binary Coalescence, Astrophys. J.  919, 82 (2021), arXiv:2012.03963 [gr-qc] .
  * Johnson  _et al._ [2018] D. Johnson, E. A. Huerta, and R. Haas, Python Open source Waveform ExtractoR (POWER): an open source, Python package to monitor and post-process numerical relativity simulations, Classical and Quantum Gravity 35, 027002 (2018), arXiv:1708.02941 [gr-qc] .
  * Liu  _et al._ [2020] X. Liu, Z. Cao, and L. Shao, Validating the effective-one-body numerical-relativity waveform models for spin-aligned binary black holes along eccentric orbits, Phys. Rev. D 101, 044049 (2020), arXiv:1910.00784 [gr-qc] .
  * Barsotti  _et al._ [2018] L. Barsotti, S. Gras, M. Evans, and P. Fritschel, Advanced LIGO anticipated sensitivity curves (2018), https://dcc.ligo.org/LIGO-T1800044/public.
  * Brown  _et al._ [2013] D. A. Brown, P. Kumar, and A. H. Nitz, Template banks to search for low-mass binary black holes in advanced gravitational-wave detectors, Physical Review D 87, 10.1103/physrevd.87.082004 (2013).
  * Varma  _et al._ [2019] V. Varma, S. E. Field, M. A. Scheel, J. Blackman, L. E. Kidder, and H. P. Pfeiffer, Surrogate model of hybridized numerical relativity binary black hole waveforms, Phys. Rev. D 99, 064045 (2019).
  * Wei and Huerta [2021] W. Wei and E. A. Huerta, Deep learning for gravitational wave forecasting of neutron star mergers, Phys. Lett. B 816, 136185 (2021), arXiv:2010.09751 [gr-qc] .
  * Schäfer  _et al._ [2022] M. B. Schäfer, O. Zelenka, A. H. Nitz, H. Wang, S. Wu, Z.-K. Guo, Z. Cao, Z. Ren, P. Nousi, N. Stergioulas, P. Iosif, A. E. Koloniari, A. Tefas, N. Passalis, F. Salemi, G. Vedovato, S. Klimenko, T. Mishra, B. Brügmann, E. Cuoco, E. A. Huerta, C. Messenger, and F. Ohme, MLGWSC-1: The first Machine Learning Gravitational-Wave Search Mock Data Challenge, arXiv e-prints , arXiv:2209.11146 (2022), arXiv:2209.11146 [astro-ph.IM] .
  * Usman  _et al._ [2016] S. A. Usman _et al._ , The PyCBC search for gravitational waves from compact binary coalescence, Classical and Quantum Gravity 33, 215004 (2016), arXiv:1508.02357 [gr-qc] .
  * Sachdev  _et al._ [2019] S. Sachdev, S. Caudill, H. Fong, R. K. L. Lo, C. Messick, D. Mukherjee, R. Magee, L. Tsukada, K. Blackburn, P. Brady, P. Brockill, K. Cannon, S. J. Chamberlin, D. Chatterjee, J. D. E. Creighton, P. Godwin, A. Gupta, C. Hanna, S. Kapadia, R. N. Lang, T. G. F. Li, D. Meacher, A. Pace, S. Privitera, L. Sadeghian, L. Wade, M. Wade, A. Weinstein, and S. Liting Xiao, The GstLAL Search Analysis Methods for Compact Binary Mergers in Advanced LIGO’s Second and Advanced Virgo’s First Observing Runs, arXiv e-prints , arXiv:1901.08580 (2019), arXiv:1901.08580 [gr-qc] .
  * Klimenko  _et al._ [2008] S. Klimenko, I. Yakushin, A. Mercer, and G. Mitselmakher, A coherent method for detection of gravitational wave bursts, Classical and Quantum Gravity 25, 114029 (2008), arXiv:0802.3232 [gr-qc] .
  * Klimenko  _et al._ [2016] S. Klimenko, G. Vedovato, M. Drago, F. Salemi, V. Tiwari, G. A. Prodi, C. Lazzaro, K. Ackley, S. Tiwari, C. F. Da Silva, and G. Mitselmakher, Method for detection and reconstruction of gravitational wave transients with networks of advanced detectors, Phys. Rev. D 93, 042004 (2016), arXiv:1511.05999 [gr-qc] .
  * Luo  _et al._ [2021] Y. Luo, R. Haas, Q. Zhang, and G. Allen, DataVault: a data storage infrastructure for the Einstein Toolkit, Classical and Quantum Gravity 38, 135016 (2021), arXiv:2012.06635 [gr-qc] .
  * Hunter [2007] J. D. Hunter, Matplotlib: A 2d graphics environment, Computing in Science & Engineering 9, 90 (2007).
  * Caswell  _et al._ [2021] T. A. Caswell, M. Droettboom, A. Lee, E. S. de Andrade, T. Hoffmann, J. Hunter, J. Klymak, E. Firing, D. Stansby, N. Varoquaux, J. H. Nielsen, B. Root, R. May, P. Elson, J. K. Seppänen, D. Dale, J.-J. Lee, D. McDougall, A. Straw, P. Hobson, hannah, C. Gohlke, T. S. Yu, E. Ma, A. F. Vincent, S. Silvester, C. Moad, N. Kniazev, E. Ernest, and P. Ivanov, matplotlib/matplotlib: Rel: v3.4.3 (2021).
  * Wilson and Fonner [2014] L. A. Wilson and J. M. Fonner, Launcher: A shell-based framework for rapid development of parallel parametric studies, in  _Proceedings of the 2014 Annual Conference on Extreme Science and Engineering Discovery Environment_, XSEDE ’14 (ACM, New York, NY, USA, 2014) pp. 40:1–40:8.

##  Appendix A Convergence

Details about the nature of convergence can be found in appendix B of [7]. To
summarize, though the spatial finite difference operators are at 8th order,
the error in the simulations does not scale to 8th order with spatial
resolution. This is due to a combination of lower order operations due
interpolation on the mesh refinement boundary (5th order accuracy), adaptive
mesh refinement operations and varying temporal resolution (from differing
spatial resolutions). For each simulation in the library, we have 3 different
resolutions which we use to check for convergence—$N=36,40,44$ corresponding
to the number of points in the finest grid radius. We compare the phase
difference between the highest resolution and the lower resolutions. To see
how much the phase difference reduces with resolution, we scale the phase
difference of the higher difference ($h_{40}-h_{44}$) to match the lower
difference ($h_{36}-h_{44}$). Figure 4 shows the phase difference of the
signals for the U1007 simulation. The order appears to be around 7 which is
reasonable for these simulations. Note that this is not the same scaling for
other simulations in the library—it can vary from 4 to 10. This illustrates
the point that it is difficult to pull out a universal convergence scaling of
the simulations.

Figure 4: Convergence of the phase difference between the waveform of the
highest resolution ($h_{44}$) and the lower resolutions ($h_{40}$, $h_{36}$)
with appropriate scaling to get a rough match. This suggests an order of
around 7 but this is not representative of the entire library. Note that the
plot includes the initial junk radiation (left of vertical dotted line) and
the merger and ringdown signal both of which have very large phase differences
that are cut out in the plot.

##  Appendix B Inferred Parameters from NRHybSur2dq8

Here we list the inferred parameters from the parameter survey of the
NRHybSur2dq8 library of quasi-circular, spin-aligned binary waveforms for both
the $(\ell=|m|=2)$ and the $l\leq 4$ modes separately. The simulations not
listed in Table 2 had consistently low FFs across all parameter space. The
resolution of the grid search was 0.1 in q, and 0.02 in spins near the
inferred values (a lower resolution search was initially done followed by a
finer search).

Simulation | $\ell=m=2$ | $l\leq 4$
---|---|---
| q | $\chi_{1z}$ | $\chi_{2z}$ | FF(%) | q | $\chi_{1z}$ | $\chi_{2z}$ | FF(%)
U0010 | 2.7 | 0.60 | -0.53 | 60.9 | 2.3 | 0.55 | 0.37 | 46.7
U0011 | 3.0 | 0.58 | 0.28 | 47.8 | 1.1 | 0.13 | 0.54 | 49.8
U0014 | 4.3 | -0.62 | -0.52 | 72.1 | 4.2 | -0.62 | -0.52 | 69.7
U0020 | 6.0 | -0.62 | -0.56 | 84.9 | 5.2 | -0.6 | -0.09 | 82.5
U0021 | 5.4 | 0.60 | -0.31 | 52.5 | 5.7 | 0.47 | 0.58 | 48.5
U0023 | 5.0 | 0.60 | -0.33 | 72.8 | 5.0 | 0.60 | -0.31 | 70.9
U1007 | 1.4 | 0.56 | 0.66 | 93.9 | 1.3 | 0.58 | 0.66 | 93.9
U1008 | 1.4 | -0.49 | -0.56 | 80.2 | 1.0 | -0.52 | -0.43 | 79.3
U1019 | 5.6 | 0.60 | 0.35 | 90.8 | 5.5 | 0.60 | 0.51 | 90.0
U0032 | 5.0 | -0.62 | 0.28 | 40.0 | 4.5 | -0.51 | -0.23 | 39.6
U0038 | 5.0 | -0.58 | -0.17 | 39.5 | 6.8 | -0.47 | -0.66 | 42.0
U0040 | 5.7 | -0.33 | -0.05 | 88.4 | 5.2 | -0.20 | -0.64 | 85.7
U0041 | 5.0 | 0.47 | 0.01 | 62.1 | 5.0 | 0.47 | -0.15 | 55.5
Table 2: Parameters from NRHybSur2dq8 that best match the simulation data
along with fitting factors (FFs) for both $(\ell=|m|=2)$ and the $l\leq 4$
modes. Low FFs indicate that spin-aligned eccentric signals, such as those in
our simulation library, will be poorly recovered or go missing when using
current quasi-circular template match filtering techniques. The only chance to
see these signals would be through unmodeled searches if they are sufficiently
loud.


proofProof

[orcid=0000-0001-7961-183X]

]organization=CSIS Department, BITS Pilani, Hyderabad Campus,
addressline=Jawahar Nagar, city=Hyderabad, postcode=500078, state=Telangana,
country=India

[orcid=0000-0002-7647-5358]

[cor1]Corresponding author

# Edge-Vertex Dominating Set in Unit Disk Graphs

Vishwanath R. Singireddy<EMAIL_ADDRESS>[  Manjanna
Basappa<EMAIL_ADDRESS>
###### Abstract

Given an undirected graph $G=(V,E)$, a vertex $v\in V$ is edge-vertex (ev)
dominated by an edge $e\in E$ if $v$ is either incident to $e$ or incident to
an adjacent edge of $e$. A set $S^{ev}\subseteq E$ is an edge-vertex
dominating set (referred to as ev-dominating set) of $G$ if every vertex of
$G$ is ev-dominated by at least one edge of $S^{ev}$. The minimum cardinality
of an ev-dominating set is the ev-domination number. The edge-vertex
dominating set problem is to find a minimum ev-domination number. In this
paper we prove that the ev-dominating set problem is NP-hard on unit disk
graphs. We also prove that this problem admits a polynomial-time approximation
scheme on unit disk graphs. Finally, we give a simple 5-factor linear-time
approximation algorithm.

###### keywords:

Unit disk graph Edge-vertex dominating set Approximation scheme

##  1 Introduction

Given an undirected graph $G=(V,E)$, the edge neighborhood of an edge
$e^{\prime}\in E$ is the set of edges in $E$ which share a common vertex $v\in
V$ with $e^{\prime}$, i.e., the set of all edges which are adjacent to
$e^{\prime}$. The set of these neighbors of $e^{\prime}$ is represented as the
set $N_{e}(e^{\prime})=\\{f\in E\mid e^{\prime}$ and $f$ share a common vertex
$v\in V\\}$. The closed edge neighborhood of $e^{\prime}$ is defined as
$N_{e}[e^{\prime}]=N_{e}(e^{\prime})\cup\\{e^{\prime}\\}$. The edge
neighborhood of a set $S\subseteq E$ is $N_{e}(S)=\bigcup_{e^{\prime}\in
S}N_{e}(e^{\prime})$. Similarly, the closed edge neighborhood of a set
$S\subseteq E$ is $N_{e}[S]=\bigcup_{e^{\prime}\in S}N_{e}[e^{\prime}]\cup S$.
The edge neighborhood of neighborhood of $e^{\prime}$ is
$N_{e}(N_{e}(e^{\prime}))=N_{e}^{2}(e^{\prime})$. Similarly, the $r$-th edge
neighborhood is $N_{e}^{r}(e^{\prime})=N_{e}(N_{e}^{r-1}(e^{\prime}))$ for an
integer $r\geq 1$.

Given an undirected graph $G=(V,E)$, a vertex $v\in V$ is ev (edge-
vertex)-dominated by an edge $e\in E$ if $v$ is incident to $e$ (i.e., an
endpoint of $e$) or if $v$ is incident to an adjacent edge of $e$. A set
$S^{ev}\subseteq E$ is an edge-vertex dominating set (EVDS) (referred to as
ev-dominating set) of $G$ if at least one edge of $S^{ev}$ (at least two edges
for double edge-vertex dominating set), ev-dominates every vertex of $G$. The
minimum cardinality of an ev-dominating set is the ev-domination number,
denoted by $\gamma_{ev}(G)$. If $S^{ev}$ is an edge-vertex dominating set and
every edge in $S^{ev}$ have an endpoint with other edge in $S^{ev}$, then
$S^{ev}$ is called the total edge-vertex dominating set, and the minimum
cardinality of this set is called the total edge-vertex domination number and
it is denoted by $\gamma^{t}_{ev}$. In the literature, analogous to the edge-
vertex dominating set there is a variant of the dominating set called vertex-
edge dominating set.

As well known, a given set $D$ of $n$ disks of unit diameter (hence called
unit disks) induces a graph $G$, where a unit disk graph (UDG) $G=(V,E)$ is an
undirected graph such that (i) each vertex $v$ in whose vertex set $V$
corresponds to a disk $d_{v}\in D$ of unit diameter in the plane, (ii) each
edge $(u,v)$ in whose edge set $E$ corresponds to a pair of mutually
intersecting disks $d_{u}$ and $d_{v}$ in the plane.

The applications of the edge-vertex dominating set problem arise in locating
the monitoring devices such as cameras to safeguard facilities in a given
region. We can place the monitoring devices at the endpoints of an edge that
is in the edge-vertex dominating set. Hence, these monitoring devices can
monitor all the adjacent facilities, including the monitoring devices, which
are at another endpoint of the edge that is in the edge-vertex dominating set.
If one of the devices fails, then the immediate adjacent device can service
those facilities that are monitored by the failed device.

##  2 Related Work

The edge-vertex dominating set and vertex-edge dominating set in a graph were
introduced by Peters [1]. The edge-vertex dominating set and vertex-edge
dominating set problems are NP-complete, even when restricted to bipartite
graphs [2]. For every nontrivial tree ${\cal T}$, an upper bound on
$\gamma_{ev}({\cal T})$ is $(\gamma_{t}({\cal T})+s-1)/2$ where $s$ is the
number of support vertices (the vertex adjacent to a leaf) [3]. The total
domination number ($\gamma_{t}$) of a tree is equal to the ev-domination
number ($\gamma_{ev}$) plus one [4]. The vertex-edge dominating set problem in
UDG is NP-complete [5]. Also, in [5], a polynomial time approximation scheme
(PTAS) is proposed. Finding $\gamma_{ve}$ even in cubic planar graphs is NP-
hard [6]. The vertex-edge domination problem can be solved in linear time on
block graphs [7]. In the same paper it is also shown that finding
$\gamma_{ve}$ in undirected path graphs is NP-complete. Given a connected
graph $G$ with $n$ vertices where $n\geq 6$, then we have
$\gamma_{ve}(G)\leq\lfloor\frac{n}{3}\rfloor$[8]. Boutrig et al. [9] gave an
upper bound for the independent ve-domination number in terms of the ve-
domination number for connected $K_{1,k}$-free graph with $k\geq 3$ and also
gave an upper bound on the ve-domination number for connected $C_{5}$-free
graph.

The double vertex-edge domination was introduced by Krishnakumari et al. [10].
They showed that finding $\gamma_{dve}$ in a bipartite graph is NP-complete
and also proved that for every non-trivial connected graph $G$,
$\gamma_{dve}(G)\geq\gamma_{ve}(G)+1$, and $\gamma_{dve}({\cal
T})=\gamma_{ve}({\cal T})+1$ or $\gamma_{dve}({\cal T})=\gamma_{ve}({\cal
T})+2$ for any tree ${\cal T}$. Finding $\gamma_{dve}$ in chordal graphs is
NP-complete [11]. They gave a linear time algorithm to find $\gamma_{dve}$ in
proper interval graphs and also showed that finding $\gamma_{dve}$ in general
graphs with vertices having degree at most 5 is APX-complete. The double
version of edge-vertex domination was studied by Sahin and Sahin [12]. They
also gave the relationship between $\gamma_{dev}$ and $\gamma_{dve}$,
$\gamma_{t}$, $\gamma_{ev}$ for trees and graphs, and also gave formulas to
determine the double ev-domination number of paths and cycles. Sahin and Sahin
[13] proved that the total ev-dominating set problem is NP-hard for bipartite
graphs. They also showed that $(n-l+2s-1)/2$ is the upper bound for
$\gamma^{t}_{ev}$ for a tree ${\cal T}$ with order $n$, $l$ leaves and $s$
supporting vertices. To the best of our knowledge, in the literature, ev-
dominating set problem is not yet studied in the context of geometric
intersection graphs.

###  2.1 Our Contribution

In this article, we study the EVDS problem on unit disk graphs. We show that
the decision version of this problem is NP-complete in UDGs. We also prove
that this problem on UDG admits a polynomial time approximation scheme (PTAS).
We finally present a simple 5-factor linear-time approximation algorithm.

##  3 Hardness Results

In this section, we show that the decision version of the EVDS is NP-complete,
as stated below. We describe a polynomial time reduction from the vertex cover
problem, which is known to be NP-complete in planar graphs with maximum degree
3 [14], to this problem on UDG.

The EVDS problem on UDGs (EVDS-UDG)
Instance: A UDG $G=(V,E)$ and a positive integer $k$.
Question: Does there exist an edge-vertex dominating set $S^{ev}$ of $G$ such
that $S^{ev}\leq k$.

###### Lemma 1

([15]) An embedding of a planar graph $G=(V,E)$ with maximum degree $4$ in the
plane is possible such that this embedding uses only $O(|V|^{2})$ area and its
vertices are at integer coordinates and its edges are drawn so that they are
along the grid line segments of the form $x=i$ or $y=j$, for some $i$ and $j$.

Biedl and Kant [16] gave an algorithm that produces this kind of embedding in
linear time (see Figure 1).

###### Corollary 2

([5]) An embedding of a planar graph $G=(V,E)$ with $|V|\geq 3$ and maximum
degree 3 in the plane can be constructed in polynomial time, where the
embedding is such that the vertices of $G$ are at $(4i,4j)$ and the edges of
$G$ are drawn as a sequence of consecutive line segments along the lines
$x=4i$ or $y=4j$, for some $i$ and $j$.

Figure 1: (a) A planar graph $G$ with max degree 3. (b) The embedding of $G$
on a grid.

###### Lemma 3

Let $G=(V,E)$ be an instance of the vertex cover problem with number of edges
at least 2. An instance $G^{\prime}=(V^{\prime},E^{\prime})$ of EVDS-UDG can
be constructed from $G$ in polynomial time.

######  Proof 3.4.

The construction of $G^{\prime}=(V^{\prime},E^{\prime})$ from $G=(V,E)$ is as
follows: First we embed the graph $G=(V,E)$ into the grid of size $4n\times
4n$ such that each edge of $E$ is composed of a sequence of horizontal or
vertical line segment(s) each of whose length is four units long, using one of
the algorithms discussed in [17, 18]. The points
$\\{p_{1},p_{2},\dots,p_{n}\\}$ are referred as the node points in the
embedding with respect to the vertex set of $G$ (see Figure 1(a) and 1(b)).
For each edge of length greater than four units, we add a joint point at the
joining of two line segments in the embedding other than the node points. Name
these points as the joint points (see empty circles in Figure 2). Then for
each line segment in the embedding we add three extra points such that each at
a distance of 1 unit from one another, at least 1 unit from node points and
joint points. Name these points as the added points (see filled square points
in Figure 2).

Let $A$ be the set of added points and $J$ be the set of joint points. We
construct an UDG $G^{\prime}=(V^{\prime},E^{\prime})$ where the vertex set
$V^{\prime}=V\cup A\cup J$, and there is an edge between two vertices of
$V^{\prime}$ if and only if the distance between them is at most 1 unit (see
Figure 2). If $l$ is the total number of line segments in the embedding, then
$|A|=3l$ and $|J|$ is at most $l-|E|$. It follows from Lemma 1 that $l$ is at
most $O(n^{2})$. Clearly, the graph defined by the intersection of unit disks
centered at points in $V^{\prime}$ is a unit disk graph. Since both the sets
$|V^{\prime}|$ and $|E^{\prime}|$ are bounded by $O(n^{2})$, we can construct
$G^{\prime}$ from $G$ in polynomial time. ∎

Figure 2: A unit disk graph construction from embedding

######  Lemma 3.5.

The EVDS-UDG problem is in NP.

######  Proof 3.6.

Given a subset $S^{ev}\subseteq E$ and a positive integer $k$, we can verify
that $S^{ev}$ is an edge-vertex dominating set of size at most $k$ in
polynomial time, by checking whether each vertex $v\in V$ is edge-vertex
dominated by an edge $e\in S^{ev}$ in polynomial time. ∎

We prove the NP-hardness of the EVDS-UDG problem by reducing the decision
version of the vertex cover on planar graph with maximum degree 3 to it. Let
$G=(V,E)$ be a planar graph with maximum degree 3. Then from Lemma 3 we can
construct an instance $G^{\prime}=(V^{\prime},E^{\prime})$ of EVDS-UDG in
polynomial time.

Figure 3: (a) Vertex cover of $G$. (b) EVDS of UDG.

######  Lemma 3.7.

G has a vertex cover of size at most $k$ if and only if $G^{\prime}$ has an
edge-vertex dominating set of size at most $3k+l$.

######  Proof 3.8.

Let $D\subseteq V$ be a vertex cover of $G$ of cardinality at most $k$. Let
$D^{\prime}$ be the set of vertices of $G^{\prime}$ that correspond to the
vertices in $D$. Now, choose every edge of $G^{\prime}$ that is incident to
every vertex in $D^{\prime}$. Represent these chosen edges as the set
$N^{\prime}$. Since $G^{\prime}$ is constructed from $G$, every vertex of
$G^{\prime}$ has degree at most 3. Therefore, the cardinality of $N^{\prime}$
is at most 3$k$. Now, choose an edge of each line segment apart from the edges
of $N^{\prime}$, and let $N^{\prime\prime}$ be the set of those chosen edges.
The cardinality of $N^{\prime\prime}$ is $l$ since there are $l$ line segments
in the embedding. Therefore, we have $|N^{\prime}|+|N^{\prime\prime}|\leq
3k+l$. Let $p_{i}\rightsquigarrow p_{j}$ be a path of $G^{\prime}$
corresponding to an edge $(v_{i},v_{j})\in E$ of $G$. Since $D$ is the set of
vertices corresponding to the vertex cover of $G$, either $p_{i}\in
D^{\prime}$ or $p_{j}\in D^{\prime}$ (or both vertices are in $D^{\prime}$).
An edge for each line segment will be chosen as follows:

  * $(1)$

If only one vertex of $(p_{i},p_{j})$ is in $D^{\prime}$, then choose the
third edge of line segment that is incident to that vertex in $D^{\prime}$. If
both vertices of $(p_{i},p_{j})$ are in $D^{\prime}$ then choose third edge of
line segment that is incident to either $p_{i}$ or $p_{j}$.

  * $(2)$

Next, choose every fourth edge from the chosen edge on each line segment by
traversing through the line segments of $p_{i}\rightsquigarrow p_{j}$ until
reaching $p_{j}$ (see Figure 3 for illustration).

  * $(3)$

Apply the same process for each sequence of line segments of $G^{\prime}$
corresponding to each edge in $G$.

Now, observe that $S^{ev}=N^{\prime}\cup N^{\prime\prime}$ is the set of edges
in $G^{\prime}$ such that every vertex in $G^{\prime}$ is ev-dominated by at
least one edge $e\in S^{ev}$ and $|S^{ev}|\leq 3k+l$.

To prove the sufficiency, consider any edge-vertex dominating set
$S^{ev}\subseteq E^{\prime}$ of size at most $3k^{\prime}+l$, in $G^{\prime}$,
where $k^{\prime}$ is a positive integer.

Consider a simple path $p_{i}\rightsquigarrow p_{j}$ in $G^{\prime}$ between a
pair of node points $p_{i}$ and $p_{j}$ (say, $p_{3}\rightsquigarrow p_{5}$ in
Fig. 4) such that the other vertices the path $p_{i}\rightsquigarrow p_{j}$
passes through are only joint points and added points. Now we want to ensure
that for any such path all the incident edges at one of $p_{i}$ and $p_{j}$
are part of $S^{ev}$. Observe that if both $p_{i}$ and $p_{j}$ are ev-
dominated by only edges of $E(p_{i}\rightsquigarrow p_{j})\cap S^{ev}$, then
$|E(p_{i}\rightsquigarrow p_{j})|/4$ edges are not sufficient to ev-dominate
all the vertices of $p_{i}\rightsquigarrow p_{j}$. Hence, the number of edges
in $E(p_{i}\rightsquigarrow p_{j})\cap S^{ev}$ is greater than
$|E(p_{i}\rightsquigarrow p_{j})|/4$. Then, we can reselect the same number of
edges in $p_{i}\rightsquigarrow p_{j}$ as in $E(p_{i}\rightsquigarrow
p_{j})\cap S^{ev}$ and update $S^{ev}$ such that at least one edge of them is
now incident at $p_{i}$ or $p_{j}$ (consider the simple path
$p_{3}\rightsquigarrow p_{5}$ in Figure 4, the darken edges are in $S^{ev}$,
then we need to add one more edge to $S^{ev}$ to ev-dominate $p_{5}$, i.e.,
either first or second edge from $p_{5}$ so that $p_{5}$ will be ev-
dominated).

Figure 4: Edges in $S^{ev}$ of simple path $p_{3}\rightsquigarrow p_{5}$

We can repeat the above process for other such paths in $G^{\prime}$. However,
if both or at least one of $p_{i}$ and $p_{j}$ is ev-dominated by edges
outside $p_{i}\rightsquigarrow p_{j}$, then we can simply select all the
incident edges at one of them and replace the edges in
$E(p_{i}\rightsquigarrow p_{j})\cap S^{ev}$ with their adjacent ones so that
the other endpoint of $p_{i}\rightsquigarrow p_{j}$ is ev-dominated. Note that
the cardinality of the updated $S^{ev}$ is still at most $3k^{\prime}+l$,
because $\sum_{i,j}(|E(p_{i}\rightsquigarrow p_{j})\cap S^{ev}|-1)\leq l$,
where $k^{\prime}$ is a positive integer.

Now, given such a $S^{ev}$, we can select the vertices in $G$ corresponding to
those node points in $G^{\prime}$, whose all the incident edges are in
$S^{ev}$. Clearly, this set $D$ of the selected vertices form a vertex cover
of size at most $k^{\prime}$ in $G$. The construction of $D$ takes polynomial
time. ∎

######  Theorem 3.9.

The EVDS-UDG problem is NP-complete.

######  Proof 3.10.

Follows from Lemma 3.5 and 3.7. ∎

##  4 Polynomial Time Approximation Scheme

In this section, we propose a PTAS for the EVDS set problem in a UDG. It is
based on the concept of $m$-separated collection of subsets, which was
introduced by Nieberg and Hurink [19]. This concept was used by many other
authors to develop PTAS (for e.g., the Roman dominating set [20], minimum
Liar’s dominating set [21], vertex-edge dominating set [5]). However, the way
we use it here is quite different from these as we have to select edges to
dominate vertices in the EVDS problem. Though our proof idea resembles in
them, this is a completely different domination model. Let $G=(V,E)$ be a UDG.
Let $h(e_{1},e_{2})$ denote the minimum number of edges in a simple path
between the endpoints of the edges $e_{1}$ and $e_{2}$. Consider any two
subsets $E_{1}\subseteq E$ and $E_{2}\subseteq E$, $h(E_{1},E_{2})$ is defined
as the minimum number of edges between any two edges $e_{1}\in E_{1}$ and
$e_{2}\in E_{2}$. We use $EVD(A)$ to denote an ev-dominating set and
$EVD_{opt}(A)$ to denote the optimal ev-dominating set of the edge-induced
subgraph corresponding to $A(\subseteq E)$ (i.e., the subgraph induced by the
set of edges $A(\subseteq E)$ and the endpoints of edges in $A$).

Let $S$ be a set of $k$ pairwise disjoint subsets of $E$, i.e., $S_{i}\subset
E$ for $i=1,2,\dots,k$. If $h(S_{i},S_{j})\geq m$, for $i\geq 1$, $j\leq k$
and $i\neq j$, then $S$ is called as $m$-separable collection of subsets of
$E$ (see Figure 5 for $m=4$).

######  Lemma 4.11.

In a graph $G=(V,E)$, if $S=\\{S_{1},S_{2},\dots,S_{k}\\}$ is a $4$-separated
collection of $k$ subsets of $E$, then

$\sum_{i=1}^{k}|EVD_{opt}(S_{i})|\leq|EVD_{opt}(E)|.$

######  Proof 4.12.

Let $A_{i}$ be the set of edges which are adjacent to edges of $S_{i}$ for
each $i=1,2,\dots,k$ and $R_{i}$ the set of edges such that $R_{i}=S_{i}\cup
A_{i}$. The edges in sets $R_{1},R_{2},\dots,R_{k}$ are pairwise disjoint,
since the set $S$ is 4-separated collection of edges i.e., $(R_{i}\cap
R_{j})=\emptyset$, where $i\neq j$. Hence, the edges of $EVD_{opt}(E)\cap
R_{i}$ will ev-dominate every vertex in $S_{i}$, since $EVD_{opt}(E)$ will ev-
dominate every vertex $v\in V$. On the other hand, also
$EVD_{opt}(S_{i})\subset R_{i}$ ev-dominates every vertex of $S_{i}$, with a
minimum number of edges of $G$. This implies that
$|EVD_{opt}(S_{i})|\leq|EVD_{opt}(E)\cap R_{i}|$. For all $k$ subsets of edges
in the 4-separated collection $S$, we get

$\begin{split}\sum_{i=1}^{k}|EVD_{opt}(S_{i})|&\leq\sum_{i=1}^{k}|(EVD_{opt}(E)\cap
R_{i})|\\\ &\leq|EVD_{opt}(E)|.\end{split}$

∎

The above Lemma 4.11 states that a 4-separated collection of subsets of edges
$S$ will give a lower bound on the cardinality of a EVDS. Hence, we can get an
approximation for the EVDS in $G$, if we are able to enlarge $S_{i}$ to
subsets $Q_{i}\subset E$, in such way that EVDS of expansions are bounded
locally and dominate every $v\in V$ globally.

Figure 5: 4-Separable collection of edge sets
$S=\\{S_{1},S_{2},S_{3},S_{4},S_{5}\\}$

######  Lemma 4.13.

In a graph $G=(V,E)$, let $S=\\{S_{1},S_{2},\dots,S_{k}\\}$ be a 4-separated
collection of subsets of edges and $Q=\\{Q_{1},Q_{2},\dots,Q_{k}\\}$ be a
collection of subsets of $E$ with $S_{i}\subseteq Q_{i}$ for every
$i=1,2,\dots,k$. If there is a $\rho\geq 1$ such that

$|EVD_{opt}(Q_{i})|\leq\rho|EVD_{opt}(S_{i})|$

holds for every $i=1,2,\dots,k$, and if $\bigcup_{i=1}^{k}EVD_{opt}(Q_{i})$ is
an edge-vertex dominating set of $G$, then $\sum_{i=1}^{k}|EVD_{opt}(Q_{i})|$
is the $\rho$-approximation of minimum EVDS set of $G$.

######  Proof 4.14.

From Lemma 4.11 we have,

$\sum_{i=1}^{k}|EVD_{opt}(S_{i})|\leq|EVD_{opt}(E)|.$

Hence,
$\sum_{i=1}^{k}|EVD_{opt}(Q_{i})|\leq\rho\sum_{i=1}^{k}|EVD_{opt}(S_{i})|\leq\rho|EVD_{opt}(E)|$.
∎

In the following section we discuss a procedure to construct the subsets
$Q_{i}\subset E$, that contains a 4-separated collection of edges
$S_{i}\subset Q_{i}$, in such a way that a local $(1+\epsilon)$-approximation
can be guaranteed. The union of the respective local EVDS will ev-dominate the
entire vertex set of $G$, which results in a global
$(1+\epsilon)$-approximation for the EVDS problem.

###  4.1 Subset Construction

Here, we discuss the construction of the 4-separated collection of subsets of
edges $S=\\{S_{1},S_{2},\dots,S_{k}\\}$ and respective subsets
$Q=\\{Q_{1},Q_{2},\dots,Q_{k}\\}$ of $E$ such that $S_{i}\subseteq Q_{i}$ for
every $i=1,2,\dots,k$. The basic idea of the algorithm is as follows. We start
with an arbitrary edge $e\in E$ and consider the $r$-th edge neighborhood of
$e$, for $r=0,1,2,\dots$, with $N_{e}^{0}[e]=e$. We compute the EVDS for these
edge neighborhoods until the following condition holds

$|EVD(N_{e}^{r+4}[e])|>\rho|EVD(N_{e}^{r}[e])|$ (1)

Let $r_{1}$ be the smallest $r$ that violates the above inequality (1). Set
$S_{1}=N_{e}^{r_{1}}[e]$, $Q_{1}=N_{e}^{r_{1}+4}[e]$ and
$E_{i+1}=E_{i}\backslash(N_{e}^{r_{i}+4}(e))$, where $E_{1}=E$. We follow this
procedure iteratively for each graph induced by $E_{i+1}$ and until
$E_{i+1}=\emptyset$, finally returning the sets
$S=\\{S_{1},S_{2},\dots,S_{k}\\}$ and $Q=\\{Q_{1},Q_{2},\dots,Q_{k}\\}$.

We find the edge-vertex dominating set of the $r$-edge neighborhood
$EVD(N_{e}^{r}[e])$ of an edge $e$, with respect to the graph $G$ as follows.
Find a maximal matching $M$ for the graph induced by the edges of
$N_{e}^{r}[e]$. We can observe that the edges in $M$ forms an edge-vertex
dominating set for the graph induced by $N_{e}^{r}[e]$. Hence,
$EVD(N_{e}^{r}[e])=M$ as the following lemma says.

######  Lemma 4.15.

A maximal matching $M$ of the graph $G^{\prime}=(V^{\prime},E^{\prime})$
induced by the edges in $N_{e}^{r}[e]$, is an EVDS of $N_{e}^{r}[e]$.

######  Proof 4.16.

For the contradiction, assume that $M$ is not an EVDS of the graph
$G^{\prime}=(V^{\prime},E^{\prime})$ induced by the edges in $N_{e}^{r}[e]$.
It means that there exist a vertex $v\in V^{\prime}$ which is incident to an
edge $e^{\prime}\in E^{\prime}$ such that $N_{e}[e^{\prime}]\cap M=\emptyset$.
It contradicts that $M$ is a maximal matching in $G^{\prime}$ as the set
$M\cup\\{e^{\prime}\\}$ is a matching in $G^{\prime}$. Thus, the lemma
follows. ∎

######  Lemma 4.17.

If $G^{\prime}=(V^{\prime},E^{\prime})$ is a UDG induced by the edges in
$N_{e}^{r}[e]$ and $M$ is the maximal matching of $G^{\prime}$ then
$|EVD(N_{e}^{r}[e])|\leq O(r^{2})$.

######  Proof 4.18.

First we find a maximal matching $M$, before finding the EVDS in
$G^{\prime}=(V^{\prime},E^{\prime})$ which is induced by the edges of
$N_{e}^{r}[e]$. The number of edges in $M$ of $G^{\prime}$ is bounded by the
number of unit disks that are packed in a disk of radius $r+2$ and centered at
middle of the edge $e$. Hence, $|M|\leq(r+2)^{2}$ and cardinality of the
$EVD(N_{e}^{r}[e])$ is bounded by $|M|$ (see Lemma 4.15). Therefore, we have

$|EVD(N_{e}^{r}[e])|\leq|M|\leq(r+2)^{2}\leq O(r^{2}).$

∎

######  Theorem 4.19.

There exists an $r_{1}$ which violates the following inequality.

$|EVD(N_{e}^{{r_{1}}+4}[e])|>\rho|EVD(N_{e}^{r_{1}}[e])|$

where $\rho=1+\epsilon$ and it is bounded by
$O(\frac{1}{\epsilon}\log{\frac{1}{\epsilon}})$.

######  Proof 4.20.

For the contradiction, assume that there exists an edge $e\in E$ such that

$|EVD(N_{e}^{r+4}[e])|>\rho|EVD(N_{e}^{r}[e])|$

for all $r\geq r_{1}$. Then, from Lemma 4.17 , we have

$(r+6)^{2}\geq|EVD(N_{e}^{r+4}[e])|.$

Hence, when $r$ is even we have,

$\begin{split}(r+6)^{2}\geq|EVD(N_{e}^{r+4}[e])|&>\rho|EVD(N_{e}^{r}[e])|>\\\
\cdots&>\rho^{\frac{r}{2}}|EVD(N_{e}^{2}[e])|\geq\rho^{\frac{r}{2}}\end{split}$
(2)

and when $r$ is odd, we have,

$\begin{split}(r+6)^{2}\geq|EVD(N_{e}^{r+4}[e])|&>\rho|EVD(N_{e}^{r}[e])|>\\\
\cdots&>\rho^{\frac{r-1}{2}}|EVD(N_{e}^{1}[e])|\geq\rho^{\frac{r-1}{2}}\end{split}$
(3)

Now, we can observe that in both the inequalities (2), (3) on the left hand
side we have a polynomial in $r$ which is at least the right hand side value
which is exponential in $r$, it is a contradiction. Therefore, for all $r\geq
r_{1}$ the inequality (2) cannot hold, hence there exist such $r_{1}$.
Ultimately, $r_{1}$ depends only on $\rho$, not on the size of the edge-
induced subgraph by $N_{e}^{r+4}[e]$. As in [19], we can argue that $r_{1}$ is
bounded by $O(\frac{1}{\epsilon}\log{\frac{1}{\epsilon}})$ where
$\rho=1+\epsilon$. ∎

######  Lemma 4.21.

For an edge $e\in E$, $EVD_{opt}(Q_{i})$ can be computed in polynomial time.

######  Proof 4.22.

From the way of construction of $Q_{i}$, we can see that $Q_{i}\subseteq
N_{e}^{r+4}[e]$. The cardinality of $N_{e}^{r+4}[e]$ is bounded by $O(r^{2})$
(see Lemma 4.17), where $r$ is bounded by
$O(\frac{1}{\epsilon}\log{\frac{1}{\epsilon}})$ (see Theorem 4.19). Hence, we
need at most $O(n^{r^{2}})$ possible combinations of tuples to check whether
the selected tuple is an EVDS of $Q_{i}$.∎

######  Lemma 4.23.

$\bigcup_{i=1}^{k}EVD(Q_{i})$ is an edge-vertex dominating set in $G=(V,E)$.

######  Proof 4.24.

It follows from the construction of the collection of subsets of edges
$\\{Q_{1},Q_{2},$ $\dots,Q_{k}\\}$ that each edge that is incident to a vertex
$v\in V$ belongs to a specific subset $Q_{i}$ and $EVD(Q_{i})$ is an EVDS of
the graph induced by the edges of $Q_{i}$. Therefore, every vertex $v\in V$ is
incident to at least one edge $e$ such that at least one edge of $N_{e}[e]$ is
in $\bigcup_{i=1}^{k}EVD(Q_{i})$. ∎

######  Corollary 4.25.

$\bigcup_{i=1}^{k}EVD_{opt}(Q_{i})$ is an edge-vertex dominating set in
$G=(V,E)$, for the collection of subsets of edges
$Q=\\{Q_{1},Q_{2},\dots,Q_{k}\\}$.

######  Theorem 4.26.

For a given unit disk graph and an $\epsilon>0$, there exists a PTAS (an
$(1+\epsilon)$-approximation) algorithm for the EVDS problem with running time
$n^{O(c^{2})}$, where $c=(\frac{1}{\epsilon}\log{\frac{1}{\epsilon}})$.

######  Proof 4.27.

Follows from Corollary 4.25 and Lemma 4.21. ∎

##  5 5-Factor Approximation Algorithm

In this section, we present a $5$-factor approximation algorithm for the EVDS
problem on UDG. Let ${\cal S}$ be a set of $n$ points given in the Euclidean
plane. We join two of these points with an edge if the distance between those
two points is less than or equal to 1 unit. Let $E$ be the set of such edges
with cardinality $m$ and $V$ be the set of vertices corresponding to points in
${\cal S}$. The graph induced by $V$ and $E$ will form a UDG since the
distance between any two end-points of $e\in E$ is at most 1. Assume that such
an UDG has no isolated vertex, otherwise EVDS does not exist. To present an
approximation algorithm, we consider a rectangular region that contains UDG,
and then we partition the region into a set of hexagons. Let ${\cal R}$ be an
axis-parallel rectangle that contains these points. Consider an hexagonal
partition of ${\cal R}$, where each hexagon is of side length $\frac{1}{2}$
and hence the maximum distance between any two points inside it is at most 1.
Assume that no point in $V$ lies on the boundary of any hexagon in the
partition.

######  Lemma 5.28.

Any edge $e$ with its two endpoints lying in adjacent hexagons can ev-dominate
every point in those two hexagons.

######  Proof 5.29.

It follows from the fact that there will be an edge between any two points
that lie in a hexagon since the distance between those two points will be at
most 1. Therefore, an edge $e\in EVDS$ whose endpoint lies in that hexagon
will ev-dominate every other point in that hexagon. ∎

The outline of the algorithm is as follows. Initialize the set $S^{ev}$ of
edges that are in EVDS as empty. Now, arbitrarily pick an edge $e\in E$ whose
endpoints lie in different hexagons and add this edge to $S^{ev}$ and set
$E=E\backslash\\{e\\}$. Mark all points that are ev-dominated by $e$. If there
are any unmarked vertices, now choose an edge $e\in E$ that is incident to
unmarked vertex and having another endpoint in a different hexagon, add $e$ to
$S^{ev}$ and mark all unmarked points that are ev-dominated by $e$. Repeat
this process until every point in $V$ is marked (see Algorithm 1).

Algorithm 1 Edge-vertex domination

Input: An UDG $G=(V,E)$ placed over an hexagonal grid.
Output: An EVDS of $G$.

1: Initialize $S^{ev}=\emptyset$, $E^{\prime}=E$, and let all vertices in $V$
be unmarked initially.

2: while there is an edge $e\in E^{\prime}$ with its both end-points unmarked
do

3: Pick an edge $e\in E^{\prime}$ such that $e=(u,v)$, the unmarked vertices
$u\in A$ and $v\in B$, where $A$ and $B$ are adjacent hexagonal cells

4: Set $S^{ev}=S^{ev}\cup\\{e\\}$ and $E^{\prime}=E^{\prime}\backslash\\{e\\}$

5: Mark all vertices which are incident to $N_{e}(e)$

6: end while

7: while there is an hexagon containing unmarked vertices do

8: Pick any arbitrary edge $e\in E$ with at least one endpoint in that hexagon

9: $S^{ev}=S^{ev}\cup\\{e\\}$

10: end while

11: return $S^{ev}$

######  Theorem 5.30.

Algorithm 1 gives a factor 5-approximation for EVDS problem on a UDG in
$O(m+n)$ time.

######  Proof 5.31.

Algorithm 1 picks an edge $e$ arbitrarily whose endpoints lie in different
hexagons and then repeatedly selects an edge between an unmarked vertex and
another vertex in the different hexagon until there are no unmarked vertices
(see Figure 6). In Figure 6, we can observe that Algorithm 1 selected EVDS as
$\\{e_{1},e_{2},e_{3},e_{4},e_{5}\\}$ whose cardinality is five whereas the
optimal solution may have a single edge that will ev-dominate every given
point (see edge $e$ in Figure 6). Next, one can see that the algorithm may
select at most five times the optimal value, since an edge between points in
two adjacent hexagons may ev-dominate the points in all of its adjacent eight
hexagons. As we look at every edge between points to know whether its
endpoints are the marked vertices and select an edge at line 3 and 8 of
Algorithm 1, the running time is polynimial in $m$ and $n$.

The approximation factor five of Algorithm 1 follows due to the following two
facts:

  1. 1.

If both the endpoints of an edge $e$ selected by Algorithm 1 lie within the
same hexagon, then none of the vertices corresponding to these points are
adjacent to a vertex of its adjacent hexagons.

  2. 2.

Otherwise an edge $e$ selected by Algorithm 1 ev-dominates all the points in
both the adjacent hexagons (Lemma 5.28).

All the cells (hexagons) in ${\cal R}$ can be grouped as a collection of mega-
cells (as in Figure 7), where each mega-cell consists of ten adjacent
hexagonal cells (cells colored with same color in Figure 7). Algorithm 1 picks
at most five edges to ev-dominate all the points in each mega-cell, whereas in
optimal solution at least one edge is required.∎

Figure 6:  $EVDS=\\{e_{1},e_{2},e_{3},e_{4},e_{5}\\}$, and minimum
$EVDS=\\{e\\}$ Figure 7: Four adjacent Mega-cells

##  6 Discussion

We can assign weights $w_{e}$ to the edges of UDG $G=(V,E)$ such that $w_{e}$
is the Euclidean distance between the endpoints of the edge $e\in E$. We then
have a weighted unit disk graph $G$ and the goal is to find an ev-dominating
set $S^{ev}$ in $G$, where $w(S^{ev})=\sum_{e\in S^{ev}}w(e)$ is minimized. We
believe that a motivation for this is that it is quite common for a pair of
monitoring devices placed at the endpoints of an edge that is in the ev-
dominating set to be such that the maintenance cost is minimized, where the
cost is proportional to distance a maintenance staff has to travel back and
forth between the sites of these two devices. It is not clear whether we can
use the $m$-separated collection concept to extend our PTAS for the weighted
variant of the problem. Hence, this could be a future work.

##  7 Conclusion

In this paper, we have proved that the edge-vertex dominating set problem in
unit disk graphs is NP-complete. We also showed that the EVDS problem admits a
polynomial time approximation scheme (PTAS). We also gave a simple 5-factor
approximation algorithm in linear time.

## References

  * Peters [1987] K. Peters,  Theoretical and algorithmic results on domination and connectivity (nordhaus-gaddum, gallai type results, max-min relationships, linear time, series-parallel). (1987).
  * Lewis [2007] J. R. Lewis, Vertex-edge and edge-vertex domination in graphs, Ph.D. thesis, Ph. D. Thesis, Clemson University, Clemson, 2007.
  * Venkatakrishnan and Krishnakumari [2018] Y. B. Venkatakrishnan, B. Krishnakumari,  An improved upper bound of edge–vertex domination number of a tree,  Information Processing Letters 134 (2018) 14–17.
  * Krishnakumari et al. [2016] B. Krishnakumari, Y. Venkatakrishnan, M. Krzywkowski,  On trees with total domination number equal to edge-vertex domination number plus one,  Proceedings-Mathematical Sciences 126 (2016) 153–157.
  * Jena and Das [2021] S. K. Jena, G. K. Das,  Vertex-edge domination in unit disk graphs,  Discrete Applied Mathematics (2021).
  * Ziemann and Żyliński [2020] R. Ziemann, P. Żyliński,  Vertex-edge domination in cubic graphs,  Discrete Mathematics 343 (2020) 112075.
  * Paul and Ranjan [2019] S. Paul, K. Ranjan,  On vertex-edge and independent vertex-edge domination,  in: International Conference on Combinatorial Optimization and Applications, Springer, 2019, pp. 437–448.
  * Żyliński [2019] P. Żyliński,  Vertex-edge domination in graphs,  Aequationes mathematicae 93 (2019) 735–742.
  * Boutrig et al. [2016] R. Boutrig, M. Chellali, T. W. Haynes, S. T. Hedetniemi,  Vertex-edge domination in graphs,  Aequationes mathematicae 90 (2016) 355–366.
  * Krishnakumari et al. [2017] B. Krishnakumari, M. Chellali, Y. B. Venkatakrishnan,  Double vertex-edge domination,  Discrete Mathematics, Algorithms and Applications 9 (2017) 1750045.
  * Venkatakrishnan and Kumar [2019] Y. B. Venkatakrishnan, H. N. Kumar,  On the algorithmic complexity of double vertex-edge domination in graphs,  in: International Workshop on Algorithms and Computation, Springer, 2019, pp. 188–198.
  * Şahin and Şahin [2020] B. Şahin, A. Şahin,  Double edge–vertex domination,  in: International Conference on Intelligent and Fuzzy Systems, Springer, 2020, pp. 1564–1572.
  * Sahin and Sahin [2020] A. Sahin, B. Sahin,  Total edge–vertex domination,  RAIRO-Theoretical Informatics and Applications 54 (2020) 1.
  * Garey and Johnson [1979] M. R. Garey, D. S. Johnson, Computers and intractability, volume 174, freeman San Francisco, 1979.
  * Valiant [1981] L. G. Valiant,  Universality considerations in vlsi circuits,  IEEE Transactions on Computers 100 (1981) 135–140.
  * Biedl and Kant [1998] T. Biedl, G. Kant,  A better heuristic for orthogonal graph drawings,  Computational Geometry 9 (1998) 159–180.
  * Hopcroft and Tarjan [1974] J. Hopcroft, R. Tarjan,  Efficient planarity testing,  Journal of the ACM (JACM) 21 (1974) 549–568.
  * Itai et al. [1982] A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter,  Hamilton paths in grid graphs,  SIAM Journal on Computing 11 (1982) 676–686.
  * Nieberg and Hurink [2005] T. Nieberg, J. Hurink,  A ptas for the minimum dominating set problem in unit disk graphs,  in: International Workshop on Approximation and Online Algorithms, Springer, 2005, pp. 296–306.
  * Shang and Hu [2007] W. Shang, X. Hu,  The roman domination problem in unit disk graphs,  in: International conference on computational science, Springer, 2007, pp. 305–312.
  * Jallu et al. [2020] R. K. Jallu, S. K. Jena, G. K. Das,  Liar’s domination in unit disk graphs,  Theoretical Computer Science 845 (2020) 38–49.