# A First Look at Cepheids in a SN Ia Host with JWST

Wenlong Yuan Department of Physics & Astronomy, Johns Hopkins University,
Baltimore, MD 21218, USA  Adam G. Riess Department of Physics & Astronomy,
Johns Hopkins University, Baltimore, MD 21218, USA  Space Telescope Science
Institute, 3700 San Martin Drive, Baltimore, MD 21218, USA  Stefano Casertano
Space Telescope Science Institute, 3700 San Martin Drive, Baltimore, MD 21218,
USA  Lucas M. Macri George P. and Cynthia W. Mitchell Institute for
Fundamental Physics and Astronomy,
Department of Physics and Astronomy, Texas A&M University, College Station, TX
77843, USA

###### Abstract

We report the first look at extragalactic Cepheid variables with the James
Webb Space Telescope, obtained from a serendipitous (to this purpose)
observation of NGC 1365, host of an SN Ia (SN 2012fr), a calibration path used
to measure the Hubble constant. As expected, the high-resolution observations
with NIRCam through F200W show better source separation from line-of-sight
companions than HST images at similar near-infrared wavelengths, the spectral
region that has been used to mitigate the impact of host dust on distance
measurements. Using the standard star P330E as a zeropoint and PSF reference,
we photometered 31 previously-known Cepheids in the JWST field, spanning
$1.15<\log P<1.75$ including 24 Cepheids in the longer period interval of
$1.35<\log P<1.75$. We compared the resultant Period-Luminosity relations to
that of 49 Cepheids in the full period range including 38 in the longer period
range observed with WFC3/IR on HST and transformed to the JWST photometric
system (F200W, Vega). The P-L relations measured with the two space telescopes
are in good agreement, with intercepts (at $\log P=1$) of 25.74 $\pm$0.04 and
25.72 $\pm$0.05 for HST and JWST, respectively. Our baseline result comes from
the longer period range where the Cepheids have higher signal-to-noise ratios
where we find 25.75$\pm 0.05$ and 25.75$\pm 0.06$ mag for HST and JWST,
respectively. We find good consistency between this first JWST measurement and
HST, and no evidence that HST Cepheid photometry is “biased bright” at the
$\sim 0.2$ mag level that would be needed to mitigate the Hubble Tension,
though comparisons from more SN hosts are warranted and anticipated. We expect
future JWST observations to surpass these in quality as they will be optimized
for measuring Cepheids.

##  1 Introduction

Cepheid variables have held a central role in measuring extragalactic
distances for more than a century (Leavitt & Pickering, 1912). They exhibit
several features which make them uniquely suited for this role. Their nature
is well understood as a consequence of the $\kappa$ mechanism, which drives a
periodic overshooting of hydrostatic equilibrium and produces their pulsations
(Eddington, 1927). Their great luminosities, $\sim 10^{5}L_{\odot}$, make them
visible with modern telescopes at many tens of Megaparsecs. The large
amplitude of their variations uniquely identifies them and their periods
standardize their luminosities to a precision of a few percent. They are
ubiquitous in areas of recent star formation, including many hosts of Type Ia
supernovae (which have still greater range). Lastly, hundreds of Cepheids in
the Milky Way are in range of precise parallaxes from the ESA Gaia satellite
to provide a 1% geometric calibration of their fiducial luminosity (Riess et
al., 2022a; Cruz Reyes & Anderson, 2022). For these reasons, Cepheids are the
primary distance indicator most often selected for measuring long-range
distances and the Hubble constant (Riess et al., 2022b, hereafter, R22).

A succession of technological advancements has extended the reach, precision
and accuracy of Cepheid distance estimates at tens of Megaparsecs. One of the
original goals of the Hubble Space Telescope (HST) was to resolve
extragalactic Cepheids, which was achieved in dozens of galaxies within $\sim$
20 Mpc with the Wide Field Planetary Camera 2 (WFPC2) at optical wavelengths
(Freedman et al., 2001; Sandage et al., 2006). HST instruments with greater
sensitivity and higher resolution, ACS and WFC3/UVIS, extended this reach to
$\sim 50$ Mpc and a greater number of nearby SNe Ia and geometric calibrators
(Macri et al., 2006; Riess et al., 2011; Hoffmann et al., 2016).

Given that Cepheids are found in regions of recent star formation, they are
observed through interstellar dust with a mean reddening (in modestly-inclined
spirals, R22) of $E(V-I)\sim 0.3$ mag. Thus, their visible- (0.5$\micron$) and
infrared- (0.8$\micron$) band measurements must account for a mean of $\sim
0.7$ mag and $\sim 0.4$ mag of extinction, respectively, to provide accurate
distance measurements, which in consequence are sensitive to the uncertain
nature of extragalactic reddening laws.

Wide-scale follow-up of Cepheids in the near-infrared (NIR), to mitigate dust
effects, first became practical with WFC3/IR, allowing measurements at
$1.6\micron$ and reducing the mean impact of extinction to $\sim$ 0.1 mag and
the sensitivity to reddening laws (Riess et al., 2011). However, the advantage
of NIR observations over optical bands came with new challenges; at these
wavelengths, the resolution of HST is 2-3 times lower and the background (in
the form of ubiquitous red giants) is an order of magnitude greater. The
result is an increase in the measurement errors (after statistical removal of
the backgrounds measured using artificial stars) which may limit the precision
of distance measurements without a large number ($>$50) of Cepheids in each
host. While Cepheid distance measurements from either the optical or NIR are
in good agreement (R22), a result most likely if both are accurate, the
pursuit of a 1% measurement of the Hubble constant demands ever more stringent
tests of Cepheid photometry.

The newly-launched James Webb Space Telescope (JWST) offers the twin
advantages of angular resolution comparable to WFC3/UVIS at visible
wavelengths and the lower impact of interstellar dust as WFC3/IR in the same
observation. JWST observations planned for its first GO cycle have been
designed to take advantage of these capabilities and reobserve Cepheids
previously measured with HST, work which is likely to require years to collect
and thoroughly analyze to fully come to fruition. However, an early
observation with JWST of a SN Ia host previously observed by HST offers a
serendipitous (for this endeavor) and valuable preview.

To be clear in setting expectations for future JWST observations, these
serendipitous observations of the Cepheids in NGC 1365 fall short of
demonstrating the full capability of the observatory for this endeavor. They
are shorter in exposure time by a factor of a few than those planned for this
purpose and they are obtained at nearly twice the wavelength needed to
optimally resolve and reduce the contributions of nearby red giants (i.e., the
background). Notably, they cover a more crowded region along a spiral arm (see
Figure 1) compared to most of those observed by HST. Further, they provide
only a single (i.e., “random”) epoch or phase in each Cepheid light curve,
which adds an additional dispersion of $0.1$ to $0.2$ mag depending on the
amplitude of the Cepheid. Lastly, the state of the JWST calibration data
(e.g., flat fields, dark frames, bias frames, geometric distortion maps,
linearity corrections) is in its first iteration and will improve with time.
Nevertheless, and with these limitations in mind, these observations preview
the enhanced capabilities of JWST over HST and provide meaningful, if
preliminary, quantitative results.

In §2 we describe the details of the JWST observations for NGC 1365, as well
as the data reduction and photometry procedures. We show our results in §3 and
a brief discussion in §4. An appendix provides information about past HST
observations of Cepheids in NGC 1365 for easy reference.

##  2 Observations, data reduction, and photometry

###  2.1 Observations & data reduction

The central region of NGC 1365 was recently observed with JWST NIRCam on 2022
August 13 as part of program GO-2107 (PI: Janice Lee), which aims to study the
star formation activity in 19 nearby galaxies. The NGC 1365 field partially
overlaps with an HST WFPC2 time-series field (GO-5972, PI: Jeremy Mould) where
dozens of Cepheids were discovered (Silbermann et al., 1999; Hoffmann et al.,
2016) and followed up in the NIR (R22). With the Cepheid locations and periods
determined from those HST data, we have an opportunity to photometer and study
these Cepheids in the new JWST observations. In Figure 1 we show the
footprints of the JWST observations as well as archival HST observations and
locations of previously-identified Cepheids. The initial WFPC2 time-series and
WFC3 follow-up targeted a less crowded part of the host off the spiral arms,
but the NIRCam observations targeted the center of the galaxy and primarily
contain Cepheids in a small dense, crowded region. Appendix Figure 4 shows
less-crowded Cepheids imaged by HST that are more similar to those typically
studied in HST fields. Due to the overlap of the two observatories, we can
also directly compare the images and measurements of many of the same Cepheids
in the denser regions of the host.

Figure 1: Observation footprints of NGC 1365 with JWST NIRCam (magenta), HST
WFPC2 (cyan), WFC3/UVIS (green), and WFC3/IR (red) overlaid on a color
composite image from the Dark Energy Survey (DOE/FNAL/DECam/
CTIO/NOIRLab/NSF/AURA). The locations of Cepheids used in this study are
indicated by circles. North is up and east is to the left.

We retrieved JWST observations of NGC 1365 from MAST and processed the raw
data (stage 0) using the JWST Science Calibration Pipeline version 1.6.2.
There are 25 exposures in total, with the short-wavelength channel through the
F200W filter and the long-wavelength channel through the F300M, F335M, and
F360M filters. In this study, we only analyzed the F200W data for their depth
and proximity in wavelength coverage compared to the HST F160W band. The F200W
data consist of eight subfields, with each one covered by approximately one
short-wavelength detector. Only the two east-most subfields contain
previously-identified Cepheids; thus, we excluded the other six from the
analysis. The total exposure times are 1202.52s for both analyzed subfields.

We noticed the 1/f noise causing small bias shifts in the calibrated stage 2
data products (see §2 of Merlin et al., 2022). We corrected them by
subtracting the median value of each row and then each column before the JWST
pipeline stage 3 process. Similar to Merlin et al. (2022), we masked all
sources when computing the median values for row and column subtractions.

We used the WCS in the images to locate the Cepheids based on their HST
positions. We identified a global shift of $\sim 0\farcs 5$ between the HST
and JWST positions and accounted for this to register the images. After this
global shift we found point sources at the expected positions of the Cepheids
to a precision of less than a NIRCam pixel ($0\farcs 031$; see Figure 2). The
HST NIR observations in these spiral arms are under-sampled (even after
drizzling to $0\farcs 08/$pixel resolution) and lack the inherent resolution
of JWST (despite the greater wavelength of those observations).

While the Cepheids were easily apparent in the deeper and higher-resolution
images in F200W, they were hard to discern in the accompanying observations at
longer-wavelengths and through medium-width bands due to their much shorter
exposure times, lower angular resolution and lower throughput of these
filters. As a result we only analyzed the F200W images.

Figure 2: Image cuts of 5 example Cepheids analyzed in this study. Their
locations are indicated by the corresponding colors in Figure 1. The circles
cover a radius of 0$\farcs$375 while the image cuts display 3″ in a side. From
left to right, each row shows one (same) Cepheid in HST F555W, F814W, F160W,
and JWST F200W, where the exposure times are 1410s, 1770s, 3618s, and 1203s,
respectively. The orientation of the image cuts is indicated by the white
compass in the top-left panel.

###  2.2 Photometry

We performed point-spread function (PSF) photometry using a crowded-field
photometry package based on DAOPHOT/ALLSTAR Stetson (1987, 1994). We
constructed an empirical model of the PSF using F200W observations of the
standard star P330E (taken on 2022 Aug 29, obs. ID=jw01538o155t002) obtained
in a 160-pixel subarray (using a minimal exposure time to keep the star below
saturation) which included two dithers placed on each of the B-module chips.

We chose not to use the pipeline calibration to obtain the image zeropoints as
they have been found to have limited accuracy (at the time of this writing)
including chip-to-chip offsets (and possible time-dependence between the early
life of the mission and the present, Brammer, 2022; Boyer et al., 2022;
Nardiello et al., 2022). To produce reliable zeropoints for the observation of
NGC 1365 we used the above observations of P330E obtained and combined for
each B-module chip separately to directly calibrate the Cepheids observed in
that chip. We assigned each image of P330E a reference Vega magnitude of 11.42
mag (Rieke et al., 2022). An important advantage of using the Aug 29, 2022
observations of P330E to set the zeropoints for the images of NGC 1365 is that
they were obtained only 2 weeks after the observation of NGC 1365, an interval
during which JWST’s wave front monitoring has shown it to be relatively stable
with modeled photometric variations over the interval of $<$ 0.01 mag (M.
Perrin, 2022 private communication). (We did not make use of aperture
photometry for the Cepheids due to the inability to separate nearby sources as
expected from inspection of Figure 2.)

To avoid a flux bias from the determination of Cepheid positions in HST NIR
images, it is necessary to fix their locations using the uncrowded optical
images (i.e., “forced photometry”, Riess et al., 2009). The algorithm fits the
PSF of the Cepheids at their known, fixed positions, subtracts them from the
images, identifies additional, unresolved sources down to a fixed threshold,
and then simultaneously optimizes the fit to the non-Cepheids (parameters are
x, y and flux) and Cepheids (parameter is flux) to determine the latter’s
flux. We then add “artificial stars” at the same brightness as the Cepheid
(based on the period and iterative fit of the Period-Luminosity relation), and
remeasure these using the same procedure to account for the mean background of
unresolved sources near the position of the Cepheid (i.e., a statistical
crowding correction) and to measure the uncertainty in the Cepheid magnitude.
We also compared our results to the level 3, full-calibrated images produced
by the STScI pipeline and found that the photometry was consistent between the
versions of the images.

Figure 3: Near-infrared Period-Luminosity relations for Cepheids in the range
$1.35<\log P<1.75$ (baseline results) measured with HST and JWST. The JWST
sample (red) includes 24 Cepheids observed in F200W ($2\micron$). The HST
sample includes 38 Cepheids from R22 with F160W magnitudes transformed to
F200W using a color transformation based on their measured $V-I$ colors and
F160W$-$F200W. The inset shows the intercepts of the relations at $\log P=1$.
The solid red curve uses the JWST PSF photometry calibrated to P330E.

##  3 Results

Fixing the slope of the Period-Luminosity relation to the global value of
$-3.30$ determined from the mean of thousands of Cepheids in the MW, LMC, SMC,
M31, NGC 4258 and SN Ia hosts in the NIR (R22), we measured the intercepts at
$\log P=1$.

For our “baseline”, we limited the comparison to a period range of $1.35<\log
P<1.75$ where the Cepheids as measured from both telescopes have strong
signal-to-noise ratios. Below this range the SNR at $F160W=24.5$ (Vega) drops
to $<$10 and above this range Cepheid periods in NGC 1365 are not expected to
be accurate because the original time-series used to find the Cepheids in NGC
1365 spanned only 48 days ($\log P=1.68$), so that a full cycle would not have
been seen. The JWST and HST Cepheid Period-Luminosity relations are shown in
Figure 3.

For JWST with PSF fitting (referenced to P330E) and with 24 Cepheids we find
an intercept of 25.75$\pm 0.06$ (SD=0.36 mag). In Table 2 we provide
intercepts for broader ranges of periods and with and without $\sigma$
clipping.

To directly compare the HST and JWST Period-Luminosity relations observed at
different, though adjacent, bandpasses, it is necessary to account for their
different wavelength responses. Due to the simple spectral energy
distributions of stars, particularly on the Rayleigh-Jeans tail in the NIR, it
is relatively straightforward to estimate this difference, which is the color
F160W$-$F200W, from another measured color such as F555W$-$F814W. To do this
rigorously we used the PARSEC isochrones (Bressan et al., 2012) for stellar
atmospheres which are provided as calculated for the HST and JWST bandpasses
(using version CMD v3.6, http://stev.oapd.inaf.it/cgi-bin/cmd). We limited
these to a range appropriate for Cepheids: ages of 10 to 100 Myr, $T_{\rm
eff}$ of 4000 to 7000 degrees, initial masses $>2M_{\odot}$, and $\log g<$ 2\.
These stars have a tight locus in the color-color plane of WFC3/UVIS for
F555W$-$F814W vs F160W (HST)$-$F200W (JWST). We fit a second-order polynomial
to the color-color relation, finding

$\displaystyle{\it F160W}-{\it F200W}=0.007$ $\displaystyle+0.053({\it
F555W}-{\it F814W})$ $\displaystyle+0.077({\it F555W}-{\it F814W})^{2}$

Table 1: JWST F200W Cepheid Photometry

ID | $P$ |  F200W a | $\sigma^{b}$ | R.A.c | Decl. | subfield
---|---|---|---|---|---|---
| [days] | [mag] | [deg] (J2000.0) |
97917 | 24.00 | 24.64 | 0.32 | 53.433156 | -36.158061 | south
60205 | 25.30 | 24.44 | 0.36 | 53.435680 | -36.144208 | south
25668 | 26.13 | 24.38 | 0.51 | 53.432499 | -36.136873 | north
74699 | 26.58 | 24.67 | 0.46 | 53.427052 | -36.156193 | south
40364 | 27.48 | 23.90 | 0.39 | 53.429580 | -36.143996 | south
65664 | 29.34 | 24.74 | 0.35 | 53.431935 | -36.149101 | south
53380 | 30.85 | 24.32 | 0.40 | 53.433946 | -36.143847 | south
100027 | 31.37 | 24.34 | 0.21 | 53.439120 | -36.153423 | south
79315 | 31.46 | 24.15 | 0.31 | 53.432884 | -36.152400 | south
80300 | 32.38 | 24.44 | 0.32 | 53.434414 | -36.151327 | south
94995 | 32.42 | 23.87 | 0.31 | 53.431335 | -36.158716 | south
45761 | 33.03 | 24.45 | 0.44 | 53.430433 | -36.144804 | south
73421 | 33.50 | 23.60 | 0.33 | 53.427504 | -36.155372 | south
61628 | 37.01 | 23.25 | 0.28 | 53.427674 | -36.151793 | south
17203 | 38.12 | 24.24 | 0.43 | 53.430027 | -36.136683 | north
90510 | 39.06 | 23.65 | 0.24 | 53.433311 | -36.155466 | south
77265 | 39.61 | 24.24 | 0.27 | 53.429382 | -36.154908 | south
58983 | 39.67 | 24.32 | 0.29 | 53.427627 | -36.151066 | south
101731 | 47.24 | 22.96 | 0.19 | 53.437542 | -36.155483 | south
8616 | 48.09 | 22.85 | 0.33 | 53.427309 | -36.136727 | north
9712 | 48.33 | 23.41 | 0.29 | 53.426932 | -36.137379 | north
93422 | 51.34 | 23.38 | 0.23 | 53.431778 | -36.157790 | south
94055 | 51.45 | 23.56 | 0.18 | 53.435355 | -36.154809 | south
17544 | 51.94 | 23.56 | 0.24 | 53.430280 | -36.136566 | north

Note. — $a$: These are Vega mag referenced to P330E = 11.42 in F200W. $b$: The
errors are derived from artificial stars and also include a random phase error
in quadrature of 0.15 mag. $c$: Positions are referenced to the WCS of JWST
images processed using JWST pipeline v1.6.2.

Table 2: HST and JWST Intercepts at $\log P=1$ (slope=$-3.30$) for NIR
Cepheids in NGC 1365

Sample |  $N$ Cepheids | Period range |  F200W Intercepta
---|---|---|---
HST WFC3/IR field, baseline | 38 | 1.35 $<\boldsymbol{\log}~{}\boldsymbol{P}<$ 1.75 | 25.754 $\boldsymbol{\pm}\boldsymbol{0.045}$
HST WFC3/IR field, extended | 49 | 1.15 $<\log P<$ 1.75 | 25.736 $\pm 0.043$
HST WFC3/IR field, SH0ES R22b | 46 | 15.0 $<P<$ 50.0 | 25.750 $\pm 0.045$
JWST NIRCam field, baseline, PSF | 24 | 1.35 $<\boldsymbol{\log}~{}\boldsymbol{P}<$ 1.75 | 25.752 $\boldsymbol{\pm}\boldsymbol{0.059}$
JWST NIRCam field, extended, PSF | 31 | 1.15 $<\log P<$ 1.75 | 25.718 $\pm 0.055$

Note. — $a$: Results from HST measured in F160W and converted to F200W using
${\it F160W}-{\it F200W}=0.007+0.053({\it F555W}-{\it F814W})+0.077({\it
F555W}-{\it F814W})^{2}$. $b$: Same period range and sample used in R22.

The dispersion of the synthetic values around this approximation is 0.007 mag.
The mean Cepheid color of the sample is ${\it F555W}-{\it F814W}=1.08$ mag
(sample SD=0.22 mag) where the relation gives ${\it F160W}-{\it F200W}$=0.15
mag (sample SD=0.05 mag), however we computed the individual values for each
Cepheid, as given in the Appendix. We subtract the individual F160W$-$F200W
colors predicted from the optical colors from the measured HST F160W to
provide a direct comparison to JWST F200W as shown in Figure 3.

The baseline measurements of the HST intercepts use the F160W magnitudes as
given in R22, the F160W$-$F200W colors as given in the Appendix, and include
38 Cepheids in this period range. To increase the sample for the purpose of
this HST to JWST comparison, we added 3 Cepheids with $P=51,51,$ and 52 days
found by Hoffmann et al. (2016) and only slightly above the $P<50$ day limit
used by R22 but still well below the $1.2\times$ time-span of the observations
necessary to be reliable. We find an intercept for HST at $\log P=1$ of
25.75$\pm 0.05$ mag and provide intercepts with other period ranges in Table
2.

The inset in Figure 3 compares the intercepts. The agreement between the HST
and JWST intercepts is very good, below 1$\sigma$ in their difference. The
same mean difference is seen when comparing only identical Cepheids though the
number of Cepheids measured by both is far smaller and thus the comparison is
less significant. The dispersion around the Period-Luminosity relation as
shown in Figure 3 is comparable between HST and JWST and is likely to be
smaller for optimal JWST observations with multiple epochs, better image
calibration and in less crowded regions more typically observed with HST.

To a $\sim$0.05 mag level of preliminary accuracy based on still limited
characterization of JWST and for this case we can conclude that past HST NIR
measurements do not appear biased, let alone “biased bright” at the $\sim$0.2
mag level (i.e., by the systematics of past photometry measurements or by
previously unresolved companions) as could mitigate the “Hubble Tension” in
R22 (and then only if such a bias was not also similarly present in HST
photometry of Cepheids in the geometric anchor, NGC 4258).

##  4 Discussion

The JWST images and measurements of Cepheids in NGC 1365 and in comparison to
those from HST bode well for the quality of such future measurements. We
reiterate that these observations were not optimized for observing Cepheids
and are far from the best that JWST can do. Optimal observations would be
longer in exposure time, cover multiple passbands to the necessary depth,
include shorter wavelengths for better resolution, include multiple epochs to
reduce the random phase noise, have higher signal-to-noise calibration frames
(flats, darks, bias frames, chip offsets, geometric distortion for locating
Cepheids, etc) available and better cover the regions where past HST programs
have found Cepheids and measured their periods.

We also note that it is too early in the life of JWST and NIRCam to identify
and calibrate subtle photometric effects. There is one such effect we are
aware of, the count-rate non-linearity (CRNL), which makes faint objects
appear fainter, though the scale of this effect has been diminishing with
improvements in NIR detector manufacturing and testing used to select the best
chips. Because the level of CRNL has not yet been measured in space for
NIRCam, we did not correct either the NIRCam or the WFC3/IR Cepheid photometry
for this effect, so to first approximation we might expect that CRNL cancels
in the comparisons provided here. For WFC3/IR, CRNL makes the Cepheids in NGC
1365 $\sim 0.03$ mag faint relative to the flux level of standard stars (Riess
et al., 2009). If the CRNL of NIRCam is $\sim$ half the level of WFC3/IR (our
guess), the error in the comparison will be $\sim 0.015$ mag, negligible at
the precision of this study, but important to calibrate for future, larger
samples. The single-epoch sampling of this JWST observation introduces a
statistical bias of $\sim 0.005$ mag in the Cepheid Period-Luminosity relation
compared to the typical flux-averaged (multi-epoch) observations. This bias is
again negligible for the precision of this study.

Nevertheless, the quantitative comparison of the first JWST Cepheid Period-
Luminosity intercepts presented here is promising, and already significant as
a check on past HST measurements. We expect that the calibration of this
observatory will only improve and mature, leading to future observations that
should provide ever more definitive investigations.

We are indebted to all of those who spent years and even decades bringing JWST
to fruition. We are grateful to the proposers of GO-2107 (PI: Janice Lee) for
making their program non-proprietary, enabling the community to undertake
assorted investigations from this data including this study. This research
made use of the NASA’s Astrophysics Data System.

## References

  * Boyer et al. (2022) Boyer, M. L., Anderson, J., Gennaro, M., et al. 2022, arXiv e-prints, arXiv:2209.03348.  https://arxiv.org/abs/2209.03348
  * Brammer (2022) Brammer, G. 2022, grizli, 1.5.0, doi: 10.5281/zenodo.5012699
  * Bressan et al. (2012) Bressan, A., Marigo, P., Girardi, L., et al. 2012, MNRAS, 427, 127, doi: 10.1111/j.1365-2966.2012.21948.x
  * Cruz Reyes & Anderson (2022) Cruz Reyes, M., & Anderson, R. I. 2022, arXiv e-prints, arXiv:2208.09403.  https://arxiv.org/abs/2208.09403
  * Eddington (1927) Eddington, A. S. 1927, MNRAS, 87, 539, doi: 10.1093/mnras/87.7.539
  * Freedman et al. (2001) Freedman, W. L., Madore, B. F., Gibson, B. K., et al. 2001, ApJ, 553, 47, doi: 10.1086/320638
  * Hoffmann et al. (2016) Hoffmann, S. L., Macri, L. M., Riess, A. G., et al. 2016, ApJ, 830, 10, doi: 10.3847/0004-637X/830/1/10
  * Leavitt & Pickering (1912) Leavitt, H. S., & Pickering, E. C. 1912, Harvard College Observatory Circular, 173, 1
  * Macri et al. (2006) Macri, L. M., Stanek, K. Z., Bersier, D., Greenhill, L. J., & Reid, M. J. 2006, ApJ, 652, 1133, doi: 10.1086/508530
  * Merlin et al. (2022) Merlin, E., Bonchi, A., Paris, D., et al. 2022, arXiv e-prints, arXiv:2207.11701.  https://arxiv.org/abs/2207.11701
  * Nardiello et al. (2022) Nardiello, D., Bedin, L. R., Burgasser, A., et al. 2022, arXiv e-prints, arXiv:2209.06547.  https://arxiv.org/abs/2209.06547
  * Rieke et al. (2022) Rieke, G. H., Su, K., Sloan, G. C., & Schlawin, E. 2022, AJ, 163, 45, doi: 10.3847/1538-3881/ac3b5d
  * Riess et al. (2009) Riess, A. G., Macri, L., Casertano, S., et al. 2009, ApJ, 699, 539, doi: 10.1088/0004-637X/699/1/539
  * Riess et al. (2011) —. 2011, ApJ, 730, 119, doi: 10.1088/0004-637X/730/2/119
  * Riess et al. (2022a) Riess, A. G., Breuval, L., Yuan, W., et al. 2022a, arXiv e-prints, arXiv:2208.01045.  https://arxiv.org/abs/2208.01045
  * Riess et al. (2022b) Riess, A. G., Yuan, W., Macri, L. M., et al. 2022b, ApJ, 934, L7, doi: 10.3847/2041-8213/ac5c5b
  * Sandage et al. (2006) Sandage, A., Tammann, G. A., Saha, A., et al. 2006, ApJ, 653, 843, doi: 10.1086/508853
  * Silbermann et al. (1999) Silbermann, N. A., Harding, P., Ferrarese, L., et al. 1999, ApJ, 515, 1, doi: 10.1086/307002
  * Stetson (1987) Stetson, P. B. 1987, PASP, 99, 191, doi: 10.1086/131977
  * Stetson (1994) —. 1994, PASP, 106, 250, doi: 10.1086/133378

##  Appendix A Cepheid measurements from HST

Table 3: HST F160W Cepheid Photometry

ID | $P$ | F160W | $\sigma$ | F555W$-$ | F160W$-$ | R.A.a | Decl.
---|---|---|---|---|---|---|---
|  |  |  | F814W | F200W |  |
| [days] | [mag] | [deg] (J2000.0)
60205 | 25.16 | 25.03 | 0.54 | 1.18 | 0.18 | 53.435572 | -36.144146
136735 | 25.57 | 24.41 | 0.23 | 0.89 | 0.12 | 53.465135 | -36.152743
43927 | 25.57 | 24.98 | 0.50 | 1.17 | 0.17 | 53.440450 | -36.135135
101154 | 25.94 | 23.89 | 0.73 | 0.98 | 0.13 | 53.426225 | -36.165263
106082 | 26.38 | 24.40 | 0.68 | 0.84 | 0.11 | 53.432670 | -36.161386
74699 | 26.44 | 24.28 | 0.55 | 1.23 | 0.19 | 53.426941 | -36.156136
63449 | 26.81 | 24.39 | 0.40 | 1.35 | 0.22 | 53.445400 | -36.136227
138773 | 26.83 | 24.35 | 0.21 | 1.04 | 0.15 | 53.462525 | -36.157297
101112 | 26.88 | 24.37 | 0.63 | 0.98 | 0.13 | 53.426292 | -36.165183
120972 | 27.30 | 24.46 | 0.31 | 1.04 | 0.15 | 53.443078 | -36.160625
126914 | 27.33 | 24.78 | 0.30 | 0.80 | 0.10 | 53.455397 | -36.153646
40364 | 27.34 | 23.94 | 0.48 | 0.91 | 0.12 | 53.429471 | -36.143937
65336 | 27.79 | 24.71 | 0.38 | 0.89 | 0.12 | 53.446800 | -36.135500
124631 | 29.17 | 24.22 | 0.27 | 1.02 | 0.14 | 53.438970 | -36.166817
130859 | 29.21 | 24.56 | 0.24 | 0.98 | 0.13 | 53.458170 | -36.153817
133465 | 29.29 | 24.44 | 0.23 | 1.34 | 0.22 | 53.460423 | -36.154001
105797 | 30.17 | 23.98 | 0.47 | 1.28 | 0.20 | 53.431618 | -36.162206
106470 | 30.23 | 24.30 | 0.32 | 0.93 | 0.12 | 53.427648 | -36.166054
100027 | 31.20 | 24.11 | 0.29 | 0.66 | 0.08 | 53.439011 | -36.153369
73421 | 33.32 | 24.52 | 0.56 | 0.91 | 0.12 | 53.427399 | -36.155314
122163 | 33.91 | 24.20 | 0.19 | 1.23 | 0.19 | 53.449210 | -36.155957
139368 | 34.28 | 24.64 | 0.18 | 1.09 | 0.16 | 53.459369 | -36.160824
87703 | 34.92 | 23.51 | 0.24 | 1.22 | 0.19 | 53.449343 | -36.140061
117850 | 35.09 | 24.21 | 0.46 | 1.04 | 0.15 | 53.445830 | -36.156138
61628 | 36.80 | 23.79 | 0.52 | 1.63 | 0.30 | 53.427562 | -36.151741
103387 | 36.88 | 24.25 | 0.26 | 0.94 | 0.12 | 53.447790 | -36.146777
80315 | 36.90 | 23.12 | 0.27 | 1.20 | 0.18 | 53.449213 | -36.137887
142648 | 36.94 | 24.32 | 0.14 | 0.93 | 0.12 | 53.457318 | -36.166545
90510 | 38.84 | 23.92 | 0.42 | 1.05 | 0.15 | 53.433201 | -36.155411
128912 | 40.51 | 23.39 | 0.38 | 1.14 | 0.17 | 53.437587 | -36.170953
103704 | 40.63 | 24.24 | 0.28 | 1.43 | 0.24 | 53.440403 | -36.153516
104907 | 42.66 | 23.14 | 0.42 | 1.11 | 0.16 | 53.432245 | -36.161310
123489 | 42.77 | 23.96 | 0.23 | 0.95 | 0.13 | 53.431458 | -36.172785
109560 | 46.44 | 23.80 | 0.20 | 1.54 | 0.27 | 53.447707 | -36.149730
101731 | 46.99 | 23.31 | 0.43 | 0.90 | 0.12 | 53.437427 | -36.155425
93422 | 51.07 | 23.65 | 0.37 | 1.49 | 0.26 | 53.431666 | -36.157737
94055 | 51.17 | 24.00 | 0.29 | 1.35 | 0.22 | 53.435250 | -36.154750
134975 | 52.31 | 23.21 | 0.15 | 0.88 | 0.11 | 53.460099 | -36.155567

Note. — $a$: Positions are referenced to the WCS of HST F160W images processed
using AstroDrizzle v2.2.6.

Figure 4: Same as Figure 2 but for 5 examples in the more typical, lower-
density HST F160W field, where JWST observations are not available. See Figure
1 for location.


# Bounding the edge cover of a hypergraph

Farhad Shahrokhi
Department of Computer Science and Engineering, UNT
P.O.Box 13886, Denton, TX 76203-3886, USA<EMAIL_ADDRESS>
###### Abstract

Let $H=(V,E)$ be a hypergraph. Let $C\subseteq E$, then $C$ is an edge cover,
or a set cover, if $\cup_{e\in C}\\{v|v\in e\\}=V$. A subset of vertices $X$
is independent in $H,$ if no two vertices in $X$ are in any edge. Let $c(H)$
and $\alpha(H)$ denote the cardinalities of a smallest edge cover and largest
independent set in $H$, respectively. We show that $c(H)\leq{\hat{m}}(H)c(H)$,
where ${\hat{m}}(H)$ is a parameter called the mighty degeneracy of $H$.
Furthermore, we show that the inequality is tight and demonstrate the
applications in domination theory.

##  1 Introduction

We assume the reader is familiar with standard graph theory [5], hypergraph
theory [1], [3], domination theory [11], and algorithm analysis [6].
Throughout this paper we denote by $H=(V,E)$ a hypergraph on vertex set $V$
and the edge set $E$. So any $e\in E$ is a subset of $V$. We do not allow
multiple edges in our definition of a hypergraph, unless explicitly stated.
Every hypergraph can be represented by its incidence bipartite graph $B$ whose
vertex set is $V\cup E$. If $x\in V$ and $e\in E$, then $xe$ is an edge in
$B$, provide that $x\in e$. Let $C\subseteq E$, then $C$ is an edge cover, or
a set cover, if $\cup_{e\in C}\\{v|v\in e\\}=V$. A subset of vertices $X$ is
independent in $H$, if no two vertices in $X$ are in any edge. Let $c(H)$ and
$\alpha(H)$ denote the cardinalities of a largest independent set and a
smallest edge cover in $H$, respectively. It is known that computing
$\alpha(H)$ and $c(H)$ are NP hard problems [10]. Clearly,
$c(H)\geq\alpha(H)$. Furthermore, it is known that $c(H)$ can not bounded
above by a function of $\alpha(H)$, only. However, an important result in this
area is known. Specifically, it is a consequence of the result in [9] that

$c(H)={\alpha(H)}^{O(2^{v})}$ (1)

where $v$ denotes the vc dimension of $H$ [16]. Design of approximation
algorithms for the edge cover problem has been an active and ongoing research
in computer science. A greedy algorithm [7], [13] is known to approximate
$c(H)$ within $O(log(n)$ from its optimal value. Moreover, there are examples
of hypergraphs that show the worst case approximation scenario of $O(log(n))$
can not be improved [4].

The main result of this paper is to show that

$c(H)\leq{\hat{m}}(H)\alpha(H)$ (2)

where the multiplicative factor ${\hat{m}}(H)$ is a parameter called the
mighty degeneracy  of $H$ which we introduce here. Recall that a set
$S\subseteq V$ is a transversal set (hitting set) in the hypergraph $H=(V,E)$,
if every $e\in E$ has a vertex in $S$. A set $M\subseteq E$ is a matching in
$H$, if every two edges in $M$ are disjoint. Let $\tau(H)$ and $\rho(H)$
denote the sizes of a smallest transversal and a largest matching in $H$,
respectively, and note that $\tau(H)\geq\rho(H)$.

A direct consequence of (2) is that

$\tau(H)\leq{\hat{m}}(H^{d})\rho(H)$ (3)

where ${\hat{m}}(H^{d})$ is the mighty degeneracy of the dual hypergraph of
$H$, defined as $H^{d}=\\{E,V\\}$.

This paper is organized as follows. In Section Two we introduce some terms and
concepts and set up our notations. Particularly, we introduce the strong
degeneracy of a hypergraph, denoted by ${\hat{s}}(H)$, which is an upper bound
on ${\hat{m}}(H)$. In Section Three we derive (2) which is the main result,
and also present a linear time algorithm for computing ${\hat{s}}(H)$. Section
Four contains the applications to domination theory of graphs. Specifically,
we show ${\hat{s}}(H)=1$ (and hence ${\hat{m}}(H)=1$), when the underlying
graph $G$ is a tree and $H$ is the so called closed or open neighborhood
hypergraph of $G$. Consequently, we provide new proofs (and algorithms) for
two classical results in domination theory [14], [15], by showing that in any
tree the size of a smallest dominating (total domination) set equals to the
size of a largest 2- packing (open 2-packing). The results in Section Four are
conveniently derived utilizing concept of strong degeneracy, instead of mighty
degeneracy, however generally speaking, the former can be much large than the
latter. In Section Five we give examples of hypergraphs with bounded mighty
degeneracy, whose strong degeneracy is a linear function of number of
vertices. Section Six contains our suggestions for future research.

##  2 Preliminaries

Let $H=(V,E)$, let $S\subseteq V$ and $e\in E$, then $e\cap S$ is the trace of
$e$ on $S$. The restriction of $H$ to $S$, denoted by $H[S]$, is the
hypergraph on vertex set $S$ whose edges are the set of all distinct traces of
edges in $E$ on $S$. $H[S]$ is also referred to as the induced subhypergraph
of $H$ on $S$. In general, a hypergraph $I$ is a subhypergraph of $H$, if it
can be obtained by removing some vertices and some edges from $H$111When a
vertex set is removed from $H$, the edges of $H$ will also be updated
accordingly.. $S$ is shattered in $H$, if any $X\subseteq S$ is a trace. Thus
if $S$ is shattered, then it has $2^{|S|}$ traces. The Vapnik–Chervonenkis
(VC) dimension of a hypergraph $H$, denoted by $vc(H)$, is the cardinality of
the largest subset of $V$ which is shattered in $H$. Let $H=(V,E)$ and let
$x\in V$. The degree of $x$ denoted by $d_{H}(x)$ is the number of edges that
contain $x$. The strong degree of $x$ in $H$, denoted by $s_{H}(x)$, is the
number of distinct maximal edges that contain $x$. ( An edge is maximal, if it
is not properly contained in another edge.) Let $\delta(H)$ and $s(H)$ denote
the smallest degree and smallest strong degree, respectively, of any vertex in
$H$. The degeneracy and strong degeneracy of $H$, denoted by
${\hat{\delta}}(H)$ and ${\hat{s}}(H)$, respectively, are the largest minimum
degree and largest minimum strong degree of any induced subhypergraph of $H$.
Let $R\subseteq S$. A strong subset of $V$ in $H$ is a non empty subset of $V$
which is obtained by removing all vertices in $R$ from $H$, as well as all
vertices in the edges that have nonempty intersection with $R$ and all
vertices in such edges.

The mighty degeneracy of $H$, denoted by ${\hat{m}}(H)$, is the largest
minimum strong degree of any strong subhypergraph of $H$. Clearly, for any
$x\in V$ one has ${s}_{H}(x)\leq{d}_{H}(x)$ and consequently

${\hat{m}}(H)\leq{\hat{s}}(H)\leq{\hat{\delta}}(H)$ (4)

##  3 Our Greedy Algorithms

Our next result is the main result of this paper.

######  Theorem 3.1.

Let $H=(V,E)$ be a hypergraph, then there is an an edge cover $C$, and an
independent set $X$ in $H$ so that

$|C|\leq{\hat{m}}(H)|X|$ (5)

Consequently

$|C|\leq{\hat{s}}(H)|X|$ (6)

Moreover, $X$ and and $C$ can be constructed in $O(|V|+\sum_{e\in E}|e|)$
time.

Proof. Consider the following algorithm.

Initially, set $i\leftarrow 1$, $I\leftarrow H,W\leftarrow V$ and $K\leftarrow
E$. While there are vertices in $W$ repeat the following steps: Remove the
vertex of minimum strong degree, denoted by $x_{i}$, from $W$, remove the set
of all distinct maximal edges containing $x_{i}$ from $K$, then, remove and
the set of all vertices contained in theses edges from $W$ and finally set
$i\leftarrow i+1$.

Clearly, the algorithm terminates. Now let $t$ be the number iterations of the
algorithm and at any iteration $i=1,2,...,t$, let $I_{i}$ denote the
constructed hypergraph, (which is strongly induced), and let $W_{i}$ (which is
a strong subset) and $K_{i}$ denote, respectively, the vertices and edges of
this hypergraph. Let $X=\\{x_{1},x_{2},...,x_{t}\\}$ be the set of all
vertices removed from $H$ when the algorithm terminates. Clearly, $X$ is an
independent set in $H$. We denote by $K_{x_{i}}$ the set of all distinct
maximal edges containing the vertex $x_{i}$ in the hypergraph $I_{i}$ at
iteration of $i$ of the algorithm and note that $|K_{x_{i}}|\leq{\hat{m}}(H)$,
since $x_{i}$ is the vertex of minimum strong degree in $I_{i}$. Consequently,

$\sum_{i=1}^{t}|K_{x_{i}}|\leq{\hat{m}}(H)\times t={\hat{m}}(H)\times|X|$ (7)

Now for $i=1,2,...,t$, let $C_{x_{i}}$ be the set of all edges in $H$ obtained
by extending each edge of $K_{x_{i}}$ in $I_{i}$ to an edge in $H$ and let
$C=\cup_{i=1}^{t}C_{x_{i}}$. Clearly, $C$ is an edge cover and furthermore
$|C|=|\cup_{i=1}^{t}F_{x_{i}}|$, and therefore the first claim follows from
(7).

To verify the second inequality note that ${\hat{m}}(H)\leq{\hat{s}}(H)$. We
omit the details of claims regrading time complexity that involves
representing $H$ as a bipartite graph. $\Box$

To use Theorem 3.1 we really need to know ${\hat{m}}(H)$. Alternatively, we
can use ${\hat{s}}(H)$ which is an upper bound for ${\hat{m}}(H)$. At this
time, we still do not know how to efficiency compute ${\hat{m}}(H)$. We finish
this section by presenting a simple greedy algorithm for computing
${\hat{s}}(H)$ which is similar to the known algorithm for computing
degeneracy of $H$, or ${\hat{\delta}}(H)$. The properties of the output of
algorithm will be used to prove our results in the next section.

######  Theorem 3.2.

Let $H=(V,E)$ be a hypergraph on $n$ vertices, then ${\hat{s}}(H)$ can be
computed in $O(|V|+\sum_{e\in E}|e|)$ time.

Proof. Consider the following algorithm. For $i=1,.2,...,n$, select a vertex
$x_{i}$ of of minimum strong degree $s_{i}={s}(H_{i})$ in the induced
subhypergraph $H_{i}=H[V_{i}]$ whose vertex set is
$V_{i}=V-\\{x_{1},x_{2},...,x_{i-1}\\}$ and whose edge set is denoted by
$E_{i}$. Let $s=\max\\{s_{i},i=1,2,...,n\\}$. We claim that ${\hat{s}}(H)=s$.
Note that ${\hat{s}}(H)\geq s$. We will show that ${\hat{s}}(H)\leq s$. Now
let $I=(W,F)$ be an induced subhypergraph of $H$ whose minimum strong degree
equals ${\hat{s}}(H)$ and let $j,1\leq j\leq n,$ be the smallest integer so
that $x_{j}\in W$. Then $s_{I}(x_{j})\leq s_{j}={s}(H_{j})\leq s$, since
$W\subseteq E_{i}$ and and consequently the claim is proved. To verify the
claim for time complexity, one needs to represent $H$ as a bipartite graph $H$
as the input of algorithm. The details are omitted. $\Box$

##  4 Applications in domination theory

For a graph $G$ on vertex set $V$ and $x\in V$ let $N(x)$ denote the open
neighborhood of $x$, that is the set of all vertices adjacent to $x$, not
including $x$. The closed neighborhood of $x$ is $N[x]=N(x)\cup\\{x\\}$. The
closed (open) neighborhood hypergraph of an $n$ vertex graph $G$ is a
hypergraph on the same vertices as $G$ whose edges are all $n$ closed (open)
neighborhoods of $G$. A subset of vertices $S$ in $G$ is a dominating set
[11], if for every vertex $x$ in $G$, $N[x]\cap S\neq\emptyset$. $S$ is a
total or open domination set if, $N(x)\cap S\neq\emptyset$. $S$ is a 2-packing
(packing) , if for any distinct pair $x,y\in S$, $N[x]$ and $N[y]$ do not
intersect. $S$ is an open 2-packing(packing), if for any distinct pair $x,y\in
S$, $N(x)$ and $N(y])$ do not intersect Let
$\gamma(G),\gamma^{o}(G),\alpha_{2}(G)$ and $\alpha^{0}_{2}(G)$ denote the
sizes of a smallest dominating, a smallest open domination, a largest packing
and a largest open packing, respectively, in $G$. Computing
$\gamma(G),\gamma^{o}i(G),\alpha_{2}(G)$ and $\alpha^{o}_{2}(G)$ are known to
be NP-hard. $\gamma(G)$ can be approximated within a factor of $O(log(n))$
times form its optimal solution in $O(n+m)$ time, where $n$ and $m$ are the
number of vertices and edges of $G$. The approximation algorithm is arising
from the approximation algorithm for the set cover problem[13] [7]. It is
known that one can not improve the approximation factor of $O(log(n))$
asymptotically.

Let $G$ be a graph on vertex set $V$. The closed neighborhood hypergraph, of
$G$ is a hypergraph on vertex set $V$ and edge set $\\{N[x],x\in V\\}$. The
open neighborhood  hypergraph of graph $G$ is a hypergraph on the vertex set
$V$ and the edge set $\\{N(x),x\in V\\}$. The following summarizes basic
properties of neighborhood hypergraphs as they relate to our work.

######  Observation 4.1.

Let $H$ the closed neighborhood hypergraph of a graph $G$ with the vertex set
$V$.

  1. (i)

Let $S\subseteq V$, then $S$ is a dominating set in $G$ if and only if $S$ is
an edge cover in $H$.

  2. (ii)

Let $S\subseteq V$, then $S$ is a packing in $G$ if and if $S$ is an
independent set in $H$.

  3. (iii)

Let $x\in V$, then $s_{H}(x)\leq deg(x)+1$, where $deg(x)$ is degree of $x$ in
$G$. Consequently, ${\hat{s}}(H)\leq\Delta(G)+1$, where $\Delta(G)$ is the
maximum degree of $G$.

  4. (iv)

If $G$ is a tree and $x\in V$ is a leaf, then $s_{H}(x)=1$.

######  Remark 4.1.

Observation 4.1 is valid if $H$ is the open neighborhood hypergraph of $G$,
with the exception that in item $(iii)$, one has $s_{H}(x)\leq deg(x)$ and
consequently ${\hat{s}}(H)\leq\Delta(G)$.

By the above observation, if we apply the greedy algorithm in Theorem 3.1 to
the neighborhood hypergraph of a graph $G$, we obtain a dominating (total
domination) set $C$ and a packing (open packing) $X$ so that
$|C|\leq{\hat{s}}(H)|X|$. To determine how small is $C$, we need to estimate
${\hat{s}}(H)$, for the hypergraph $H$. As stated above, we only know
${\hat{s}(H)}\leq\Delta(G)+1$, where $\Delta(G)$ is the maximum degree of $G$.
For trees one can get a significantly better result.

Let $T$ be a tree and let $T_{1}$ be a tree which is obtained after removing
all leaves of $T$. Then each leaf in $T_{1}$ is a support vertex in $T$
(attached to a leaf) and is called a canonical support vertex in $T$.

Next we derive two classical results in domination theory that were proved
first proved in [14] and [15], respectively.

######  Theorem 4.1.

Let $T$ be a tree on the vertex set $V$ whose closed and open neighborhood
hypergraphs are $H$ and $H^{o}$, respectively. Then, the following hold.

  1. (i)

${\hat{s}}(H)={\hat{m}}(H)=1$ and consequently $\gamma(T)=\alpha_{2}(T)$.

  2. (ii)

${\hat{s}}(H^{o})={\hat{m}}(H^{o})=1$ and consequently
$\gamma^{0}(T)=\alpha^{o}_{2}(T)$.

Moreover, the domination and packing sets can be obtained in $O(V)$ time

Proof. We first verify that at each iteration of the greedy algorithm in
Theorem 3.2 a vertex of strong degree one is detected. This shows
${\hat{s}i}(H)=1$. We then apply the greedy algorithm in Theorem 3.1 to obtain
the equality of packing and domination numbers.

To prove the first the claim, note that algorithm in Theorem 3.2 can break the
ties arbitrary. So assume that the algorithm selects the leaves in $T$ which
as stated in 4.1 have strong degree one in $H$. Now Consider the execution of
algorithm on Tree $T_{1}$ which is obtained after removing all leaves of $T$.
If $T_{1}$ is empty we are done, since all vertices have already had degree
one. So assume $T_{1}$ is not empty.

Claim. Let $x$ be a leaf in $T_{1}$, then $s_{I}(x)=1$, where $I$ is the
closed induced neighborhood hypergraph which is obtained after removal of all
leaves of $T$.

Proof of claim. Since $x$ is leaf in $T_{1}$, there is exactly one vertex $z$
adjacent to $x$ in $T_{1}$. Now Let $Y\subset V$ be the set of leaves of $T$
adjacent to $x$ (in $T$) and $N_{I}[y]$ denote the closed neighborhood of
$y\in Y$ in $I$ after removal of $y$. Then, we have $N_{I}[y]=x$.
Additionally, note that $N_{I}[x]=\\{x,z\\}\subseteq N_{I}[z]$, since $x\in
N_{I}[z]$, and consequently $s_{I}(x)=1$.

Coming back to the proof, now let algorithm select leaves of $T_{1}$, then,
delete all these leaves and continue the process with the tree obtained after
removal of these leaves. This proves ${\hat{s}}(H)=1$, consequently
${\hat{m}}(H)=1$. Now run the algorithm in Theorem 3.1 on $T$ to prove
$\gamma(T)=\alpha_{2}(T)$.

Proof of second the claim is similar to the first and is omitted. The claim on
the time complexity follows from running times stated in Theorems 3.1, 3.2.
$\Box$

##  5 The gap between ${\hat{m}}(H)$ and ${\hat{s}}(H)$

In the proof of Theorem 4.1, we were able to effectively use ${\hat{s}}(H)$
instead of ${\hat{m}}(H)$. However, in general this may not be possible since
${\hat{s}}(H)$ can be much larger than ${\hat{m}}(H)$ as demonstrated in the
following.

######  Theorem 5.1.

For any integer $n\geq 3$ there is an $n$ vertex hypergraph such that
${\hat{m}}(H)=2$ and ${\hat{s}}(H)=n-2$.

Proof. Let $G$ be a graph on vertex set $V=\\{v_{1},v_{2},...,v_{n}\\}$
composed of a clique on vertex set $\\{v_{2},v_{3},...,v_{n}\\}$ so that
vertex $v_{1}$ (which is not in the clique) is adjacent to vertex $v_{2}$
(which is in the clique). Now define a hypergraph $H=(V,E)$ with
$E=N[v1]\cup_{i=2}^{n}N(v_{i})$. Note that

$s_{H}(v_{1})=2$ (8)

since $N[v_{1}]$ and $N(v_{2})$ are maximal edges of $H$ containing $v_{1}$.
It is also easy to verify that

$s_{H}(v_{2})=n-1\mbox{ and that }s_{H}(v_{i})=n-2\mbox{ for }i=3,4,...,n$ (9)

Next note that the only strong subset of $V$ in $H$ is $V$ itself and thus
equations 8 and 9 imply ${\hat{m}}(H)=s_{H}(v_{1})=2$ as claimed for mighty
degeneracy.

Now consider the induced hypergraph $I$ on vertex set $W=V-\\{v_{1}\\}$, whose
edges are obtained by removing $v_{1}$ from those edges of $H$ that contains
$v_{1}$ (these edges are $N[v_{1}]$ and $N(v_{2})$). One can verify that

$s_{I}(v_{i})=n-2\mbox{ for }i=2,3,...,n$ (10)

which implies ${\hat{s}}(H)=n-2$ as claimed. $\Box$

##  6 Future Work

This paper contains our preliminary results and we suggest several directions
for future research.
It is not known to us yet, if ${\hat{m}}(H)$ can be computed in polynomial
time or not. We suspect that a variation of the algorithm in Theorem 3.1 can
actually compute ${\hat{m}}(H)$, but have not been able to prove it.
The connections between the $vc(H)$ and ${\hat{m}}(H)$ (${\hat{s}}(H)$) needs
to be explored further. Is it true that one can always be bounded by a
function of the other?

The most recent results for approximation of $\gamma(G)$ (domination number of
a graph $G$) in sparse graphs require solving the linear programming
relaxations (fractional versions) of the problem and then rounding the
solutions [2],[8]. For a recent survey see [12]. We suspect that proper
modification of our method in Section Four would give similar results without
the need to actually solve the linear programming problems.

## References

  * [1] Berge C.: Theory of Graphs and its Applications. Methuen, London (1962).
  * [2] Bansal, Umboh S. W.: Tight approximation bounds for dominating set on graphs of bounded arboricity. Information Processing Letters. (2017), 21-24.
  * [3] Bousquet N.: Hitting sets: VC-dimension and Multicuts. Université Montpellier II-Sciences et Techniques du Languedoc (2013).
  * [4] Brönnimann H., Goodrich M.T.: Almost Optimal Set Covers in Finite VC-Dimension. Discret. Comput. Geom. 1995, 14, 463–479.
  * [5] Chartrand G., Lesniak L., Zhang P.: Graphs and Digraphs; CRC Press: Boca Raton, FL, USA, 2010.
  * [6] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, MIT Press: Cambridge.
  * [7] Chvatal V.: A greedy heuristic for the set-covering problem, Mathematics of Operations Research, 4(3):233-235, 1979.
  * [8] Dvorak Z. On distance r-dominating and 2r-independent sets in sparse graphs. J. Graph Theory 2017.
  * [9] Ding G.L., Seymour P., Winkler P.: Bounding the vertex cover number of a hypergraph, Combinatorica volume 14, pages 23–34 (1994).
  * [10] Garey M.R., Johnson D.J.: Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1978.
  * [11] Haynes T. W., Hedetniemi S., Slater P.: Fundamentals of Domination in Graphs, CRC press, 1988.
  * [12] Li J., Potru R., Shahrokhi F.: A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph, Algorithms 13 (12), 339, 2021.
  * [13] Lovasz L.: On the Ratio of Optimal Integral and Fractional Covers. Discrete Mathematics, Vol. 13, 1975, 383-390.
  * [14] Meir A., Moon J. W.: Relations between packing and covering numbers of a tree, Pacific Journal of Mathematics 61 (1975) 225–233.
  * [15] Rall D.F.:Total Domination in Categorical Products of Graphs. Discussiones Mathematicae Graph Theory 25(1-2):35-44, 2005.
  * [16] Vapnik V. N, Chervonenkis A.: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities.,Theory of Probability and Its Applications. 16(2), pp. 264-279, Springer (1971).