N)}{\pi N}-\frac{3\cos(\pi N)}{(\pi N)^{2}}+\frac{3\sin(\pi N)}{(\pi
N)^{3}}\right)\right.\\\ \left.+\sin^{2}\psi\left(\frac{\cos^{3}(\pi N)}{(\pi
N)^{2}}+\frac{4\sin^{3}(\pi N)}{3(\pi N)^{3}}-\frac{\sin(\pi N)}{(\pi
N)^{3}}\right)\right].$ (151)

The next two components are also zero

$\displaystyle(\mathbf{m}_{0})_{5}$ $\displaystyle=$
$\displaystyle\int_{-1}^{+1}-2r_{1}(\Sigma_{11}r_{3}-\Sigma_{13}r_{1})+r_{2}(\Sigma_{21}r_{3}-\Sigma_{23}r_{1})+r_{3}(\Sigma_{31}r_{3}-\Sigma_{33}r_{1})\mathrm{d}s=0,$
(152) $\displaystyle(\mathbf{m}_{0})_{6}$ $\displaystyle=$
$\displaystyle\int_{-1}^{+1}-2r_{1}(\Sigma_{12}r_{1}-\Sigma_{11}r_{2})+r_{2}(\Sigma_{22}r_{1}-\Sigma_{21}r_{2})+r_{3}(\Sigma_{32}r_{1}-\Sigma_{31}r_{2})\mathrm{d}s=0,$
(153)

because each term in the integrals is an odd function of $s$.

##  Appendix C Useful integrals

We provide some useful integrals for the RFT calculations in Appendices A and
B.

$\displaystyle\int_{-1}^{+1}\cos(\pi Ns)\mathrm{d}s=\frac{2\sin(\pi N)}{\pi
N},$ (154) $\displaystyle\int_{-1}^{+1}\sin^{2}(\pi
Ns)\mathrm{d}s=1-\frac{\sin(2\pi N)}{2\pi N},$ (155)
$\displaystyle\int_{-1}^{+1}\cos^{2}(\pi Ns)\mathrm{d}s=1+\frac{\sin(2\pi
N)}{2\pi N},$ (156) $\displaystyle\int_{-1}^{+1}\sin^{2}(\pi Ns)\cos(\pi
Ns)\mathrm{d}s=\frac{2\sin^{3}(\pi N)}{3\pi N},$ (157)
$\displaystyle\int_{-1}^{+1}\cos^{3}(\pi Ns)\mathrm{d}s=\frac{2\sin(\pi
N)}{\pi N}-\frac{2\sin^{3}(\pi N)}{3\pi N},$ (158)
$\displaystyle\int_{-1}^{+1}s\sin(\pi Ns)\mathrm{d}s=-\frac{2\cos(\pi N)}{\pi
N}+\frac{2\sin(\pi N)}{(\pi N)^{2}},$ (159)
$\displaystyle\int_{-1}^{+1}s\sin(\pi Ns)\cos(\pi
Ns)\mathrm{d}s=-\frac{\cos(2\pi N)}{2\pi N}+\frac{\sin(2\pi N)}{(2\pi
N)^{2}},$ (160) $\displaystyle\int_{-1}^{+1}s\sin(\pi Ns)\cos^{2}(\pi
Ns)\mathrm{d}s=-\frac{2\cos^{3}(\pi N)}{3\pi N}+\frac{2\sin(\pi N)}{3(\pi
N)^{2}}-\frac{2\sin^{3}(\pi N)}{9(\pi N)^{2}},$ (161)
$\displaystyle\int_{-1}^{+1}s^{2}\cos(\pi Ns)\mathrm{d}s=\frac{2\sin(\pi
N)}{\pi N}+\frac{4\cos(\pi N)}{(\pi N)^{2}}-\frac{4\sin(\pi N)}{(\pi N)^{3}},$
(162) $\displaystyle\int_{-1}^{+1}s^{2}\sin^{2}(\pi
Ns)\mathrm{d}s=\frac{1}{3}-\left[\frac{\sin(2\pi N)}{2\pi N}+\frac{2\cos(2\pi
N)}{(2\pi N)^{2}}-\frac{2\sin(2\pi N)}{(2\pi N)^{3}}\right],$ (163)
$\displaystyle\int_{-1}^{+1}s^{2}\cos^{2}(\pi
Ns)\mathrm{d}s=\frac{1}{3}+\left[\frac{\sin(2\pi N)}{2\pi N}+\frac{2\cos(2\pi
N)}{(2\pi N)^{2}}-\frac{2\sin(2\pi N)}{(2\pi N)^{3}}\right].$ (164)

In addition to these, we point out that

$\int_{-1}^{+1}s^{j}\sin^{k}(\pi Ns)\cos^{l}(\pi Ns)\mathrm{d}s=0,$ (165)

for any non-negative integer powers $j,k,l$ so long as $j+k\equiv
1~{}(\mathrm{mod}2)$, because the integrand is an odd function of $s$.

##  Appendix D Validation of computational method

In order to validate our implementation of slender-body theory (SBT), we carry
out four different tests. For the implementation of single-filament dynamics
(i.e. standard SBT), we verify our computations against classical results for
prolate spheroids (Fig. 11), semi-circular arcs (Fig. 12) and helices (Fig.
13). In all three cases, our implementation of SBT is in excellent agreement
with results published in the literature. To test cross-filament interactions,
we compare the hydrodynamic resistance of two helical filaments placed head-
to-head and that of a single helical filament with twice the length (Fig. 14).
The relative error between the two setups decays with decreasing distance
between the two half-filaments, thus validating our implementation of cross-
filament HIs as well.

To determine the appropriate level of truncation in our spectral method
implementation of SBT, we perform self-convergence tests for a single helical
filament. In Fig. 15, we vary the number of Legendre polynomial modes from
$10$ to $20$, and we compare the resistance matrix at a given number of modes,
$N_{\mathrm{Legendre}}$, with the most refined numerical solution available,
i.e. $N_{\mathrm{Legendre}}=20$. The results of the self-convergence test for
a helix with four helical turns suggest that a truncation level of
$N_{\mathrm{Legendre}}=15$ is sufficient to obtain 99% accuracy. Unless
otherwise stated, this is the level of truncation used for the simulations
presented in this paper.

29.7cm17cm 21.0cm12cm

Figure 11: Tests for a prolate spheroid. Verifying our implementation of SBT
against the exact solution for spheroids [69]. In our implementation of SBT,
we truncate the numerical solution to $N_{\mathrm{Legendre}}=5$ Legendre
polynomial modes.

29.7cm17cm 21.0cm6cm

Figure 12: Tests for a semi-circular filament. (a) Verifying our
implementation of SBT (red circles) against Johnson’s asymptotic solution
(solid line) from Eq. (36) in Ref. [59]. The quantity being plotted is the
vertical component of the force density exerted by a horizontal semi-circular
filament, with slenderness $\epsilon=0.1$, translating vertically as shown in
the inset. (b) Verifying our implementation of SBT (red circles) against
Johnson’s SBT computations (solid line) and two asymptotic solutions (dashed
lines) by Cox [57] and Johnson [59]. The quantity being plotted is the drag
force per unit length on a semi-circular filament, with slenderness
$\epsilon=0.1$, translating along its axis of symmetry as shown in the inset.
For both (a) and (b), we use a truncation of $N_{\mathrm{Legendre}}=10$ in our
implementation of SBT. In (b), our results are overlaid onto Fig. 4 from Ref.
[59].

29.7cm17cm 21.0cm8.242cm

Figure 13: Tests for a helical filament. Verifying our implementation of SBT
(red circles) against Lighthill’s exact solution for infinite helices (dashed
line) [58] and Johnson’s SBT (solid line) [59]. The three data series
represent the tangential ($f_{s}$), normal ($f_{n}$) and binormal ($f_{b}$)
components of the force density along a helix (with a prolate spheroidal
cross-section) that is translating and rotating about its axis of symmetry
such that the net force along the axis is zero. Helix parameters: (a) five
helical turns, $\epsilon=0.0021$, $\psi=1.0039$ rad; (b) one helical turn,
$\epsilon=0.0107$, $\psi=1.0039$ rad. In our implementation of SBT, we
truncate the solution to $N_{\mathrm{Legendre}}=25$ Legendre polynomial modes.
Our results are overlaid onto Fig. 6 from Ref. [59].

29.7cm17cm 21.0cm8.5cm

Figure 14: Tests for cross-filament HIs. We compare the hydrodynamic
resistance of two interacting helical filaments, having two helical turns each
and placed head-to-head (H2H), with that of one helical filament that has four
helical turns (ONE). In the limit $\delta\to 0$, the two problems are
identical. We plot (on a log-linear scale) the relative errors in the
coefficients of the resistance matrix $A_{33}=F_{z}/U_{z}$ (blue circles),
$B_{33}=F_{z}/\Omega_{z}$ (purple rightward triangles), $A_{11}=F_{x}/U_{x}$
(yellow upward triangles) and $D_{33}=T_{z}/\Omega_{z}$ (orange squares). The
relative error is defined as $|1-\textrm{H2H}/\textrm{ONE}|$ and decays with
decreasing separation $\delta$, thus validating our implementation of cross-
filament HIs. Helix parameters: $\psi=0.5043$ rad, $\epsilon=0.0024$ (for
$N=4$ helical turns) and $\epsilon=0.0048$ (for $N=2$ helical turns).

29.7cm17cm 21.0cm8.5cm

Figure 15: Self-convergence test for a single helical filament. The percentage
errors in $A_{33}=F_{z}/U_{z}$ (blue circles), $B_{33}=F_{z}/\Omega_{z}$
(purple rightward triangles), $A_{11}=F_{x}/U_{x}$ (yellow upward triangles)
and $D_{33}=T_{z}/\Omega_{z}$ (orange squares) are calculated at each number
of Legendre modes relative to the most accurate numerical solution available,
in this case $N_{\mathrm{Legendre}}=20$. Helix parameters: $\psi=0.5043$ rad,
$\epsilon=0.0038$, $N=4$ helical turns.

## References

  * Darnton  _et al._ [2010] N. C. Darnton, L. Turner, S. Rojevsky, and H. C. Berg, Dynamics of bacterial swarming, Biophys. J. 98, 2082 (2010).
  * Brumley  _et al._ [2014] D. R. Brumley, K. Y. Wan, M. Polin, and R. E. Goldstein, Flagellar synchronization through direct hydrodynamic interactions, eLife 3, e02750 (2014).
  * Wan and Goldstein [2016] K. Y. Wan and R. E. Goldstein, Coordinated beating of algal flagella is mediated by basal coupling, Proc. Natl. Acad. Sci. USA 113, E2784 (2016).
  * Guo  _et al._ [2021] H. Guo, Y. Man, K. Y. Wan, and E. Kanso, Intracellular coupling modulates biflagellar synchrony, J. R. Soc. Interface 18, 20200660 (2021).
  * Ishikawa [2009] T. Ishikawa, Suspension biomechanics of swimming microbes, J. R. Soc. Interface 6, 815 (2009).
  * Shaqfeh and Fredrickson [1990] E. S. Shaqfeh and G. H. Fredrickson, The hydrodynamic stress in a suspension of rods, Phys. Fluids A 2, 7 (1990).
  * Mackaplow and Shaqfeh [1996] M. B. Mackaplow and E. S. Shaqfeh, A numerical study of the rheological properties of suspensions of rigid, non-Brownian fibres, J. Fluid Mech. 329, 155 (1996).
  * Guazzelli and Hinch [2011] É. Guazzelli and J. Hinch, Fluctuations and instability in sedimentation, Annu. Rev. Fluid Mech. 43, 97 (2011).
  * du Roure  _et al._ [2019] O. du Roure, A. Lindner, E. N. Nazockdast, and M. J. Shelley, Dynamics of flexible fibers in viscous flows and fluids, Annu. Rev. Fluid Mech. 51, 539 (2019).
  * Ramaswamy [2010] S. Ramaswamy, The mechanics and statistics of active matter, Annu. Rev. Condens. Matter Phys. 1, 323 (2010).
  * Marchetti  _et al._ [2013] M. C. Marchetti, J. F. Joanny, S. Ramaswamy, T. B. Liverpool, J. Prost, M. Rao, and R. A. Simha, Hydrodynamics of soft active matter, Rev. Mod. Phys. 85, 1143 (2013).
  * Sharifi-Mood  _et al._ [2016] N. Sharifi-Mood, A. Mozaffari, and U. M. Córdova-Figueroa, Pair interaction of catalytically active colloids: from assembly to escape, J. Fluid Mech. 798, 910–954 (2016).
  * Varma  _et al._ [2018] A. Varma, T. D. Montenegro-Johnson, and S. Michelin, Clustering-induced self-propulsion of isotropic autophoretic particles, Soft Matter 14, 7155 (2018).
  * Varma and Michelin [2019] A. Varma and S. Michelin, Modeling chemo-hydrodynamic interactions of phoretic particles: A unified framework, Phys. Rev. Fluids 4, 124204 (2019).
  * Saha  _et al._ [2019] S. Saha, S. Ramaswamy, and R. Golestanian, Pairing, waltzing and scattering of chemotactic active colloids, New J. Phys. 21, 063006 (2019).
  * Vicsek and Zafeiris [2012] T. Vicsek and A. Zafeiris, Collective motion, Phys. Rep. 517, 71 (2012).
  * Elgeti  _et al._ [2015] J. Elgeti, R. Winkler, and G. Gompper, Physics of microswimmers—single particle motion and collective behavior: a review, Rep. Prog. Phys. 78, 056601 (2015).
  * Li  _et al._ [2016] G. Li, A. Ostace, and A. M. Ardekani, Hydrodynamic interaction of swimming organisms in an inertial regime, Phys. Rev. E 94, 053104 (2016).
  * Weihs [1973] D. Weihs, Hydromechanics of Fish Schooling, Nature 241, 290–291 (1973).
  * Dai  _et al._ [2018] L. Dai, G. He, X. Zhang, and X. Zhang, Stable formations of self-propelled fish-like swimmers induced by hydrodynamic interactions, J. R. Soc. Interface 15, 20180490 (2018).
  * Pan and Dong [2020] Y. Pan and H. Dong, Computational analysis of hydrodynamic interactions in a high-density fish school, Phys. Fluids 32, 121901 (2020).
  * Jeffery [1915] G. B. Jeffery, On the steady rotation of a solid of revolution in a viscous fluid, Proc. Lond. Math. Soc. 14, 327 (1915).
  * Stimson and Jeffery [1926] M. Stimson and G. B. Jeffery, The motion of two spheres in a viscous fluid, Proc. R. Soc. Lond. A 111, 110 (1926).
  * Goddard  _et al._ [2020] B. D. Goddard, R. D. Mills-Williams, and J. Sun, The singular hydrodynamic interactions between two spheres in stokes flow, Phys. Fluids 32, 062001 (2020).
  * Goldman  _et al._ [1966] A. Goldman, R. Cox, and H. Brenner, The slow motion of two identical arbitrarily oriented spheres through a viscous fluid, Chem. Eng. Sci 21, 1151 (1966).
  * Wakiya [1967] S. Wakiya, Slow motions of a viscous fluid around two spheres, J. Phys. Soc. Japan 22, 1101 (1967).
  * Dabroś [1985] T. Dabroś, A singularity method for calculating hydrodynamic forces and particle velocities in low-Reynolds-number flows, J. Fluid Mech. 156, 1–21 (1985).
  * Kim and Mifflin [1985] S. Kim and R. T. Mifflin, The resistance and mobility functions of two equal spheres in low‐Reynolds‐number flow, Phys. Fluids 28, 2033 (1985).
  * Yoon and Kim [1987] B. J. Yoon and S. Kim, Note on the direct calculation of mobility functions for two equal-sized spheres in Stokes flow, J. Fluid Mech. 185, 437–446 (1987).
  * Felderhof [1977] B. Felderhof, Hydrodynamic interaction between two spheres, Physica A 89, 373 (1977).
  * Cichocki  _et al._ [1988] B. Cichocki, B. Felderhof, and R. Schmitz, Hydrodynamic interactions between two spherical particles, Physico Chem. Hyd. 10, 383 (1988).
  * Jayaweera  _et al._ [1964] K. O. L. F. Jayaweera, B. J. Mason, and G. W. Slack, The behaviour of clusters of spheres falling in a viscous fluid Part 1. Experiment, J. Fluid Mech. 20, 121– (1964).
  * Cichocki  _et al._ [1994] B. Cichocki, B. U. Felderhof, K. Hinsen, E. Wajnryb, and J. Bławzdziewicz, Friction and mobility of many spheres in Stokes flow, J. Chem. Phys. 100, 3780 (1994).
  * Hocking [1964] L. M. Hocking, The behaviour of clusters of spheres falling in a viscous fluid Part 2. Slow motion theory, J. Fluid Mech. 20, 129– (1964).
  * Nasseri and Phan-Thien [1997] S. Nasseri and N. Phan-Thien, Hydrodynamic interaction between two nearby swimming micromachines, Comp. Mech. 20, 551 (1997).
  * Ishikawa  _et al._ [2007] T. Ishikawa, G. Sekiya, Y. Imai, and T. Yamaguchi, Hydrodynamic interactions between two swimming bacteria, Biophys. J. 93, 2217 (2007).
  * Ishikawa  _et al._ [2020] T. Ishikawa, T. J. Pedley, K. Drescher, and R. E. Goldstein, Stability of dancing Volvox, J. Fluid. Mech. 903, A11 (2020).
  * Gyrya  _et al._ [2010] V. Gyrya, I. S. Aranson, L. V. Berlyand, and D. Karpeev, A model of hydrodynamic interaction between swimming bacteria, Bull. Math. Biol. 72, 148 (2010).
  * Götze and Gompper [2010] I. O. Götze and G. Gompper, Mesoscale simulations of hydrodynamic squirmer interactions, Phys. Rev. E 82, 041921 (2010).
  * Molina  _et al._ [2013] J. J. Molina, Y. Nakayama, and R. Yamamoto, Hydrodynamic interactions of self-propelled swimmers, Soft Matter 9, 4923 (2013).
  * Liao  _et al._ [2007] Q. Liao, G. Subramanian, M. DeLisa, D. Koch, and M. Wu, Pair velocity correlations among swimming Escherichia coli bacteria are determined by force-quadrupole hydrodynamic interactions, Phys. Fluids 19, 061701 (2007).
  * Drescher  _et al._ [2009] K. Drescher, K. C. Leptos, I. Tuval, T. Ishikawa, T. J. Pedley, and R. E. Goldstein, Dancing Volvox: Hydrodynamic bound states of swimming algae, Phys. Rev. Lett. 102, 1168101 (2009).
  * Kim and Powers [2004] M. Kim and T. R. Powers, Hydrodynamic interactions between rotating helices, Phys. Rev. E 69, 061910 (2004).
  * Reigh  _et al._ [2012] S. Y. Reigh, R. G. Winkler, and G. Gompper, Synchronization and bundling of anchored bacterial flagella, Soft Matter 8, 4363 (2012).
  * Reigh  _et al._ [2013] S. Y. Reigh, R. G. Winkler, and G. Gompper, Synchronization, slippage, and unbundling of driven helical flagella, PLoS ONE 8, e70868 (2013).
  * Chakrabarti and Saintillan [2019] B. Chakrabarti and D. Saintillan, Hydrodynamic synchronization of spontaneously beating filaments, Phys. Rev. Lett. 123, 208101 (2019).
  * Man and Kanso [2020] Y. Man and E. Kanso, Multisynchrony in active microfilaments, Phys. Rev. Lett. 125, 148101 (2020).
  * Guirao and Joanny [2007] B. Guirao and J.-F. Joanny, Spontaneous creation of macroscopic flow and metachronal waves in an array of cilia, Biophys. J. 92, 1900 (2007).
  * Elgeti and Gompper [2013] J. Elgeti and G. Gompper, Emergence of metachronal waves in cilia arrays, Proc. Natl. Acad. Sci. USA 110, 4470 (2013).
  * Nguyen and Graham [2018] F. T. M. Nguyen and M. D. Graham, Impacts of multiflagellarity on stability and speed of bacterial locomotion, Phys. Rev. E 98, 042419 (2018).
  * Man  _et al._ [2016] Y. Man, L. Koens, and E. Lauga, Hydrodynamic interactions between nearby slender filaments, Europhys. Lett. 116, 24002 (2016).
  * Kim  _et al._ [2003] M. J. Kim, J. C. Bird, A. J. Van Parys, K. S. Breuer, and T. R. Powers, A macroscopic scale model of bacterial flagellar bundling, Proc. Natl. Acad. Sci. USA 100, 15481 (2003).
  * Kim  _et al._ [2004] M. J. Kim, M. J. Kim, J. C. Bird, J. Park, T. R. Powers, and K. S. Breuer, Particle image velocimetry experiments on a macro-scale model for bacterial flagellar bundling, Exp. Fluids 37, 782 (2004).
  * Hancock [1953] G. Hancock, The self-propulsion of microscopic organisms through liquids, Proc. R. Soc. A 217, 96 (1953).
  * Gray and Hancock [1955] J. Gray and G. J. Hancock, The propulsion of sea-urchin spermatozoa, J. Exp. Biol. 32, 802 (1955).
  * Lighthill [1996] J. Lighthill, Helical distributions of stokeslets, J. Eng. Math. 30, 35 (1996).
  * Cox [1970] R. G. Cox, The motion of long slender bodies in a viscous fluid Part 1. General theory, J. Fluid Mech. 44, 791–810 (1970).
  * Lighthill [1976] J. Lighthill, Flagellar hydrodynamics—The John von Neumann lecture, 1975, SIAM Rev. 18, 161 (1976).
  * Johnson [1980] R. E. Johnson, An improved slender-body theory for Stokes flow, J. Fluid Mech. 99, 411 (1980).
  * Tornberg and Shelley [2004] A. K. Tornberg and M. J. Shelley, Simulating the dynamics and interactions of flexible fibers in Stokes flows, J. Comp. Phys. 196, 8 (2004).
  * Maxian  _et al._ [2021] O. Maxian, A. Mogilner, and A. Donev, Integral-based spectral method for inextensible slender fibers in stokes flow, Phys. Rev. Fluids 6, 014102 (2021).
  * Koens [2016] L. M. Koens,  _The Hydrodynamics of Complex Microswimmers: An exploration of slender filaments and ribbons_ , Ph.D. thesis, University of Cambridge (2016).
  * Götz [2000] T. Götz,  _Interactions of fibers and flow: asymptotics, theory and numerics_ , Ph.D. thesis, University of Kaiserslautern (2000).
  * Darnton  _et al._ [2004] N. Darnton, L. Turner, K. Breuer, and H. C. Berg, Moving fluid with bacterial carpets, Biophys. J. 86, 1863 (2004).
  * Kim and Breuer [2008] M. Kim and K. Breuer, Microfluidic pump powered by self-organizing bacteria, Small 4, 111 (2008).
  * Martindale and Fu [2017] J. D. Martindale and H. C. Fu, Autonomously responsive pumping by a bacterial flagellar forest: A mean-field approach, Phys. Rev. E 96, 033107 (2017).
  * Dauparas  _et al._ [2018] J. Dauparas, D. Das, and E. Lauga, Helical micropumps near surfaces, Biomicrofluidics 12, 014108 (2018).
  * Buchmann  _et al._ [2018] A. Buchmann, L. J. Fauci, K. Leiderman, E. Strawbridge, and L. Zhao, Mixing and pumping by pairs of helices in a viscous fluid, Phys. Rev. E 97, 023101 (2018).
  * Chwang and Wu [1975] A. T. Chwang and T. Y.-T. Wu, Hydromechanics of low-Reynolds-number flow. Part 2. Singularity method for Stokes flows., J. Fluid Mech. 67, 787 (1975).


# Click prediction boosting via Bayesian hyperparameter optimization based
ensemble learning pipelines

Çağatay Demirel  A. Aylin Tokuç  Ahmet Tezcan Tekin  Computer Engineering
Department, Istanbul Technical University, Istanbul, Turkey  Donders Institute
for Brain, Cognition and Behaviour, Radboud University Medical Center,
Nijmegen, Netherlands  Computer Engineering Department, Kadir Has University,
Istanbul, Turkey University

###### Abstract

Online travel agencies (OTA’s) advertise their website offers on meta-search
bidding engines. The problem of predicting the number of clicks a hotel would
receive for a given bid amount is an important step in the management of an
OTA’s advertisement campaign on a meta-search engine, because $bid\times
numberofclicks$ defines the cost to be generated. Various regressors are
ensembled in this work to improve click prediction performance. Following the
preprocessing procedures, the feature set is divided into train and test
groups depending on the logging date of the samples. The data collection is
then subjected to feature elimination via utilizing XGBoost, which
significantly reduces the dimension of features. The optimum hyper-parameters
are then found by applying Bayesian hyperparameter optimization to XGBoost,
LightGBM, and SGD models. The different trained models are tested separately
as well as combined to form ensemble models. Four alternative ensemble
solutions have been suggested. The same test set is used to test both
individual and ensemble models, and the results of 46 model combinations
demonstrate that stack ensemble models yield the desired $R^{2}$ score of all.
In conclusion, the ensemble model improves the prediction performance by about
10%.

###### keywords:

Machine Learning , Ensemble Learning , Bayesian Optimization , Meta-search
Engines , Online travel agencies

††journal: arXiv

##  1 Introduction

Millions of travelers book hotel accommodation over the Internet each year.
Modern travelers rely on peer options, electronic word of mouth (eWOM), and
peer reviews. Popular online travel websites offer reliable reviews and prices
[1]. Therefore, customers choose to inspect and compare different options on
meta-search sites like Kayak.com, Trivago, and TripAdvisor before booking
their accommodations.

Online travel agencies (OTA’s) advertise their website offers on meta-search
bidding engines. If the OTA chooses to have a Cost-Per-Click (CPC) ad
campaign, the OTA promises to pay a certain amount for each click a certain
hotel gets from the platform under predefined conditions. The amount to pay
per click is the OTA’s $bid$ amount. The problem of predicting the number of
clicks a hotel would get for a certain bid amount is an important step in the
OTA’s advertisement campaign management on a meta-search engine, as $bid\times
numberofclicks$ defines the cost to be generated.

In one study, state-of-the-art prediction algorithms and Extreme Gradient
Boosting (XGBoost) [2] regressor as well as a minimum Redundancy-Maximum
Relevance (mRMR) [3] feature selection algorithm were executed to predict the
daily clicks to be received per hotel, using a large OTA’s data from Turkey
[4]. The data set received from the meta-search bidding engine contained both
numerical and categorical features, with each column having missing and
outlier values. The number of clicks as the multiplication of the predicted
click-through rate (CTR) and the predicted hotel impression were modelled. The
highest R-Squared values obtained in the prediction of individual-hotel based
CTR and impression values are both achieved by XGBoost in this work.

Another study aimed to forecast how many impressions and clicks a hotel will
acquire as well as how many rooms it will sell via a meta-search bidding
engine [5]. The given model predicts how much money an OTA’s hotels will make
the following day. The authors demonstrate that by incorporating OTA-specific
information into prediction models, the generalization of models improves and
better results are obtained. In that study, the best results were obtained
using tree-based boosting techniques.

Predicting hotel searches, clicks, and bookings is a challenging task due to
many external factors such as seasonality, events, location, and hotel-based
properties. Capturing such properties increases the accuracy of prediction
models. Due to the high variance in daily OTA data, the use of non-linear
prediction methods and creating relevant features with a time-delayed data
preprocessing approach is adopted in a work trying to forecast daily room
sales for each hotel in a meta-search bidding platform [6]. They applied
XGBoost, random forest, gradient boosting, deep neural networks, and
generalized linear models (GLM) [7]. The most successful model to predict
bookings is gradient boosting, applied on a dataset enriched by features that
can summarize the trends in the target variable well.

The demand for hotel rooms in the hotel industry in Turkey between the years
2002-2013 is estimated using ARIMA by Efendioglu and Bulkan [8]. In their
study, they determined the hotel room capacity according to the cost of the
unsold rooms and the ARIMA distribution. They also reported that the hotel
room demand in the country could be affected by outer factors such as
political crises and warnings about terrorism. This work shows the non-
deterministic nature of hotel room demand and how unpredictable factors
suddenly affect the click prediction problem.

In the literature, studies are focusing on the problem of predicting the CTR
of a sponsored display advertisement to be shown on a search engine, related
to a query. Click and CTR prediction is an ongoing research for both industry
and academia [9] [10] [11]. Our aim of predicting the number of clicks is
highly related to the CTR prediction problem, hence those studies are
investigated to get a better understanding of related work.

In order to predict ad clicks, Google makes use of logistic regression with
improvements in the context of traditional supervised learning based on an
FTRL-Proximal online learning algorithm [12] for better sparsity and
convergence. Microsoft’s Bing Search Engine proposes a new Bayesian online
learning algorithm for CTR prediction for sponsored search [13], which is
based on a probit regression model that maps discrete or real-valued input
features to probabilities. The scalability of the algorithm is ensured through
a principled weight pruning procedure and an approximate parallel
implementation. Yahoo adopts a machine learning framework based on Bayesian
logistic regression to predict click-through and conversion rates [14], which
is simple, scalable, and efficient. Facebook combines decision trees with
logistic regression [15], generating 3% better results in click prediction,
compared to other methods.

Ensemble learning [16] is a machine learning model combination that gets
decisions from various models to enhance the overall performance. The ensemble
approach provides the stability and low-variety predictions of machine
learning algorithms. It builds a set of decision-makers, namely classifiers
and regressors, with various techniques as final decisions [17].

An ensemble model is proposed by Wang et al. to predict the CTR of
advertisements on search engines [18]. Firstly, they tried several Maximum
Likelihood Estimation (MLE)-based methods to exploit the training set;
including Online Bayesian Probit Regression (BPR) [19], Support Vector Machine
(SVM), and Latent Factor Model (LFM) [20] and optimized them by selecting the
most descriptive features. They have created a rank-based ensemble model using
the outputs of BPR, SVM, and MLE. The results are ensembled using harmonic
means to generate the final blending submission. The proposed model’s output
shows an on average 0.013 improvement over the individual models.

Ensemble learning techniques implemented by King et al. to investigate whether
they could increase the profitability of pay-per-click (PPC) campaigns [21].
They applied voting, bootStrap aggregation (Bagging) [22], stacked
generalization (or stacking) [23], and metacost [24] techniques to four base
classifiers, namely, Naïve Bayes, logistic regression, decision trees, and
Support Vector Machines. The research in this work analyzed a data set of PPC
advertisements placed on the Google search engine, aiming to classify PPC
campaign success. They used average accuracy, recall, and precision metrics to
measure the performance of both base classifiers and ensemble models. They
also introduced the evaluation metric of total campaign portfolio profit and
illustrated how relying on overall model accuracy can be misleading. They
conclude that applying ensemble learning techniques in PPC marketing campaigns
can achieve higher profits.

Eight ensemble methods were proposed by Ling et al. to accurately estimate the
CTR in sponsored search ads [25]. A single model would lead to sub-optimal
accuracy, and the regression models all have different advantages and
disadvantages. The ensemble models are created via bagging, boosting,
stacking, and cascading. The training data is collected from historical ads’
impressions and the corresponding clicks. The Area under the Receiver
Operating Characteristic Curve (AUC) and Relative Information Gain (RIG)
metrics are computed against the testing data to evaluate prediction accuracy.
They conclude that boosting is better than cascading for the given problem.
Boosting neural networks with gradient boosting decision trees turned out to
be the best model in the given setting. They conclude that the model ensemble
is a promising direction for CTR prediction; meanwhile, domain knowledge is
also essential in the ensemble design.

Etsy, an online e-commerce platform, displays promoted search results, which
are similar to sponsored search results and our problem with meta-search
bidding engines. CTR prediction is utilized in the system to determine the
ranking of the ads [26]. They found out that different features capture
different aspects, so they classified the features as being historical and
content-based. They train separate CTR prediction models based on historical
and content-based features, separately. Then, these individual models are
combined with a logistic regression model. They reported AUC, Average
Impression Log Loss, and Normalized Cross-Entropy metrics to compare the
models to non-trivial baselines on a large-scale real-world dataset from Etsy,
demonstrating the effectiveness of the proposed system.

In this study, we utilize ensemble learning pipelines to predict the number of
clicks a hotel will receive the next day, and comparing substantial amount of
stand-alone prediction performance of the models.

##  2 Overview of the Proposed System

Figure 1: Overview of the System. The main train set is divided into two
subsets (train and test) to assess the importance of features. These are used
to determine the most representative feature subspace by testing with the
individual dataset that should be isolated from the actual test set.
Accordingly, Bayesian hyperparameter optimization is applied to each
individual model via training with a sub-train set. The dimensionality of the
main test set is reduced over a predefined feature subspace, and the model is
tested over five different model pipelines, including individual ten regressor
models, simple averaged and weighted averaged ensemble models, and stack and
blend ensemble pipelines.

There are five primary components in the proposed system. The complete
system’s flow diagram is depicted in Fig.-1. To summarize, queries are used to
retrieve the dataset from the database. Preprocessing is used to extract time-
domain seasonal decomposition features with suitable data cleaning in the next
stage. XGBoost, LightGBM (LGBM) [27] and Stochastic Gradient Descent (SGD)
[28] algorithms are then subjected to hyper-parameter tuning. In the final
step, individual and ensembled models are trained and tested with the same
train and test sets to generate click predictions. Each model’s $R^{2}$ score
is presented, and 46 distinct models are trained and tested via the proposed
system.

###  2.1 Dataset Generation and Data Preprocessing

The data is retrieved from a major OTA company based on Turkey. Contents of
the meta-search platform’s daily reports are combined with the data retrieved
from the OTA. The dataset contains both numerical and categorical features.
Some of the columns are eliminated during the data analysis phase as they
contain a high ratio of missing values. In this study, we have replaced the
missing values with the most common value and the average of the related
feature for categorical and numerical features, respectively.

In addition to OTA’s data, some external features are added to the dataset in
order to explain the state of the economical and seasonal properties of the
environment. Some simple external data examples are daily weather information
and daily exchange rates. Data enrichment improves the quality of the dataset.
The closeness of the related day to the next public holiday and the length of
the holiday are also added as additional numerical variables.

In order to improve the accuracy and generalization ability of the prediction
model, additional features are generated from the data following a sliding-
window (time-delay) approach. For example, the average and standard deviation
of numerical values for some specific time periods (such as the last 3, 7, and
30 days) are calculated and used as input features for prediction. The aim of
adding such features is to improve the accuracy and generalization ability of
the prediction model.

Feature space is enriched with the seasonal decomposition of some time-series
features. Seasonal decomposition is a naive decomposition model that generates
additive components by breaking the original feature into three. The output of
the algorithm is T: Trend, S: Seasonality, and e: Residual, where
$Y[t]=T[t]+S[t]+e[t]$. The seasonal component is first removed by applying a
convolution filter to the data. The average of this smoothed series for each
period is the returned seasonal component [29]. Decomposed seasonality, trend,
and residual values are added to the dataset as new features.

As a final step, feature one-hot encoding is proposed for some of the string-
based features and binarized. In the last step, the feature set is normalized
with min-max scaling to force values to be between 0 and 1.

###  2.2 XGBoost-based recursive feature elimination

XGBoost is the part of gradient boosting decision tree which operate via
regularization of the tree framework. By using gradient boosting to create the
boosted trees and collect the feature scores in an effective manner, each
feature’s significance to the training model is indicated [30]. The formula
calculation the feature importance of every feature $F_{n}$ is shown in Eq. 1.

$F_{n}(T)=\sqrt{\frac{1}{E}\sum_{e=1}^{E}\hat{i}^{2}(T_{e})}$ (1)

There is a subdivision of each node into two regions at every node $e$ for
each feature $n$ as a part of the feature space $F_{n}$ from a given single
decision tree $T$. The maximally forecasted score boosting rate $\hat{i}^{2}$
represents the metric of squared error shifts of the cost function from the
given XGBoost regression outcome of an additive tree $T_{e}$. The summation of
the squared importance over all trees $E$ proposes the summarization of the
square importance of the given feature $n$. Accordingly, the root mean squared
importance manifests the absolute importance factor of the feature.

The estimation of such an improvement depends on replacing the actual feature
value in space with random noise to determine a relative magnitude shift in
the final regression performance. Running multiple trees simultaneously
provides a better understanding of the average importance of the feature.

In the next step, the customized recursive feature elimination algorithm is
used to minimize the feature space [31]. The algorithm 1 shows the procedure
of the flow. The goal is to cover the features ($feature\\_subspace$) that
represent best the feature importance levels in a descending order. To avoid
the complexity of the classical recursive-based feature elimination due to the
large feature space, the initial feature importance values are considered as
bias factors for the features. Given that the randomization factor of the
selected features will be auto-biased in the subspace, such a specialization
significantly reduces the elimination process. $r^{2}\\_score$ value of a new
$feature\\_subspace$ is calculated within every iteration until convergence
occurs ($r^{2}\\_temp$ value stop being exceeded by $r^{2}\\_score$). Again
XGBoost regressor is selected as feature sub-space evaluator.

Data:

$\;\;\;\;\;\;\;FI=sort\\_descending(feature\\_importances)$

$\;\;\;\;\;\;\;r^{2}\\_temp=0$

Result:

$\;\;\;\;\;\;\;feature\\_subspace$

for  _$FI_{0}\;\;in\;\;FI$_ do

$feature\\_subspace=feature\\_space\>(FI_{0}<FI)$

$model=initialize\\_XGB\\_regressor\>()$

$model=XGB\\_regressor\\_train\>(train\\_data,\;train\\_labels)$

$r^{2}\\_score=XGB\\_regressor\\_test\>(model,\;test\\_data,\;test\\_labels)$

if  _$r^{2}\\_score <r^{2}\\_temp$_ then

return $(feature\\_subspace)$

else

$r^{2}\\_temp=r^{2}\\_score$

end if

end for

Algorithm 1 Recursive XGBoost dimensionally reduction algorithm

###  2.3 Bayesian Hyper-parameter Optimization

Hyper-parameter optimization is an essential approach for some machine
learning models to enhance prediction performance. There are a few algorithms
for tuning hyper-parameters. One of them is a Grid Search [32] which tries
each combination of given hyper-parameter candidates of a model. Another
optimization algorithm is known as random search [33], which randomly extracts
hyper-parameter combinations and tries to reach local optima of a performance
score. However, none of them are able to reach successful local optima of
performance in a short period. Bayesian hyper-parameter optimization [34] is a
relatively more powerful and efficient algorithm for hyper-parameter tuning.
It aims to reach a global optimum in a much shorter time than grid search.
There is a probabilistic model of $f(x)$ that aims to be exploited to make
decisions about where $X$ is accepted as the next performing function. This
procedure helps to find the minimum of non-convex functions in a few epochs,
which positively effects the performance. The evaluation metric to rank hyper-
parameter combinations through input data is $R-squared(R^{2})$. $R-squared$
is a statistical measure that represents the proportion of the variance for a
dependent variable that’s explained by an independent variable or variables in
a regression model. The formula of $R^{2}$ is shown in Eq. 2.

$R2=1-\frac{ExplainedVariation}{TotalVariation}$ (2)

In this work, $R^{2}$ values of individual machine learning algorithms
(XGBoost , LightGBM , SGD, Lasso [35], Lasso Lars [36], Ridge [37], Bayesian
Ridge [38], Huber [39], Passive Aggressive Regressors [40] and Elastic Net
[41]) are used and compared in ensemble models.

###  2.4 Ensembling

If there are M models with errors extracted from the same dataset which are
uncorrelated with them, the average error of a model is theoretically reduced
by some factor by simply averaging the model outputs. On the other hand, if
some of the model outputs have lower performance and are not fit to predict
results as well as others, overall error may not be reduced or even increase
in some cases.

####  2.4.1 Average & Weighted Average of Model Outputs

The first and most basic ensembling approach is to take an average of various
model outputs. There are two different averaging techniques for ensembling.
The first one is taking a mean of predicted values. It provides a lower
variance of predicted values since different algorithms proceed to predict
various aspects of the input data set. The formula for an average of model
outputs is shown in Eq. 3.

$Avg_{i}=\frac{\sum_{r}^{n}pi_{r}}{n}$ (3)

where $i$ is the $i^{th}$ sample, $r$ is regressor model, $pi_{r}$ is
individual probability of given regressor and $n$ is the number of models
used.

However, some machine learning models perform worse than others in terms of
prediction, culminating in a poorer overall ensemble prediction performance
than some individual regressor prediction performances. The fundamental reason
for this is because we give weak regressors the same weight as other ones that
provide decent individual performance. As a consequence, while taking an
average of all estimations, the weighted average is also utilized in this
study to eliminate the detrimental influence of low-performance models.
Weights are produced using each model’s individual $R^{2}$ score and scaled
between 0 and 1 to standardize the weight of each regressors, ensuring that
the sum of all weights is 1. This method allows models that predict higher
performance to have a greater impact on final prediction than models that
predict lower performance. The formula of the weighted average of model
outputs is shown in Eq. 4.

$\begin{split}Wavg_{i}=\sum_{r}w_{r}*pi_{r},\\\ r\in R\,for\,i=1\,to\,N,\\\
\sum_{r}w_{r}=1\end{split}$ (4)

where $r$ is the chosen regressor model, $w_{r}$ is normalized individual
$R^{2}$ performance of regressor. $r$, $pi_{r}$ is prediction result of
regressor $r$ of $i$’th sample and $N$ is the number of models used.

####  2.4.2 Stack Ensemble Model

Stack Ensemble algorithm, assemble results of individual results for different
models to make an intermediate input dataset, and the final model is used to
create a final regression result. In the proposed approach, ten different
models (XGBoost, LGBM, SGD, Lasso, Lasso Lars, Ridge, Bayesian Ridge, Huber,
Passive Aggressive Regressors, and Elastic Net) are trained to stack their
extracted predictions, and the intermediate dataset, which is the input to
ensemble regressors, is also trained with four different meta-regressor models
including XGB, Lasso, Bayesian ridge, and linear regressions for the final
click predictions. Additional meta-learners are also tried, but due to their
immense poor performance, those models are discarded and do not appear in the
outcomes of model variants.

Stacking the individual predictions enables us to analyze the intermediate
regressor model to linearly weight results to create a learnable weighted
average of provided predictions through each sample of input data. Overall
ensemble model variations are indicated in Fig. 2 along with the associations
between them.

Figure 2: Ensemble model pipelines. Individual models are trained via a
dimensionally reduced training set. Model predictions are further operated via
four ensemble methods: taking the prediction list’s average and a weighted
average to increase the positive bias for some regressors with better
prediction performance; four meta-regressor variations are fed by mediated
input features; the blend ensemble learning pipeline via combining a
collection of initial feature sets with model prediction results, and feeding
the blend into four different meta-regressor variations.

####  2.4.3 Blend Ensemble Model

The Stack ensemble method and the Blend ensemble algorithm [42] have similar
designs. The separate outcomes of regressor models are assembled in the first
stage. Additionally, the individual model outcomes are merged with a
dimensionally reduced featureset, which adds mediated features extracted as
predicted clicks with knowledge of intended predictions to produce an expanded
feature dimension.

Similar to stack ensemble models, XGBoost, LightGBM, SGD, Lasso, Lasso Lars,
Ridge, Bayesian Ridge, Huber, Passive Aggressive Regressors, and Elastic Net
are used to stack their given prediction outputs and blended with the input
feature set. Then, the blended dataset is also trained with four different
models same as the ones (XGB, Lasso, Bayesian ridge, and linear regressions)
chosen for the stack ensemble meta-learners to extract four different $R^{2}$
results.

##  3 Experiments and Results

Instead of splitting a dataset into train and test with some percentage, daily
click predictions of each hotel are estimated. Accordingly, the train set is
designed from the earliest day until test day that clicks will be predicted.
By using this approach, 11 consecutive days are chosen as test days and 11
corresponding $R^{2}$ test scores are produced by processing four different
ensembling models (Average & weighted average, stack ensemble, and blend
ensemble). Besides, individual $R^{2}$ test scores of ten regressor models
(XGBoost, LightGBM, SGD, Lasso, Lasso Lars, Ridge, Bayesian Ridge, Huber,
Passive Aggressive Regressors, and Elastic Net) are reported for the control
group, and efficiency of ensemble models is evaluated.

For each test day, 22 different predictions are measured (10 individual
predictions, average & weighted average predictions, five stack ensemble
prediction, and four blend ensemble predictions). $R^{2}$ score of each
prediction is saved and the average of each test $R^{2}$ score is calculated.
The average $R^{2}$ test scores of 21 model types are shown in Fig. 3.

Figure 3: Overall Test $R^{2}$ Scores for Each Regressor Model

###  3.1 Click prediction performances of individual models

Individual regressor predictions of all models (XGBoost, LightGBM, SGD, Lasso,
Lasso Lars, Ridge, Bayesian Ridge, Huber, Passive Aggressive Regressors, and
Elastic Net) are reported for the control group, and $R^{2}$ scores of models
are evaluated as 0.485, 0.538, 0.497, 0.496, 0.272, 0.578, 0.579, 0.514,
0.557, and -0.012 respectively.

###  3.2 Click prediction performances of ensemble models

The performance of the ensemble model largely exceeded the results of the
individual models, with the highest $R^{2}$ value of 0.639 shared by three
stack ensemble models (ensemble stack with linear regression; ensemble stack
with Lasso; and ensemble stack with Bayesian ridge). According to these
models, ensemble blending with Lasso and ensemble blending with Bayesian ridge
regressors came second at 0.638. The key detail here is that the six best-
performing models are ensemble ones. The performance drops relatively
significantly on a more primitive ensemble model, the weighted average
predictor, which comes third with an $R^{2}$ value of 0.597. The other three
ensemble methods, ensemble stack with XGB, ensemble blend with LGBM, and
ensemble stack with LGBM, show performance at the isolated model level (0.512,
0.5, and 0.451).

It can be inferred from the results that simpler regressor models as meta-
predictors overshadow tree based regressors due to the fact that the most of
the work is already done by the level-0 learners; the level-1 regressor is
basically just a mediator and it makes sense to choose a rather simple
algorithm for this purpose [43]. Simple linear models at the leaves suppose to
work well, and the results are likely to prove once again.

##  4 Conclusion and discussion

Assorted regressors are ensembled in the proposed study to improve click
prediction performance. The feature set is divided into train and test groups
depending on the logging date in the first phase. The data collection is then
subjected to an XGBoost-based dimension reduction, which significantly reduces
the dimension of features. To discover the most ideal hyper-parameters,
Bayesian Hyper-parameter optimization is developed for the XGBoost, LightGBM,
and SGD models. XGBoost, LightGBM, SGD, Lasso, Lasso Lars, Ridge, Bayesian
Ridge, Huber, Elastic Net, and Passive Aggressive regressors are all tested
separately and then fused to create ensemble models.

The authors suggest four different ensemble approaches. The first ensemble
model takes an average of anticipated results as well as a weighted average. A
stack ensemble model, for example, assembles all the results of individual
forecasts as an intermediate layer that feeds into another individual layer.
The third model is a blend ensemble model, which stacks all of the individual
prediction outputs and blends them with the original feature set once more.
With the outcomes of multiple model outputs, this framework offers an
artificial feature generation to boost the feature dimension.

The same test set is used to test both individual and ensemble models, and the
results of 46 model combinations demonstrate that stack ensemble models
produce the best $R^{2}$ score of all. The greatest $R^{2}$ score is 0.639 for
the stack ensemble model combined with linear regression, whereas the best
machine learning model had an $R^{2}$ score of 0.579. As a conclusion, the
ensemble model improves prediction performance by about 10%.

Various types of artificial neural network (ANN) models will be added to
ensemble models in the future, with the goal of improving stack and blend
ensemble models. Yandex’s CatBoost machine learning model [44], which handles
categorical information, can also be added to the list of regressors to
examine.

The concept of meta-learners is designed to provide the final outcome, yet
there are possibilities to convert them into intermediate learners via
inducing additional hyperparameter optimization mechanisms or additional meta-
feature elimination due to forming the additive judgement on stacked
predictions on an originally reduced feature dimension [45]. Articulating
meta-learners as mediators would be an inception based regularizer for
intercommunication between multiple meta-models as a single pipeline, which
might recalibrate incoming feature space with new model parameters to interact
with.

##  5 Declaration of Competing Interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## References

  * [1] L. V. Casaló, C. Flavián, M. Guinalíu, Y. Ekinci, Do online hotel rating schemes influence booking behaviors?, International Journal of Hospitality Management 49 (2015) 28–36.  doi:https://doi.org/10.1016/j.ijhm.2015.05.005.
  * [2] T. Chen, C. Guestrin, XGBoost: A scalable tree boosting system, in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, ACM, New York, NY, USA, 2016, pp. 785–794.  doi:10.1145/2939672.2939785.
  * [3] A. Torralba, A. Oliva, Depth estimation from image structure, IEEE Transactions on Pattern Analysis & Machine Intelligence 27 (09) (2002) 1226–1238.  doi:10.1109/TPAMI.2002.1033214.
  * [4] T. Cakmak, A. T. Tekin, C. Senel, T. Coban, Z. E. Uran, C. O. Sakar, Accurate prediction of advertisement clicks based on impression and click-through rate using extreme gradient boosting, in: Proceedings of the ICPRAM 2019 - 8th International Conference on Pattern Recognition Applications and Method, 2019\.
  * [5] A. T. Tekin, F. Cebi, Click and sales prediction for digital advertisements: Real world application for otas, in: C. Kahraman, S. Cebi, S. Cevik Onar, B. Oztaysi, A. C. Tolga, I. U. Sari (Eds.), Intelligent and Fuzzy Techniques in Big Data Analytics and Decision Making, Springer International Publishing, Cham, 2020, pp. 205–212.
  * [6] G. Aras, G. Ayhan, M. A. Sarikaya, A. A. Tokuç, C. O. Sakar, Forecasting hotel room sales within online travel agencies by combining multiple feature sets, in: Proceedings of the ICPRAM 2019 - 8th International Conference on Pattern Recognition Applications and Method, 2019.
  * [7] J. A. Nelder, R. W. M. Wedderburn, Generalized linear models, Journal of the Royal Statistical Society: Series A (General) 135 (3) (1972) 370–384.  doi:https://doi.org/10.2307/2344614.
  * [8] D. Efendioğlu, S. Bulkan, Capacity management in hotel industry for turkey, in: Handbook of Research on Holistic Optimization Techniques in the Hospitality, Tourism, and Travel Industry, IGI Global, 2017, pp. 286–304.
  * [9] D. C. Fain, J. O. Pedersen, Sponsored search: A brief history, Bulletin of the american Society for Information Science and technology 32 (2) (2006) 12–13.
  * [10] B. J. Jansen, T. Mullen, Sponsored search: an overview of the concept, history, and technology, International Journal of Electronic Business 6 (2) (2008) 114–131.  doi:10.1504/IJEB.2008.018068.
  * [11] A. Ghose, S. Yang, An empirical analysis of search engine advertising: Sponsored search in electronic markets, Management Science 55 (10) (2009) 1605–1622.  doi:10.1287/mnsc.1090.1054.
  * [12] H. B. McMahan, G. Holt, D. Sculley, M. Young, D. Ebner, J. Grady, L. Nie, T. Phillips, E. Davydov, D. Golovin, S. Chikkerur, D. Liu, M. Wattenberg, A. M. Hrafnkelsson, T. Boulos, J. Kubica, Ad click prediction: A view from the trenches, in: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’13, Association for Computing Machinery, New York, NY, USA, 2013, p. 1222–1230.  doi:10.1145/2487575.2488200.
  * [13] T. Graepel, J. Q. n. Candela, T. Borchert, R. Herbrich, Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft’s bing search engine, in: Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML’10, Omnipress, Madison, WI, USA, 2010, p. 13–20.
  * [14] O. Chapelle, E. Manavoglu, R. Rosales, Simple and scalable response prediction for display advertising, ACM Trans. Intell. Syst. Technol. 5 (4).  doi:10.1145/2532128.
  * [15] X. He, J. Pan, O. Jin, T. Xu, B. Liu, T. Xu, Y. Shi, A. Atallah, R. Herbrich, S. Bowers, J. Q. n. Candela, Practical lessons from predicting clicks on ads at facebook, in: Proceedings of the Eighth International Workshop on Data Mining for Online Advertising, ADKDD’14, Association for Computing Machinery, New York, NY, USA, 2014, p. 1–9.  doi:10.1145/2648584.2648589.
  * [16] S. Lei, M. Xinming, X. Lei, H. Xiaohong, Financial data mining based on support vector machines and ensemble learning, in: 2010 International Conference on Intelligent Computation Technology and Automation, Vol. 2, 2010, pp. 313–314.  doi:10.1109/ICICTA.2010.787.
  * [17] T. G. Dietterich, Ensemble methods in machine learning, in: Multiple Classifier Systems, Springer Berlin Heidelberg, Berlin, Heidelberg, 2000, pp. 1–15.
  * [18] X. Wang, S. Lin, D. Kong, L. Xu, Q. Yan, S. Lai, L. Wu, A. Chin, G. Zhu, H. Gao, et al., Click-through prediction for sponsored search advertising with hybrid models, in: KDD Workshop, 2012.
  * [19] T. E. Smith, J. P. LeSage, A bayesian probit model with spatial dependencies, in: Spatial and spatiotemporal econometrics, Emerald Group Publishing Limited, 2004.  doi:10.1016/S0731-9053(04)18004-3.
  * [20] D. Agarwal, B.-C. Chen, Regression-based latent factor models, in: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09, Association for Computing Machinery, New York, NY, USA, 2009, p. 19–28.  doi:10.1145/1557019.1557029.
  * [21] M. A. King, A. S. Abrahams, C. T. Ragsdale, Ensemble learning methods for pay-per-click campaign management, Expert Systems with Applications 42 (10) (2015) 4818–4829.  doi:https://doi.org/10.1016/j.eswa.2015.01.047.
  * [22] L. Breiman, Bagging predictors, Machine learning 24 (2) (1996) 123–140.  doi:https://doi.org/10.1007/BF00058655.
  * [23] S. Zirpe, B. Joglekar, Negation handling using stacking ensemble method, in: 2017 International Conference on Computing, Communication, Control and Automation (ICCUBEA), 2017, pp. 1–5.  doi:10.1109/ICCUBEA.2017.8463946.
  * [24] P. Domingos, Metacost: A general method for making classifiers cost-sensitive, in: Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, 1999, pp. 155–164.
  * [25] X. Ling, W. Deng, C. Gu, H. Zhou, C. Li, F. Sun, Model ensemble for click prediction in bing search ads, in: Proceedings of the 26th International Conference on World Wide Web Companion, WWW ’17 Companion, International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 2017, p. 689–698.  doi:10.1145/3041021.3054192.
  * [26] K. Aryafar, D. Guillory, L. Hong, An ensemble-based approach to click-through rate prediction for promoted listings at etsy, in: Proceedings of the ADKDD’17, ADKDD’17, Association for Computing Machinery, New York, NY, USA, 2017\.  doi:10.1145/3124749.3124758.
  * [27] G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, T.-Y. Liu, Lightgbm: A highly efficient gradient boosting decision tree, in: I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, R. Garnett (Eds.), Advances in Neural Information Processing Systems 30, Curran Associates, Inc., 2017, pp. 3146–3154.
  * [28] L. Bottou, Large-scale machine learning with stochastic gradient descent, in: Y. Lechevallier, G. Saporta (Eds.), Proceedings of COMPSTAT’2010, Physica-Verlag HD, Heidelberg, 2010, pp. 177–186.  doi:https://doi.org/10.1007/978-3-7908-2604-3_16.
  * [29] N. Avazov, J. Liu, B. Khoussainov, Periodic neural networks for multivariate time series analysis and forecasting, in: 2019 International Joint Conference on Neural Networks (IJCNN), 2019, pp. 1–8.  doi:10.1109/IJCNN.2019.8851710.
  * [30] H. Zheng, J. Yuan, L. Chen, Short-term load forecasting using emd-lstm neural networks with a xgboost algorithm for feature importance evaluation, Energies 10 (8).  doi:10.3390/en10081168.
URL https://www.mdpi.com/1996-1073/10/8/1168

  * [31] K. Yan, D. Zhang, Feature selection and analysis on correlated gas sensor data with recursive feature elimination, Sensors and Actuators B: Chemical 212 (2015) 353–363.  doi:https://doi.org/10.1016/j.snb.2015.02.025.
URL https://www.sciencedirect.com/science/article/pii/S0925400515001872

  * [32] J. S. Bergstra, R. Bardenet, Y. Bengio, B. Kégl, Algorithms for hyper-parameter optimization, in: J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems 24, Curran Associates, Inc., 2011, pp. 2546–2554.
  * [33] D. C. Karnopp, Random search techniques for optimization problems, Automatica 1 (2) (1963) 111 – 121.  doi:https://doi.org/10.1016/0005-1098(63)90018-9.
  * [34] V. Nguyen, Bayesian optimization for accelerating hyper-parameter tuning, in: 2019 IEEE Second International Conference on Artificial Intelligence and Knowledge Engineering (AIKE), 2019, pp. 302–305.  doi:10.1109/AIKE.2019.00060.
  * [35] R. Tibshirani, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society: Series B (Methodological) 58 (1) (1996) 267–288.  doi:10.1111/j.2517-6161.1996.tb02080.x.
  * [36] B. Efron, T. Hastie, I. Johnstone, R. Tibshirani, Least angle regression, Ann. Statist. 32 (2) (2004) 407–499.  doi:10.1214/009053604000000067.
  * [37] A. E. Hoerl, R. W. Kennard, Ridge regression: Biased estimation for nonorthogonal problems, Technometrics 12 (1) (1970) 55–67.  doi:10.1080/00401706.1970.10488634.
  * [38] Q. Shi, M. Abdel-Aty, J. Lee, A bayesian ridge regression analysis of congestion’s impact on urban expressway safety, Accident Analysis & Prevention 88 (2016) 124 – 137.  doi:https://doi.org/10.1016/j.aap.2015.12.001.
  * [39] Q. Sun, W.-X. Zhou, J. Fan, Adaptive huber regression, Journal of the American Statistical Association 0 (0) (2019) 1–24.  doi:10.1080/01621459.2018.1543124.
  * [40] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, Y. Singer, Online passive-aggressive algorithms, Journal of Machine Learning Research 7 (2006) 551–585.
  * [41] H. Zou, T. Hastie, Regularization and variable selection via the elastic net, Journal of the Royal Statistical Society: Series B (Statistical Methodology) 67 (2) (2005) 301–320.  doi:10.1111/j.1467-9868.2005.00503.x.
  * [42] Z. Xie, A. Singh, J. Uang, K. S. Narayan, P. Abbeel, Multimodal blending for high-accuracy instance recognition, in: 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013, pp. 2214–2221.  doi:10.1109/IROS.2013.6696666.
  * [43] G. Srivastava, T. R. G, N. Deepa, B. Prabadevi, P. K. Reddy M, An ensemble model for intrusion detection in the internet of softwarized things, in: Adjunct Proceedings of the 2021 International Conference on Distributed Computing and Networking, ICDCN ’21, Association for Computing Machinery, New York, NY, USA, 2021, p. 25–30.  doi:10.1145/3427477.3429987.
URL https://doi.org/10.1145/3427477.3429987

  * [44] L. Prokhorenkova, G. Gusev, A. Vorobev, A. V. Dorogush, A. Gulin, Catboost: Unbiased boosting with categorical features, in: Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, Curran Associates Inc., Red Hook, NY, USA, 2018, p. 6639–6649.
  * [45] L. Chen, Y. Ding, S. Pirasteh, H. Hu, Q. Zhu, X. Ge, H. Zeng, H. Yu, Q. Shang, Y. Song, Meta-learning an intermediate representation for few-shot prediction of landslide susceptibility in large areas, International Journal of Applied Earth Observation and Geoinformation 110 (2022) 102807.  doi:https://doi.org/10.1016/j.jag.2022.102807.
URL https://www.sciencedirect.com/science/article/pii/S1569843222000097


# Hamilton Paths in Dominating Graphs of Trees and Cycles

Kira Adaricheva Department of Mathematics, Hofstra University, Hempstead, NY
11549, USA<EMAIL_ADDRESS>Heather Smith Blake Department of
Mathematics and Computer Science, Davidson College, Davidson, NC 28035, USA
<EMAIL_ADDRESS>Chassidy Bozeman Department of Mathematics and
Statistics, Mount Holyoke College, South Hadley, MA 01075, USA
<EMAIL_ADDRESS>Nancy E. Clarke Department of Mathematics and
Statistics, Acadia University, Wolfville, NS B4P 2R6, Canada
<EMAIL_ADDRESS>Ruth Haas Department of Mathematics, University of
Hawaii at Mānoa, Honolulu, HI 96822, USA<EMAIL_ADDRESS>Margaret-Ellen
Messinger Department of Mathematics and Computer Science, Mount Allison
University, Sackville, NB E4L 1E2, Canada<EMAIL_ADDRESS>Karen Seyffarth
Department of Mathematics and Statistics, University of Calgary, Calgary,
Alberta T2N 1N4, Canada<EMAIL_ADDRESS>
###### Abstract

The dominating graph of a graph $H$ has as its vertices all dominating sets of
$H$, with an edge between two dominating sets if one can be obtained from the
other by the addition or deletion of a single vertex of $H$. In this paper we
prove that the dominating graph of any tree has a Hamilton path. We also show
how a result about binary strings leads to a proof that the dominating graph
of a cycle on $n$ vertices has a Hamilton path if and only if $n\not\equiv
0\pmod{4}$.

##  1 Introduction

Let $H$ be a graph with vertex set $V(H)$. A dominating set of $H$ is a set
$D\subseteq V(H)$ such that every vertex of $V(H)\backslash D$ is adjacent to
a vertex of $D$. The dominating graph of $H$, $\mathcal{D}(H)$, is the graph
whose vertices are all the dominating sets of $H$; if $X$ and $Y$ are distinct
vertices of $\mathcal{D}(H)$, then there is an edge between $X$ and $Y$ if and
only if $Y$ can be obtained from $X$ by adding a vertex of $H$ to $X$ or by
deleting a vertex from $X$. Note that we use the same label for a vertex of
$\mathcal{D}(H)$ as for the corresponding dominating set of $H$ because it is
clear from context whether we are referring to $H$ or $\mathcal{D}(H)$.

The graph $\mathcal{D}(H)$ is the reconfiguration graph of dominating sets of
$H$ under the token addition/removal (TAR) model, first considered in [9]. For
any graph $H$ and any integer $k$, $1\leq k\leq|V(H)|$, the $k$-dominating
graph of $H$, denoted $\mathcal{D}_{k}(H)$, is the subgraph of
$\mathcal{D}(H)$ induced by the dominating sets of $H$ with cardinality at
most $k$. When $k=|V(H)|$, then $\mathcal{D}_{k}(H)=\mathcal{D}(H)$. There
have been numerous papers about dominating graphs and their subgraphs, the
$k$-dominating graphs. Most of these focus on conditions on $k$ that ensure
that $\mathcal{D}_{k}(H)$ is connected. Two recent surveys of reconfiguration
of dominating sets are [1] and [11].

There has been considerable interest in reconfiguration and reconfiguration
graphs of other well known graph structures and operations, including
independent sets, cliques, vertex covers of graphs, zero forcing, and graph
coloring. Nishimura [10] examines reconfiguration from an algorithmic
perspective and considers complexity questions in a wide range of
reconfiguration settings. Reconfiguration of graph coloring problems and
dominating set problems are surveyed in a recent paper of Mynhardt and
Nasserasr [11].

In this paper we investigate Hamilton cycles and Hamilton paths in dominating
graphs, properties that have been studied for other types of reconfiguration
problems. A Hamilton path or Hamilton cycle in a reconfiguration graph is a
combinatorial Gray code, that is, a listing of all the objects in a set so
that successive objects differ in some prescribed minimal way. Several recent
papers give conditions for the existence of Gray codes for all colorings with
$k$ or fewer colors of the following classes of graphs: trees [7], bipartite
graphs [6], and 2-trees [5]. A forthcoming survey by Mütze gives a wide
variety of combinatorial Gray code results [12].

We consider only finite simple graphs. For a graph $H$, we use the notation
$P=x_{1},x_{2},\ldots,x_{j}$, where $j\geq 3$, to denote a path $P$ in $H$
where $\\{x_{1},x_{2},\ldots,x_{j}\\}$ is a subset of the vertices of $H$. An
edge $e$, i.e., a path with two vertices $x$ and $y$, is written simply as
$e=xy$. For basic graph theory notation and terminology not defined here, see
[3].

We begin with the question of which dominating graphs have Hamilton cycles. It
is clear that if $H$ is a graph, then its dominating graph, $\mathcal{D}(H)$,
is bipartite, with the bipartition based on the parity of the dominating sets
of $H$. It follows that if $\mathcal{D}(H)$ has a Hamilton cycle, then
$\mathcal{D}(H)$ has an even number of vertices (equivalently, the number of
dominating sets of $H$ is even). By contrast, we have the following
unpublished result of Brouwer [4], an expanded proof of which is included in
[1].

######  Lemma 1.

[4] The number of dominating sets of any finite graph is odd.

Combining Brouwer’s result with the observation that a bipartite graph with a
Hamilton cycle must have an even number of vertices gives a short answer to
the question of which dominating graphs have Hamilton cycles.

######  Proposition 2.

[1] For any graph $H$, the dominating graph ${\mathcal{D}}(H)$ has no Hamilton
cycle.

Henceforth, we focus our attention on Hamilton paths in dominating graphs.

In [1] we show that Hamilton paths exist in the dominating graphs of certain
classes of graphs. Specifically, we prove the following.

######  Theorem 3.

[1] Let $m$ and $n$ be positive integers. Then $\mathcal{D}(K_{n})$ has a
Hamilton path, $\mathcal{D}(P_{n})$ has a Hamilton path, and
$\mathcal{D}(K_{m,n})$ has a Hamilton path if and only if $m$ is odd.

In this paper we explore the dominating graphs of trees and prove the
following.

######  Theorem 4.

For any tree $T$, ${\mathcal{D}}(T)$ has a Hamilton path.

We also use a result of Baril and Vajnovszki [2] on Lucas strings to
characterize cycles whose dominating graphs have Hamilton paths.

######  Theorem 5.

For all integers $n\geq 3$, $\mathcal{D}(C_{n})$ has a Hamilton path if and
only if $n\not\equiv 0\pmod{4}$.

##  2 Two graph operations and their effects on the dominating graph

We begin this section by introducing two operations on a graph $H$. We then
prove that if $H^{\prime}$ is a graph obtained from $H$ by applying either
operation, and $\mathcal{D}(H^{\prime})$ has a Hamilton path, then
$\mathcal{D}(H)$ has a Hamilton path. This is later used to show that the
dominating graph of any tree has a Hamilton path.

######  Operation I.

Let $H$ be a graph with vertices $u,v$ and $x$ such that
$N_{H}(u)=N_{H}(v)=\\{x\\}$. We say that $H^{\prime}:=H-v$ is obtained from
$H$ by Operation I.

Figure 1: (a) Operation I and (b) Operation II

######  Operation II.

Let $H$ be a graph with vertices $u,v$ and $w$ such that $N_{H}(v)=\\{u,w\\}$
and $N_{H}(w)=\\{v\\}$. We say that $H^{\prime}:=H-w-v$ is obtained from $H$
by Operation II.

######  Lemma 6.

Let $H$ and $H^{\prime}$ be graphs such that $H^{\prime}$ is obtained from $H$
by Operation I. If $\mathcal{D}(H^{\prime})$ has a Hamilton path, then
$\mathcal{D}(H)$ has a Hamilton path.

###### Proof.

Suppose $H$ and $H^{\prime}$ are graphs as in the statement of the
Proposition. Then there are vertices $u,v,x\in V(H)$ such that
$N_{H}(u)=N_{H}(v)=\\{x\\}$, and $H^{\prime}:=H-v$. To simplify notation, we
define $G$ and $G^{\prime}$ to be the dominating graphs of $H$ and
$H^{\prime}$, respectively, i.e., $G:={\mathcal{D}}(H)$ and
$G^{\prime}:={\mathcal{D}}(H^{\prime})$. Recall that each vertex of $G$
represents a dominating set of $H$, so we name each vertex of $G$ with the
name of the corresponding subset of $V(H)$, and use the same convention for
vertices of $G^{\prime}$ and dominating sets of $H^{\prime}$.

Let $n=|V(G^{\prime})|$, and let $P_{G^{\prime}}:=F_{1},F_{2},\ldots,F_{n}$ be
a Hamilton path in $G^{\prime}$. For each $i$, $1\leq i\leq n$, define
$F^{v}_{i}:=F_{i}\cup\\{v\\}$, and for each $i$, $1\leq i\leq n$, with
$u\not\in F_{i}$, define

$F^{u}_{i}:=F_{i}\cup\\{u\\},\text{ and }F^{uv}_{i}:=F_{i}\cup\\{u,v\\}.$

Now consider the dominating sets of $H$. These can be partitioned into those
that contain $v$ and those that do not contain $v$. Because
$N_{H}(u)=\\{x\\}=N_{H}(v)$, the dominating sets of $H$ that contain $v$ are
precisely

$W:=\\{F_{i}^{v}~{}|~{}1\leq i\leq n\\},$

while the dominating sets of $H$ that do not contain $v$ are

$Z:=\\{F_{i}~{}|~{}x\in F_{i},1\leq i\leq n\\}.$

Now consider the following subsets of $V(G)$.

$\displaystyle X^{\prime}$ $\displaystyle:=$ $\displaystyle\\{F_{i}~{}|~{}x\in
F_{i},\,u\not\in F_{i},\,1\leq i\leq n\\},$ $\displaystyle B^{\prime}$
$\displaystyle:=$ $\displaystyle\\{F_{i}~{}|~{}\\{x,u\\}\subseteq
F_{i},\,1\leq i\leq n\\}=\\{F_{i}^{u}~{}|~{}F_{i}\in X^{\prime}\\},$
$\displaystyle X$ $\displaystyle:=$ $\displaystyle\\{F_{i}^{v}~{}|~{}x\in
F_{i},\,u\not\in F_{i},\,1\leq i\leq n\\}=\\{F_{i}^{v}~{}|~{}F_{i}\in
X^{\prime}\\},$ $\displaystyle B$ $\displaystyle:=$
$\displaystyle\\{F_{i}^{v}~{}|~{}\\{x,u\\}\subseteq F_{i},\,1\leq i\leq
n\\}=\\{F_{i}^{uv}~{}|~{}F_{i}\in X^{\prime}\\},$ $\displaystyle U$
$\displaystyle:=$ $\displaystyle\\{F_{i}^{v}~{}|~{}u\in F_{i},\,x\not\in
F_{i},\,1\leq i\leq n\\}.$

Figure 2: A partition of $V(G)=V(\mathcal{D}(H))$ into sets
$\\{U,B,X,B^{\prime},X^{\prime}\\}$, with the parts shaded grey corresponding
to a subgraph of $G$ isomorphic to $G^{\prime}=\mathcal{D}(H^{\prime})$.

It is routine to verify that $\\{X^{\prime},B^{\prime}\\}$ is a partition of
$Z$ while $\\{X,B,U\\}$ is a partition of $W$, and hence
$\\{U,B,X,B^{\prime},X^{\prime}\\}$ is a partition of $V(G)$. Furthermore, the
definitions of $B^{\prime},X$ and $B$ in terms of $X^{\prime}$ make it clear
that

$G[B^{\prime}]\cong G[X]\cong G[B]\cong G[X^{\prime}].$

Finally, the definition of $W$ ensures that $G[W]=G[X\cup B\cup U]\cong
G^{\prime}$. It follows that $P:=F_{1}^{v},F_{2}^{v},\ldots,F_{n}^{v}$ is a
path in $G$ and also a Hamilton path of $G[X\cup B\cup U]$. We now extend $P$
to a Hamilton path of $G$.

Let $Q:=F_{i}^{v},F_{i+1}^{v},\ldots,F_{j}^{v}$ be a maximal subpath of $P$ in
$G[X]$. There are two cases to consider, depending on the parity of $j-i+1$
(the number of vertices in $Q$). First suppose that $j-i+1$ is even. Then for
each $t\in\\{i,i+2,\ldots,j-1\\}$, replace the edge $F_{t}^{v}F_{t+1}^{v}$ of
$P$ by the path

$F_{t}^{v},F_{t},F_{t}^{u},F_{t+1}^{u},F_{t+1},F_{t+1}^{v}.$

Since $G[B^{\prime}]\cong G[X]$, this replacement results in a path in $G$.

Now assume that $j-i+1$ is odd. In this case, for each
$t\in\\{i,i+2,\ldots,j-2\\}$, replace the edge $F_{t}^{v}F_{t+1}^{v}$ of $P$
by the path

$F_{t}^{v},F_{t},F_{t}^{u},F_{t+1}^{u},F_{t+1},F_{t+1}^{v}.$

Again, since $G[B^{\prime}]\cong G[X]$, this replacement results in a path in
$G^{\prime}$. If $j=n$, replacing vertex $F_{n}^{v}$ in $P$ by the path
$F_{n}^{v},F_{n},F_{n}^{u}$ results in a path. Otherwise, $j<n$, so the
maximality of $Q$ implies $F_{j+1}^{v}\in B$, and hence
$F_{j+1}^{v}=F_{j}^{uv}$. Replacing the edge $F_{j}^{v}F_{j+1}^{v}$ (which
equals $F_{j}^{v}F_{j}^{uv}$) of $P$ with the path

$F_{j}^{v},F_{j},F_{j}^{u},F_{j}^{uv}$

ensures the result is a path in $G$.

Since $G[B^{\prime}]\cong G[X^{\prime}]\cong G[X]$, making these replacements
for each maximal subpath $Q$ of $P$ in $G[X]$ incorporates all the vertices of
$X^{\prime}$ and $B^{\prime}$ into the resulting path and produces a Hamilton
path of $G=\mathcal{D}(H)$. ∎

######  Lemma 7.

Let $H$ and $H^{\prime}$ be graphs such that $H^{\prime}$ is obtained from $H$
by Operation II. If $\mathcal{D}(H^{\prime})$ has a Hamilton path, then
$\mathcal{D}(H)$ has a Hamilton path.

###### Proof.

Suppose $H$ and $H^{\prime}$ are graphs as in the statement of the
Proposition. Then there exist vertices $u,v,w\in V(H)$ such that
$N_{H}(v)=\\{u,w\\}$, $N_{H}(w)=\\{v\\}$, and $H^{\prime}:=H-w-v$. As before,
we define $G$ and $G^{\prime}$ to be the dominating graphs of $H$ and
$H^{\prime}$, respectively, i.e., $G:={\mathcal{D}}(H)$ and
$G^{\prime}:={\mathcal{D}}(H^{\prime})$.

Let $Y$ be a dominating set of $H^{\prime}$. Since neither $v$ nor $w$ is a
vertex of $H^{\prime}$, $Y\cap\\{v,w\\}=\emptyset$, so we define

$Y^{v}:=Y\cup\\{v\\},Y^{w}:=Y\cup\\{w\\},\mbox{ and }Y^{vw}:=Y\cup\\{v,w\\},$

and let

$A:=\\{Y^{v},Y^{w},Y^{vw}~{}|~{}Y\in V(G^{\prime})\\}$

Then $A$ consists of dominating sets of $H$. The dominating sets of $H$ that
are not in $A$ can be described as follows. Let

$J:=\\{S\subseteq V(H^{\prime})~{}|~{}S\mbox{ is a dominating set of
}H^{\prime}-u\mbox{ and }S\cap N_{H^{\prime}}[u]=\emptyset\\},$

i.e., $J$ consists of the dominating sets of $H^{\prime}-u$ that are not
dominating sets of $H^{\prime}$. It follows that if $S\in J$, then
$S\cap\\{u,v,w\\}=\emptyset$, so we define

$\displaystyle
S^{u}:=S\cup\\{u\\},S^{v}:=S\cup\\{v\\},S^{uv}:=S\cup\\{u,v\\},$
$\displaystyle S^{vw}:=S\cup\\{v,w\\},\mbox{ and }S^{uvw}:=S\cup\\{u,v,w\\}.$

We now let

$B:=\\{S^{v},S^{vw}~{}|~{}S\in J\\}.$

It is routine to verify that $\\{A,B\\}$ is a partition of the dominating sets
of $H$.

Let $n=|V(G^{\prime})|$, and let $P_{G^{\prime}}=F_{1},F_{2},\ldots,F_{n}$ be
a Hamilton path in $G^{\prime}$. Note that $F_{i}\cap\\{v,w\\}=\emptyset$. By
Lemma 1, $n$ is odd, so replacing vertex $F_{i}$ of $P_{G^{\prime}}$ with the
path $F_{i}^{v},F_{i}^{vw},F_{i}^{w}$ when $i$ is odd, and with the path
$F_{i}^{w},F_{i}^{vw},F_{i}^{v}$ when $i$ is even produces the path

$P:=F_{1}^{v},F_{1}^{vw},F_{1}^{w},F_{2}^{w},F_{2}^{vw},F_{2}^{v},\ldots,F_{n}^{v},F_{n}^{vw},F_{n}^{w}$

in $G$. Since $P$ consists of all the vertices in $A$, what remains is to
incorporate the vertices of $B$ into this path.

First notice that, for each $S\in J$, $S^{u}$ is a dominating set of
$H^{\prime}$, and hence $S^{u}=F_{i}$ for some $i$, $1\leq i\leq n$.
Furthermore, it is clear that if $S_{1},S_{2}\in J$, then $S_{1}\neq S_{2}$ if
and only if $S_{1}^{u}\neq S_{2}^{u}$.

We now proceed as follows. For $S\in J$, let $t\in\\{1,\ldots,n\\}$ be the
index for which $S^{u}=F_{t}$. In the path $P$, we either have the edge
$F^{v}_{t}F^{vw}_{t}$ (which is the same as $S^{uv}S^{uvw}$) or the edge
$F^{vw}_{t}F^{v}_{t}$ (which is the same as $S^{uvw}S^{uv}$). If $P$ contains
$F^{v}_{t}F^{vw}_{t}$, replace it with the path

$F^{v}_{t}=S^{uv},S^{v},S^{vw},S^{uvw}=F^{vw}_{t}.$

Otherwise, replace $F^{vw}_{t}F^{v}_{t}$ with the path

$F^{vw}_{t}=S^{uvw},S^{vw},S^{v},S^{uv}=F^{v}_{t}.$

Repeating this for each $S\in J$ results in a path containing all the vertices
of $A\cup B=V(G)$, and hence all the dominating sets of $H$. Therefore,
$G=\mathcal{D}(H)$ has a Hamilton path. ∎

Together, the two preceding propositions imply the following.

######  Corollary 8.

Let $H$ be a graph and let $H^{\prime}$ be a graph obtained from $H$ by
applying any sequence of the Operations I and II. If $\mathcal{D}(H^{\prime})$
has a Hamilton path then $\mathcal{D}(H)$ has a Hamilton path.

##  3 Hamilton paths in dominating graphs of trees

A particular class of graphs to which we can apply Corollary 8 is trees. Let
$T$ be a tree and let ${\mathcal{D}}(T)$ be the dominating graph of $T$. To
prove that ${\mathcal{D}}(T)$ has a Hamilton path (Theorem 4), we use an
iterative process for constructing such a path. Doing so requires the
following lemma to deconstruct an arbitrary tree on $n\geq 3$ vertices using
Operations I and II.

######  Lemma 9.

If $T$ is a tree on $n\geq 3$ vertices, then one of the following holds:

  1. (1)

there exist distinct $u,v,x\in V(T)$ with $N_{T}(u)=N_{T}(v)=\\{x\\}$, or

  2. (2)

there exist distinct $u,v,w\in V(T)$ with $N_{T}(v)=\\{u,w\\}$ and
$N_{T}(w)=\\{v\\}$.

###### Proof.

The proof is by induction on $n$. When $n=3$, then $T\cong P_{3}$ and the
result is obvious.

Suppose $n\geq 4$. Let $z\in V(T)$ be a vertex of degree one, and let
$T^{\prime}=T-z$. By the induction hypothesis, $T^{\prime}$ satisfies (1) or
(2) of the statement of the Lemma.

First suppose that $T^{\prime}$ satisfies (1), and let $u,v,x\in
V(T^{\prime})$ with $N_{T^{\prime}}(u)=N_{T^{\prime}}(v)=\\{x\\}$. If
$N_{T}(z)\not\subseteq\\{u,v\\}$, then $N_{T}(u)=N_{T}(v)=\\{x\\}$, and $T$
satisfies (1). Otherwise, $N_{T}(z)\subseteq\\{u,v\\}$ and we may assume,
without loss of generality that, $N_{T}(z)=\\{u\\}$. We now have $z,u,x\in
V(T)$ with $N_{T}(u)=\\{z,w\\}$ and $N_{T}(z)=\\{u\\}$, so $T$ satisfies (2).

Now suppose that $T^{\prime}$ satisfies (2), and let $u,v,w\in V(T^{\prime})$
with $N_{T^{\prime}}(v)=\\{u,w\\}$ and $N_{T}(w)=\\{v\\}$. If
$N_{T}(z)\not\subseteq\\{v,w\\}$, then $N_{T}(v)=\\{u,w\\}$ and
$N_{T}(w)=\\{v\\}$, so $T$ satisfies (2). Otherwise, $N_{T}(z)=\\{v\\}$ or
$N_{T}(z)=\\{w\\}$. There are two cases to consider. If $N_{T}(z)=\\{v\\}$,
then $z,v,w\in V(T)$ and $N_{T}(w)=N_{T}(z)=\\{v\\}$, and thus $T$ satisfies
(1). If $N_{T}(z)=\\{w\\}$, then $z,v,w\in V(T)$, $N_{T}(w)=\\{v,z\\}$ and
$N_{T}(z)=\\{w\\}$, so $T$ satisfies (2). ∎

We are now in a position to prove our main result about trees, first stated in
the Introduction.

######  Theorem 4.

For any tree $T$, $\mathcal{D}(T)$ has a Hamilton path.

###### Proof.

Let $P_{i}$ denote the path on $i\geq 1$ vertices. If $|V(T)|\leq 2$, then
$T\cong P_{1}$ or $T\cong P_{2}$. Since $\mathcal{D}(P_{1})\cong P_{1}$ and
$\mathcal{D}(P_{2})\cong P_{3}$, $\mathcal{D}(T)$ has a Hamilton path. If
$|V(T)|\geq 3$, then by Lemma 9, we can repeatedly apply Operations I and II
to $T$ to obtain a tree $T^{\prime}$ with $|V(T^{\prime})|\leq 2$. Since
$\mathcal{D}(T^{\prime})$ has a Hamilton path, it follows from Corollary 8
that $\mathcal{D}(T)$ has a Hamilton path. ∎

##  4 Hamilton paths in dominating graphs of cycles

Let $C_{n}$ denote the cycle on $n\geq 3$ vertices. In our original
construction of a Hamilton path in $\mathcal{D}(C_{n})$ if and only if
$n\not\equiv 0\pmod{4}$, we encode dominating sets of $C_{n}$ as binary
strings, and construct a Gray code of this set of strings. It was pointed out
to us by T. Mütze that the set of strings corresponding to the dominating sets
of $C_{n}$ are the bitwise complements of the Lucas strings $L_{n,3}$.
Further, the Gray codes of Lucas strings are well-understood, and thus we use
them for the proof presented here.

For our purposes, the cycle on $n\geq 3$ vertices has vertex set
$V(C_{n})=\\{0,1,\ldots,n-1\\}$ and edge set $\\{ij:i-j\equiv\pm
1\pmod{n}\\}$. We encode $X\subseteq V(C_{n})$ as an $n$-digit binary string,
$x_{0}x_{1}\cdots x_{n-1}$, by setting $x_{i}=1$ if and only if $i\in X$,
$0\leq i\leq n-1$. It follows that $X\subseteq V(C_{n})$, encoded by the
binary string $x_{0}x_{1}\cdots x_{n-1}$, is a dominating set of $C_{n}$ if
and only if $x_{i-1}x_{i}x_{i+1}\neq 000$ for all $i$, $0\leq i\leq n-1$,
where subscripts are taken modulo $n$. If $X$ and $Y$ are dominating sets of
$C_{n}$, and are represented by binary strings $x_{0}x_{1}\cdots x_{n-1}$ and
$y_{0}y_{1}\cdots y_{n-1}$, respectively, then $X$ and $Y$ are adjacent in
$\mathcal{D}(C_{n})$ if and only if $x_{0}x_{1}\cdots x_{n-1}$ and
$y_{0}y_{1}\cdots y_{n-1}$ differ in exactly one bit.

The set of Lucas strings of length $n$ and order $p\geq 1$, denoted $L_{n,p}$,
is the set of binary strings of length $n$ that have no $p$ consecutive ones
when the strings are considered circularly. In particular, the set of Lucas
strings of length $n$ and order $3$ is

$L_{n,3}=\\{x_{0}\cdots x_{n-1}~{}|~{}x_{i-1}x_{i}x_{i+1}\neq 111\mbox{ for
}0\leq i\leq n-1\mbox{ subscripts mod }n\\},$

and is the set of bitwise complements of elements of $V(C_{n})$.

Baril and Vajnovszki [2] construct an ordering of the elements of $L_{n,p}$
called a minimal change list (see [2]), denoted by $\mathcal{L}_{n,p}$. They
prove $\mathcal{L}_{n,p}$ is a Gray code if and only if $n\not\equiv
0\pmod{(p+1)}$; that is, every pair of consecutive strings of
$\mathcal{L}_{n,p}$ differs in exactly one bit. Let
$\widehat{\mathcal{L}}_{n,p}$ denote the sequence obtained by taking bitwise
complements of the strings of $\mathcal{L}_{n,p}$, and note that
$\mathcal{L}_{n,p}$ is a Gray code if and only if
$\widehat{\mathcal{L}}_{n,p}$ is a Gray code. Since a Gray code of
$\widehat{\mathcal{L}}_{n,3}$ corresponds precisely to a Hamilton path in
$\mathcal{D}(C_{n})$, this proves the following.

######  Theorem 5.

For all integers $n\geq 3$, $\mathcal{D}(C_{n})$ has a Hamilton path if and
only if $n\not\equiv 0\pmod{4}$.

A computationally inefficient construction of $\mathcal{L}_{n,p}$ (though not
the construction used in the proof) is described in [2], and can easily be
modified to directly construct a Hamilton path of $\mathcal{D}(C_{n})$
whenever $n\not\equiv 0\pmod{4}$. We illustrate this construction in Example
1.

######  Example 1.

Let $n=5$. To construct a Hamilton path of $\mathcal{D}(C_{5})$, begin with
the reflected Gray code order (due to Frank Gray [8]) of the set of all binary
strings of length five. The strings are organized in Figure 3(a) to be read
from top to bottom and left to right. Next, delete any string
$x_{0}x_{1}x_{2}x_{3}x_{4}$ that has $x_{i-1}x_{i}x_{i+1}=000$ for $0\leq
i\leq 4$, subscripts modulo $4$.

00000 | 01100 | 11000 | 10100
---|---|---|---
00001 | 01101 | 11001 | 10101
00011 | 01111 | 11011 | 10111
00010 | 01110 | 11010 | 10110
00110 | 01010 | 11110 | 10010
00111 | 01011 | 11111 | 10011
00101 | 01001 | 11101 | 10001
00100 | 01000 | 11100 | 10000
(a)

|  |  | 10100
---|---|---|---
| 01101 | 11001 | 10101
| 01111 | 11011 | 10111
| 01110 | 11010 | 10110
| 01010 | 11110 | 10010
00111 | 01011 | 11111 | 10011
00101 | 01001 | 11101 |
|  | 11100 |
(b)

Figure 3: Constructing a Hamilton path in $\mathcal{D}(C_{5})$.

The reader can easily verify that remaining strings, shown in Figure 3(b), are
still a Gray code when read from top to bottom and left to right, and hence
describe a Hamilton path in $\mathcal{D}(C_{5})$.

##  5 Further results

Corollary 8 applies more generally and can be used to prove the existence of
Hamilton paths in classes of dominating graphs that are built up using
dominating graphs that are known to have Hamilton paths. These include
complete graphs, paths, cycles $C_{n}$ when $n\not\equiv 0\pmod{4}$, certain
complete bipartite graphs (Theorem 3), and trees (Theorem 4). We include one
example.

For any graph $H$, we say that $H$ is reducible to subgraph $H^{\prime}$ if
$H^{\prime}$ can be obtained from $H$ by applying a sequence of Operations I
and II as described in Section 2. Suppose $G$ is a unicyclic graph whose
unique cycle $C_{n}$ has length $n\geq 3$, where $n\not\equiv 0\pmod{4}$. Let
$V(C_{n})=\\{v_{1},v_{2},\ldots,v_{n}\\}$, and let $T_{i}$ be the component (a
tree) of $G-E(C_{n})$ containing $v_{i}$ for some $i$, $1\leq i\leq n$. If
$T_{i}$ is reducible to $v_{i}$ for each $i$, $1\leq i\leq n$, then by Theorem
5 and Corollary 8, $\mathcal{D}(G)$ has a Hamilton path.

## Acknowledgements

This project started at the Women in Graph Theory and its Applications (WIGA)
Workshop at the Institute for Mathematics and its Applications in 2019. WIGA
is a research network of the AWM, with support provided by the AWM ADVANCE
Research Communities Program (funded by NSF-HDR-1500481, Career Advancement
for Women Through Research-Focused Networks). We gratefully acknowledge the
support of the AWM, NSF and IMA.

We also thank Torsten Mütze for bringing our attention to the work of Baril
and Vajnovszki [2].

## References

  * [1] K. Adaricheva, C. Bozeman, N.E. Clarke, R. Haas, M.E. Messinger, K. Seyffarth and H. Smith, Reconfiguration graphs for dominating sets, Chapter 6 in Research Trends in Graph Theory and Applications, D. Ferrero, L. Hogben, S.R. Kingan and G.L. Matthews Eds., Springer International Publishing (2021), DOI https://doi.org/10.1007/978-3-030-77983-2.
  * [2] J-L. Baril and V. Vajnovszki, Minimal change list for Lucas strings and some graph theoretic consequences. Theoretical Computer Science 346 (2005) 189–199.
  * [3] J.A. Bondy and U.S.R. Murty, Graph Theory. GTM 244, Springer, Berlin (2008).
  * [4] A. Brouwer, P. Csorba, and L. Schrijver, The number of dominating sets of a finite graph is odd, preprint (2009) https://www.win.tue.nl/~aeb/preprints/domin4a.pdf.
  * [5] M. Cavers and K. Seyffarth, Reconfiguring vertex colourings of 2-trees, Ars Math. Contemp. 17(2) (2019) 653–698.
  * [6] M. Celaya, K. Choo, G. MacGillivray and K. Seyffarth, Reconfiguring $k$-colourings of complete bipartite graphs, Kyungpook Math. J. 56 (2016) 647–655.
  * [7] K. Choo and G. MacGillivray, Gray code numbers for graphs, Ars Math. Contemp. 4(1) (2011) 125–139.
  * [8] F. Gray, Pulse code communication, US Patent 2632058, 1953.
  * [9] R. Haas and K. Seyffarth, The $k$-dominating graph, Graphs and Combin. 30 (2014) 609–617.
  * [10] N. Nishimura, Introduction to reconfiguration, Algorithms 11(4), 52 (2018).
  * [11] C.M. Mynhardt and S. Nasserasr, Reconfiguration of colourings and dominating sets in graphs (2020). In: F. Chung, R. Graham, F. Hoffman, L. Hogben, R.C. Mullin and D.B. West, eds. 50 years of combinatorics, graph theory, and computing, Florida, CRC Press, 171–187.
  * [12] T. Mütze, Combinatorial Gray codes – an updated survey, in preparation.