# Distinct Quantum States Can Be Compatible with a Single State of
Reality111This article was published by the American Physical Society under
the terms of the Creative Commons Attribution 3.0 License. Further
distribution of this work must maintain attribution to the authors and the
published article’s title, journal citation (PRL 109, 150404 (2012)), and DOI
(10.1103/PhysRevLett.109.150404).

Peter G. Lewis<EMAIL_ADDRESS>Controlled Quantum Dynamics Theory Group,
Imperial College London, London SW7 2AZ, United Kingdom  David Jennings
Controlled Quantum Dynamics Theory Group, Imperial College London, London SW7
2AZ, United Kingdom  Jonathan Barrett  Department of Mathematics, Royal
Holloway, University of London, Egham Hill, Egham TW20 0EX, United Kingdom
Terry Rudolph  Controlled Quantum Dynamics Theory Group, Imperial College
London, London SW7 2AZ, United Kingdom

###### Abstract

Perhaps the quantum state represents information about reality, and not
reality directly. Wave function collapse is then possibly no more mysterious
than a Bayesian update of a probability distribution given new data. We
consider models for quantum systems with measurement outcomes determined by an
underlying physical state of the system but where several quantum states are
consistent with a single underlying state—i.e., probability distributions for
distinct quantum states overlap. Significantly, we demonstrate by example that
additional assumptions are always necessary to rule out such a model.

Broadly speaking, physicists today view the quantum state in one of two ways:
in correspondence with the real physical state of affairs or as representing
only an agent’s knowledge or information about some aspect of the physical
situation. The latter ‘epistemic’ viewpoint is primarily motivated by the
obvious parallel between the quantum process of instantaneous wavefunction
collapse, and the classical procedure of instantaneous updating of a
probability distribution, both of which occur upon the acquisition of
information regarding the outcome of a measurement process. The epistemic view
has a long history of illustrious advocates Einstein et al. (1935); Popper
(1967); BALLENTINE (1970); Peierls (1979); Jaynes (1980); Zeilinger A. (1999);
Caves et al. (2002); Spekkens (2007). In recent times a research programme has
arisen aimed at not only philosophically justifying the epistemic view, but
potentially deriving quantum theory from more primitive considerations about
information and/or Bayesian reasoning Brukner and Zeilinger (2001); Fuchs
(2010); Spekkens (2007); Leifer (2006); Leifer and Spekkens (2011, 2011);
Barnum and Wilce (2009); Hardy (2001); Barrett (2007).

At least two versions of the epistemic view can be distinguished. One is
operational: the quantum state represents information about which outcome will
occur if a measurement is performed on the system. Measurement itself is
treated as a primitive. The other is that the quantum state represents
information about some underlying physical state of the system, where this
underlying state need not be described by quantum theory.

In his 1935 letter to Schrödinger, in an attempt to explain what he really
meant in the EPR paper, Einstein writes (Einstein, ; Howard, 2006, p. 26):

> But then for the same [real] state of [the system] there are two (in general
> arbitrarily many) equally justified $\Psi$, which contradicts the hypothesis
> of a one-to-one or complete description of the real states.

Einstein came to this conclusion, which he termed ‘incompleteness’ of the
quantum state, using an argument based on what we now call (following
Schrödinger Schrödinger (1935)) _steering_ Harrigan and Spekkens (2010). Note
that the question he raises here is _not_ whether there are multiple states of
reality associated with a single wavefunction (one possible type of
incompleteness), but rather whether there are multiple wavefunctions
associated with a single real state. A natural way to understand this is as an
expression of the second kind of epistemic view above—that a quantum state
represents an agent’s information about an underlying reality, but is not part
of that reality itself.

Unfortunately, as shown later by Bell Bell (1966) Einstein’s specific argument
for incompleteness was based on a false premise (locality). However, a
question that stands on its own and is the topic of this article remains: is
it even mathematically possible to find an embedding of quantum theory in some
deeper theory where the quantum states are not always uniquely determined
given the underlying physical state? Following Harrigan and Spekkens (2010),
we refer to such a possibility as a $\psi$-_epistemic_ interpretation of the
quantum state.

Recently, a no-go theorem was proven Pusey  _et al._ (2012) showing that a
$\psi$-epistemic interpretation is impossible. It is important to note that a
key assumption of the argument is _preparation independence_ —situations where
quantum theory assigns independent product states are presumed to be
completely describable by independently combining the two purportedly deeper
descriptions for each system. Here, we will show via explicit constructions
that without this assumption, $\psi$-epistemic models can be constructed with
all quantum predictions retained. Hence, we show that not only is the
‘preparation independence’ assumption of that particular no-go theorem
necessary, but also any similar no-go theorem will require non-trivial
assumptions beyond those required for a well-formed ontological model.

One of the most compelling motivations for exploring the $\psi$-epistemic view
is the amazing range of phenomena, normally considered uniquely quantum, that
can be derived by imposing only a simple principle restricting an agent’s
knowledge about a presumed underlying reality Spekkens (2007); Hardy (1999);
Bartlett  _et al._ (2011). It is clear that the primary reason these theories
do manage to reproduce so many quantum-like phenomena is that the states of
knowledge (probability distributions) overlap on a non-trivial subset of the
underlying space of ‘hidden’ states, even when the agent’s knowledge is
maximal (the equivalent of a quantum pure state).

These toy theories do not, however, reproduce _all_ quantum states and
measurement statistics. About such theories which do reproduce all of quantum
theory much less is known—the main examples and constraints are outlined in
Harrigan and Rudolph (2007). In Hardy (2004) Hardy showed that the underlying
mathematical space of real states on which such theories are defined—the
‘ontic state’ space—must have cardinality at least that of the integers.
Spekkens Spekkens (2005) showed the models must be _preparation contextual_ in
addition to measurement contextual Kochen and Specker (1967). The manifold
dimension of the ontic state space was shown by Montina Montina (2008) to be
necessarily exponential assuming that the dynamics of the ontic states is
Markovian; he then went on to show the intriguing result that it is possible
to reduce the manifold dimension by one Montina (2011, 2011). This latter
construction results in probability distributions that intersect in the ontic
state space, however they do so only on a set of measure 0. The question of
economic representation of finite data in such models Hardy (2001); Galvão
(2009); Dakić  _et al._ (2008); Wehner  _et al._ (2008) has also received some
attention.

In another pair of recent works Colbeck and Renner (2011a, b), Colbeck and
Renner have argued that, given additional assumptions of experimenters’ free
choice in choosing measurement settings and no superluminal signaling of the
choice at the ontic level, the ontic states must be in one-to-one
correspondence with the quantum states. The models of the present Letter are
explicitly constructed for single systems only and, if applied to systems
composed of multiple separated subsystems, would involve superluminal
influences of measurement choices upon ontic variables. Hence, our results are
consistent with those of Colbeck and Renner (2011a, b).

Formal statement of the problem.–Following Harrigan and Spekkens (2010), an
_ontological model_ for a quantum system defines a measure space $\Lambda$,
the elements $\lambda$ of which are termed _ontic states_. These should be
thought of as the underlying physical states that a system can be in at a
given time. A pure quantum state $|\psi\rangle$ corresponds to an equivalence
class of experimental preparations, and is represented within an ontological
model as a probability distribution $\mu_{\psi}(\lambda)$ over $\Lambda$. The
distribution $\mu_{\psi}$ is called an epistemic state. It represents the
information that an agent has about the ontic state of a system, given that it
was prepared in a particular way. Dynamics correspond to trajectories of ontic
states through $\Lambda$, and these map to dynamical changes in the
probability distributions over $\Lambda$. This setting includes the standard
Hilbert space description through the trivial assignment of $\Lambda$ as the
complex projective space $CP^{d-1}$ (the boundary of the quantum state space),
and $\mu_{\psi}(\lambda)$ being a delta-function distribution centred at
$\lambda=|\psi\rangle\langle\psi|$ Beltrametti and Bugajski (1995). It is for
this reason the term ‘ontic’ is used—as opposed to ‘hidden’, for example.

Throughout, we shall consider only projective measurements on a finite
$d$-dimensional quantum system, described as a string of rank-1 projectors
$\Phi=\\{|\phi_{0}\rangle\langle\phi_{0}|,\cdots,|\phi_{d-1}\rangle\langle\phi_{d-1}|\\}$,
where $\sum_{k}|\phi_{k}\rangle\langle\phi_{k}|=\mathbbm{1}$. If a measurement
is performed, the probabilities for different outcomes are defined by the
ontic state $\lambda$ of the system. Hence each measurement is associated with
a set of $d$ _response functions_
$\\{\xi_{\phi_{k}}:\Lambda\rightarrow[0,1]\\}$, where
$\xi_{\phi_{k}}(\lambda)$ is the probability of obtaining the outcome
$|\phi_{k}\rangle\langle\phi_{k}|$ when the ontic state of the system is
$\lambda$. The response functions are positive semi-definite and normalized so
that $\sum_{k}\xi_{\phi_{k}}(\lambda)=1,\forall\lambda$. If the
$\xi_{\phi_{k}}(\lambda)$ take values only in $\\{0,1\\}$ the model is
_deterministic_. By the Kochen-Specker theorem Kochen and Specker (1967), a
deterministic ontological model for a quantum system must be measurement
contextual Harrigan and Rudolph (2007) if the system has dimension $d\geq 3$.
This means that the response function $\xi_{\phi_{k}}$ depends on the complete
set of co-measured projectors in $\Phi$. We do not indicate this dependence
for notational simplicity.

An ontological model is successful in explaining quantum measurement
statistics for measurement $\Phi$ and preparation $|\psi\rangle$ if and only
if it is the case that $\forall k$:

$\displaystyle\int_{\Lambda}\xi_{\phi_{k}}(\lambda)\mathrm{d}\mu_{\psi}$
$\displaystyle=\int_{\Lambda}\mu_{\psi}(\lambda)\xi_{\phi_{k}}(\lambda)\mathrm{d}\lambda=|\langle\phi_{k}|\psi\rangle|^{2}.$
(1)

$\Lambda$$\Lambda$$\mbox{Supp}\,(\mu_{\psi})$$\mbox{Supp}\,(\mu_{\phi})$$\mathcal{E}$
Figure 1: Schematic of two ontic state spaces in different ontological models.
The supports of epistemic states associated with four quantum states are
shown. In (a) each ontic state is in the support of the epistemic state for at
most one $\psi$: the model is $\psi$-ontic. In (b) those ontic states in the
highlighted ‘epistemic region’ $\mathcal{E}$ on the right do not uniquely
identify a quantum state, and could result from either of the associated
preparation procedures: the model is $\psi$-epistemic.

With these basic ingredients in place, an ontological model is
$\psi$-epistemic if at least two distinct quantum states $|\psi_{1}\rangle$
and $|\psi_{2}\rangle$ are described by distributions $\mu_{\psi_{1}}$ and
$\mu_{\psi_{2}}$ such that the intersection of their supports has non-zero
measure, shown schematically in Fig. 1. An ontological model is _$\psi$
-ontic_ otherwise Harrigan and Spekkens (2010); Spekkens (2005). The idea here
is that in a $\psi$-ontic model, the quantum state is uniquely determined by
the ontic state $\lambda$, since for any $\lambda$, there is only one
$|\psi\rangle$ such that $\lambda$ is contained in the support of
$\mu_{\psi}$. In this case, although the quantum state $|\psi\rangle$ plays an
epistemic role in defining a distribution $\mu_{\psi}$, the quantum state is
also a function of the ontic state, hence can justifiably be thought of as a
physical property of the system. Informally, the whole of the quantum state
$|\psi\rangle$ is ‘written into’ the real state of affairs.

In a $\psi$-epistemic model, on the other hand, there are at least some
circumstances in which two different quantum states describe systems in the
same ontic state $\lambda$. In this case, it is defensible to claim that the
quantum state ‘merely’ represents an agent’s information. A stronger
definition of the term $\psi$-epistemic would require that for _any_ non-
orthogonal states, $|\psi_{1}\rangle$ and $|\psi_{2}\rangle$, the
distributions $\mu_{\psi_{1}}$ and $\mu_{\psi_{2}}$ overlap. In this Letter,
we stick with the weaker definition above.

_The original Bell model.–_ As a counterexample to ‘von-Neumann’s silly
assumption’ Bell Bell (1966) described a simple ontological model capable of
describing a quantum system of dimension $d$. The ontic state space consists
of pairs $(|\lambda\rangle,x)$, where $|\lambda\rangle$ is an element of
$CP^{d-1}$ and $x$ is an element of the interval $[0,1]$. For the moment
consider $d=2$. The ontic state space is then isomorphic to
$\Lambda=S^{2}\times[0,1]$, where $S^{2}$ is the two-dimensional Bloch sphere.
The quantum state $|\psi\rangle$ corresponds to a distribution
$\mu_{\psi}(\hat{\lambda},x)=\delta(\hat{\lambda}-\hat{\psi})$, where the
convention here, and in what follows, is to denote the unit Bloch vector
associated to $|\psi\rangle$ as $\hat{\psi}$. This choice of distribution is
uniform over the subset $\\{(\hat{\psi},x):0\leq x\leq 1\\}$. The model is
deterministic, with response functions given by

$\displaystyle\xi_{\phi_{k}}(\hat{\lambda},x)$ $\displaystyle=$
$\displaystyle\Theta\left[(|\langle\lambda|\phi_{0}\rangle|^{2}-x)(-1)^{k}\right],$
(2)

where $\Theta$ is the Heaviside step function. For a projective measurement
outcome $|\phi\rangle\langle\phi|$ and a quantum state $|\psi\rangle$, the
Born rule is satisfied since

$\displaystyle\int\mathrm{d}\hat{\lambda}\mathrm{d}x\,\,\mu_{\psi}(\hat{\lambda},x)\xi_{\phi}(\hat{\lambda},x)=|\langle\psi|\phi\rangle|^{2}.$
(3)

Note—as Bell did—that there are many possible choices for the response
functions that would work equally well. The only requirement is that the
support over the subset $\\{(\hat{\lambda},x):0\leq x\leq 1\\}$ has measure
equal to the probability occurring in the Born rule; how this support is
distributed is entirely arbitrary.

_A $\psi$-epistemic modification of the Bell model for a qubit.–_The Bell
model is $\psi$-ontic, since no two epistemic states, corresponding to
distinct quantum states, overlap. A different ontological model for qubit
systems was described by Kochen and Specker Kochen and Specker (1967), which
is $\psi$-epistemic. To date, however, no one has extended Kochen and
Specker’s model to systems of higher dimension than two Rudolph (2006). This
section shows how the Bell model can be modified in order to obtain a
$\psi$-epistemic model for qubits. Later, this model is extended to obtain a
$\psi$-epistemic model for quantum systems of arbitrary finite dimension.

A simple visualization of the ontic state space $\Lambda$ as an annulus with
$\hat{\lambda}$ specifying the direction, and $x$ the radial distance is
depicted in Fig. 2(a). Let $\hat{z}$ correspond to the north pole of the Bloch
sphere, and let $\hat{\lambda}\cdot\hat{z}=\cos(\theta_{\lambda})$, where
$\theta_{\lambda}$ is the polar angle of the Bloch vector $\hat{\lambda}$.
Label the upper ($\theta_{\lambda}<\pi/2$) hemisphere ${\cal R}_{0}$ and the
lower ($\theta_{\lambda}>\pi/2$) hemisphere ${\cal R}_{1}$. Given a projective
measurement
$\Phi=\\{|\phi_{0}\rangle\langle\phi_{0}|,|\phi_{1}\rangle\langle\phi_{1}|\\}$,
assume that the outcomes are labelled such that
$|\langle\phi_{0}|z\rangle|^{2}\geq|\langle\phi_{1}|z\rangle|^{2}$.

$\hat{\phi}_{0}$$\hat{\psi}$$\mbox{Supp}\,(\xi_{\phi_{0}})$$\mbox{Supp}\,(\xi_{\phi_{1}})$$\hat{\phi}_{1}$
(a)

$\hat{\psi}$${\cal E}_{0}$${\cal E}_{1}$${\cal R}_{0}$${\cal R}_{1}$ (b)

Figure 2: (a) Unmodified Bell model ontic state space along with supports of a
response function for outcome $\hat{\phi_{0}}$ (green), $\hat{\phi_{1}}$
(blue) and epistemic state $\mu_{\psi}$ (red line). The inner circle is the
surface of the Bloch sphere, the dashed line indicates it also corresponds to
$x=0$. The outer solid circle corresponds to $x=1$. (b) Modified Bell model,
showing the subsets ${\cal E}_{0}$ and ${\cal E}_{1}$. Any probability weight
that $\mu_{\psi}$ gives to ontic states within ${\cal E}_{0}$ can be
redistributed over ${\cal E}_{0}$.

With response functions defined as in Eq. (2), the ontic states in the set

${\cal E}_{0}=\left\\{(\hat{\lambda},x):\hat{\lambda}\in{\cal R}_{0}\mbox{ and
}0\leq x<(1-\sin\theta_{\lambda})/2\right\\}$ (4)

all result in the $\hat{\phi}_{0}$ outcome for any measurement $\Phi$.
Similarly, those in the set

${\cal E}_{1}=\left\\{(\hat{\lambda},x):\hat{\lambda}\in{\cal R}_{1}\mbox{ and
}(1+\sin\theta_{\lambda})/2<x\leq 1\right\\}$ (5)

all result in the $\hat{\phi}_{1}$ outcome. These sets are illustrated in Fig.
2(b).

In order to construct a $\psi$-epistemic model, note that if an epistemic
state $\mu_{\psi}$ assigns non-zero probability to the subset ${\cal E}_{0}$,
then this much probability weight can be redistributed over ${\cal E}_{0}$
without changing the Born rule statistics. This is because ontic states in
${\cal E}_{0}$ behave identically to one another, as far as predictions for
quantum measurement outcomes go. Similarly ${\cal E}_{1}$. Hence define a
modified Bell model such that for $\hat{\psi}\in{\cal R}_{0}$,

$\mu_{\psi}(\hat{\lambda},x)=\delta(\hat{\lambda}-\hat{\psi})\Theta\left(x-\frac{1}{2}(1-\sin\theta_{\psi})\right)\\\
+\frac{1}{2}(1-\sin\theta_{\psi})\mu_{{\cal E}_{0}}(\hat{\lambda},x)$ (6)

where $\theta_{\psi}$ is the polar angle of $\hat{\psi}$, and $\mu_{{\cal
E}_{0}}$ is essentially arbitrary but can be taken to be the uniform
distribution over ${\cal E}_{0}$. A similar expression defines $\mu_{\psi}$
for states with $\hat{\psi}\in{\cal R}_{1}$.

The modified Bell model still reproduces the Born rule, but now the model is
$\psi$-epistemic. Any two quantum states in the same hemisphere are described
by distributions that overlap, either in ${\cal E}_{0}$ or in ${\cal E}_{1}$.
The preparation of an ontic state from either of these regions does not reveal
a unique quantum state, but only reveals in which hemisphere the quantum state
resides.

_$\psi$ -epistemic modification in higher dimensions.–_Here, we modify the
Bell model to produce a $\psi$-epistemic model for arbitrary finite dimension.
The ontic state space for the $d$-dimensional Bell model is
$\Lambda=CP^{d-1}\times[0,1]$. The distribution corresponding to a quantum
state $|\psi\rangle$ is given by
$\mu_{\psi}(|\lambda\rangle,x)=\delta(|\lambda\rangle-|\psi\rangle)$. Response
functions for a measurement $\Phi$ are defined such that $\xi_{\phi_{k}}$ has
support of length $|\langle\phi_{k}|\lambda\rangle|^{2}$ on the line segment
$\\{(|\lambda\rangle,x):0\leq x\leq 1\\}$. Up to this constraint the response
functions are arbitrary. This model is $\psi$-ontic since the delta functions
do not overlap for distinct $|\psi\rangle$.

In order to construct a $\psi$-epistemic model, fix an arbitrary preferred
state $|0\rangle$. For each measurement $\Phi$, assume that the outcomes are
ordered such that
$|\langle\phi_{0}|0\rangle|^{2}\geq|\langle\phi_{1}|0\rangle|^{2}\geq\cdots\geq|\langle\phi_{d-1}|0\rangle|^{2}$.
Fix the response functions so that

$\xi_{\phi_{k}}(|\lambda\rangle,x)=1\quad\mathrm{if}\quad\sum_{i=0}^{k-1}|\langle\lambda|\phi_{i}\rangle|^{2}\leq
x<\sum_{i=0}^{k}|\langle\lambda|\phi_{i}\rangle|^{2}$ (7)

and

$\xi_{\phi_{k}}(|\lambda\rangle,x)=0\quad\mathrm{otherwise}.$ (8)

In Equation (7), $\sum_{i=1}^{k-1}|\langle\lambda|\phi_{i}\rangle|^{2}$ is
taken to be $0$ when $k=0$. For completeness, let us specify that for $x=1$,
$\xi_{\phi_{k}}(|\lambda\rangle,x)=1$ iff $k=d-1$.

Now the aim is to define a subset ${\cal E}_{0}$ of $\Lambda$, such that ontic
states in ${\cal E}_{0}$ predict the same outcomes for all measurements. To
this end, note that $|\langle\phi_{0}|0\rangle|^{2}\geq 1/d$. Given this, it
is easy to show that if $|\langle\lambda|0\rangle|^{2}>\frac{d-1}{d}$, then
$|\langle\phi_{0}|\lambda\rangle|^{2}>0$. For arbitrary $|\chi\rangle$, let

$z(|\chi\rangle)=\inf_{|\phi\rangle:|\langle\phi|0\rangle|^{2}\geq
1/d}|\langle\phi|\chi\rangle|^{2},$ (9)

where an explicit expression is easily found but not needed. Define

${\cal
E}_{0}=\left\\{(|\lambda\rangle,x):|\langle\lambda|0\rangle|^{2}>\frac{d-1}{d}\mbox{
and }0\leq x<z(|\lambda\rangle)\right\\}.$ (10)

Any ontic state $\lambda\in{\cal E}_{0}$ has the property that whatever
measurement is performed, the outcome is $|\phi_{0}\rangle\langle\phi_{0}|$.
The epistemic states can therefore be modified as above to produce a
$\psi$-epistemic model. Informally, the idea is the same: any probability that
$\mu_{\psi}$ assigns to ontic states within the set ${\cal E}_{0}$ can be
redistributed over the whole of ${\cal E}_{0}$ without changing Born rule
statistics. More specifically, when $|\langle\psi|0\rangle|^{2}\leq(d-1)/d$,
let

$\mu_{\psi}(|\lambda\rangle,x)=\delta(|\lambda\rangle-|\psi\rangle),$ (11)

and when $|\langle\psi|0\rangle|^{2}>(d-1)/d$, let

$\mu_{\psi}(|\lambda\rangle,x)=\delta(|\lambda\rangle-|\psi\rangle)\Theta(x-z(|\psi\rangle))+z(|\psi\rangle)\mu_{{\cal
E}_{0}}(|\lambda\rangle,x),$ (12)

where, as above, $\mu_{{\cal E}_{0}}$ is arbitrary but could be taken to be
the uniform distribution over ${\cal E}_{0}$.

This model is clearly very contrived. A degree of symmetry could be restored
by postulating a preferred basis $|0\rangle,\ldots,|d-1\rangle$, instead of a
preferred state. If $|\langle\lambda|j\rangle|^{2}>(d-1)/d$ for some $j$, then
relabel measurement outcomes such that
$|\langle\phi_{0}|j\rangle|^{2}\geq|\langle\phi_{1}|j\rangle|^{2}\geq\cdots\geq|\langle\phi_{d-1}|j\rangle|^{2}$.
In this case $|\langle\phi_{0}|\lambda\rangle|^{2}>0$, and sets ${\cal E}_{j}$
can be defined in analogy with ${\cal E}_{0}$ above. For any state
$|\psi\rangle$ with $|\langle\psi|j\rangle|^{2}>(d-1)/d$, any probability
assigned to ontic states within ${\cal E}_{j}$ can be redistributed over
${\cal E}_{j}$. This results in a model that is ‘more epistemic’ than the one
above. It is an open question whether more natural models can be found.

_Discussion.–_ Our results are particularly pertinent given the recent no-go
theorem of Pusey  _et al._ (2012). The theorem shows that it is not possible
to construct $\psi$-epistemic models of quantum theory, given an assumption
that independent preparations produce uncorrelated ontic states. The present
Letter shows that $\psi$-epistemic models are possible if that assumption is
given up. None of these models is intuitive or motivated by physical
principles or considerations. The primary motivation for exploring the
possibility of $\psi$-epistemic models is to understand the formal limitations
of reproducing quantum theory from a deeper theory.

Such models may also play a useful role in other areas of quantum information.
The remarkable protocols of Toner and Bacon Toner and Bacon (2003) for
recovering the bipartite measurement statistics of a singlet state and
classical simulation of teleportation—using only one and two bits
(respectively) of classical communication—make use of shared randomness in a
way that lets the problem be recast in terms of correlated single qubit
ontological models that are $\psi$-epistemic. A related result has been
obtained by Montina Montina (2011), who has also put bounds on the classical
simulation cost for an arbitrary number of qubits.

There remain many open questions. In the models presented, it is not the case
that $\mu_{\psi}$ has non-zero overlap with $\mu_{\phi}$ for any pair of non-
orthogonal quantum states $|\psi\rangle$ and $|\phi\rangle$. Hence the models
do not satisfy the stronger definition of $\psi$-epistemic suggested above. It
would be interesting to establish whether such models exist. (Scott Aaronson
has recently combined some of the ideas that were presented in a preprint
version of this article with those of George Lowther to answer this question
in the affirmative; see Aaronson and Lowther (2006).)

The authors gratefully acknowledge support from the Engineering and Physical
Sciences Research Council (P.G.L., J.B., and T.R.), the Leverhulme Foundation
(T.R.) and the Royal Comission for the Exhibition of 1851 (D.J.).

## References

  * Einstein et al. (1935) A. Einstein, B. Podolsky, and N. Rosen, Physical Review 47, 777 (1935).
  * Popper (1967) K. R. Popper, in _Quantum Theory and Reality_ , edited by M. Bunge (Springer, 1967), chap. 1.
  * BALLENTINE (1970) L. E. Ballentine, Rev. Mod. Phys. 42, 358 (1970).
  * Peierls (1979) R. E. Peierls, _Surprises in Theoretical Physics_ (Princeton Universtiy Press, 1979), p. 32.
  * Jaynes (1980) E. T. Jaynes, _Foundations of Radiation Theory and Quantum Electrodynamics_ (Plenum, 1980).
  * Zeilinger A. (1999) A. Zeilinger, Physics Today 52, 2 (1999).
  * Caves et al. (2002) C. M. Caves, C. A. Fuchs, and R. Schack, Phys. Rev. A 65, 022305 (2002).
  * Spekkens (2007) R. W. Spekkens, Phys. Rev. A, 75, 032110 (2007).
  * Brukner and Zeilinger (2001) Č. Brukner and A. Zeilinger, Phys. Rev. A, 63, 022113 (2001).
  * Fuchs (2010) C. A. Fuchs, “QBism, the Perimeter of Quantum Bayesianism,” (2010), arXiv:1003.5209 [quant-ph].
  * Leifer (2006) M. S. Leifer, Phys. Rev. A, 74, 042310 (2006), arXiv:quant-ph/0606022.
  * Leifer and Spekkens (2011) M. S. Leifer and R. W. Spekkens, “Formulating quantum theory as a causally neutral theory of Bayesian inference,” (2011a), arXiv:1107.5849 [quant-ph].
  * Leifer and Spekkens (2011) M. S. Leifer and R. W. Spekkens, “A Bayesian approach to compatibility, improvement, and pooling of quantum states,” (2011b), arXiv:1110.1085 [quant-ph].
  * Barnum and Wilce (2009) H. Barnum and A. Wilce, “Information processing in convex operational theories,” (2009), arXiv:0908.2352 [quant-ph] .
  * Hardy (2001) L. Hardy, “Quantum theory from five reasonable axioms,” (2001), arXiv:quant-ph/0101012.
  * Barrett (2007) J. Barrett, Phys. Rev. A, 75, 032304 (2007).
  * (17) A. Einstein, Unpublished letter to E. Schrödinger, 19th June 1935, EA 22-047.
  * Howard (2006) D. Howard, “Revising the Einstein-Bohr dialogue,” online $<$http://www.nd.edu/$\sim$dhoward1/Revisiting the Einstein-Bohr Dialogue.pdf$>$ (2006).
  * Schrödinger (1935) E. Schrödinger, Proc. Cambridge Phil. Soc., 31 (1935).
  * Harrigan and Spekkens (2010) N. Harrigan and R. Spekkens, Foundations of Physics, 40, 125 (2010), ISSN 0015-9018, dOI: 10.1007/s10701-009-9347-0.
  * Pusey  _et al._ (2012) M. F. Pusey, J. Barrett, and T. Rudolph, Nat Phys advance online publication (2012), 10.1038/nphys2309.
  * Hardy (1999) L. Hardy, “Disentangling nonlocality and teleportation,” (1999), arXiv:quant-ph/9906123.
  * Bartlett  _et al._ (2011) S. D. Bartlett, T. Rudolph, and R. W. Spekkens, “Reconstruction of Gaussian quantum mechanics from Liouville mechanics with an epistemic restriction,” (2011), arXiv:1111.5057 [quant-ph].
  * Harrigan and Rudolph (2007) N. Harrigan and T. Rudolph, “Ontological models and the interpretation of contextuality,” (2007), arXiv:0709.4266 [quant-ph].
  * Hardy (2004) L. Hardy, Studies In History and Philosophy of Science Part B: Studies In History and Philosophy of Modern Physics, 35, 267 (2004), ISSN 1355-2198.
  * Spekkens (2005) R. W. Spekkens, Phys. Rev. A, 71, 052108 (2005).
  * Kochen and Specker (1967) S. Kochen and E. P. Specker, Journal of Mathematics and Mechanics, 17, 59 (1967).
  * Montina (2008) A. Montina, Phys. Rev. A, 77, 022104 (2008).
  * Montina (2011) A. Montina, Physics Letters A, 375, 1385 (2011a), ISSN 0375-9601.
  * Montina (2011) A. Montina, Phys. Rev. A, 83, 032107 (2011b).
  * Galvão (2009) E. F. Galvão, Phys. Rev. A, 80, 022106 (2009).
  * Dakić  _et al._ (2008) B. Dakić, M. Šuvakov, T. Paterek, and Č. Brukner, Phys. Rev. Lett., 101, 190402 (2008).
  * Wehner  _et al._ (2008) S. Wehner, M. Christandl, and A. C. Doherty, Phys. Rev. A, 78, 062112 (2008).
  * Colbeck and Renner (2011a) R. Colbeck and R. Renner, Nat. Commun. 2, 411 (2011a).
  * Colbeck and Renner (2011b) R. Colbeck and R. Renner, “Is a system’s wave function in one-to-one correspondence with its elements of reality?” (2011b), arXiv:1111.6597 [quant-ph] .
  * Beltrametti and Bugajski (1995) E. G. Beltrametti and S. Bugajski, Journal of Physics A: Mathematical and General, 28, 3329 (1995).
  * Bell (1966) J. S. Bell, Rev. Mod. Phys., 38, 447 (1966).
  * Rudolph (2006) T. Rudolph, “Ontological Models for Quantum Mechanics and the Kochen-Specker theorem,” (2006), arXiv:quant-ph/0608120v1.
  * Toner and Bacon (2003) B. F. Toner and D. Bacon, Phys. Rev. Lett., 91, 187904 (2003).
  * Montina (2011) A. Montina, Phys. Rev. A, 84, 042307 (2011c).
  * Werner (1989) R. F. Werner, Phys. Rev. A, 40, 4277 (1989).
  * Aaronson and Lowther (2006) S. Aaronson and G. Lowther, http://mathoverflow.net/questions/95537/psi-epistemic-theories-in-3-or-more-dimensions (2012).


HAM -HAM

# Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree

Brian Liu, Nathan Sheffield, Alek Westover

###### Abstract

We study the following generalization of the Hamiltonian cycle problem: Given
integers $a,b$ and graph $G$, does there exist a closed walk in $G$ that
visits every vertex at least $a$ times and at most $b$ times? Equivalently,
does there exist a connected $[2a,2b]$ factor of $2b\cdot G$ with all degrees
even? This problem is $\NP$-hard for any constants $1\leq a\leq b$. However,
the graphs produced by known reductions have maximum degree growing linearly
in $b$. The case $a=b=1$ — i.e. Hamiltonicity — remains -hard even in
$3$-regular graphs; a natural question is whether this is true for other $a$,
$b$.

In this work, we study which $a,b$ permit polynomial time algorithms and which
lead to $\NP$-hardness in graphs with constrained degrees. We give tight
characterizations for regular graphs and graphs of bounded max-degree, both
directed and undirected.

##  1 Introduction

###  1.1 Background and Previous Work

The Hamiltonian cycle problem asks, given a graph $G$, whether $G$ admits a
closed walk visiting every vertex exactly once. A classic result of Garey,
Johnson and Tarjan is that Hamiltonicity is -hard even in graphs of max degree
3, and in fact even in 3-regular graphs [GJT76].

In 1990, Broersma and Göbel proposed two variants of the Hamiltonian cycle
problem: for fixed $k$, is there a closed walk that visits each vertex exactly
$k$ times, or at least once and at most $k$ times, respectively? They showed
that for constant $k$, both of these problems are -hard [BG90]. Jackson and
Wormald subsequently proved that both problems remain -hard in $j$-connected
graphs for any constant $j$ [JW90]. These proofs extend to give hardness of
the following generalization:

######  Definition 1.

For fixed integers $1\leq a\leq b$, a graph $G$ is called $[a,b]\hHAM$ if
there exists a closed walk on $G$ that visits each vertex at least $a$ times
and at most $b$ times.

Being $[a,b]\hHAM$ can be considered as a graph factor problem. Letting
$2b\cdot G$ be the multigraph obtained by making $2b$ copies of each edge in
$G$, $G$ is $[a,b]\hHAM$ if and only if $2b\cdot G$ contains a spanning even
$[2a,2b]$ factor; that is, a connected subgraph containing all vertices of
$G$, with every degree even and in $[2a,2b]$. The equivalence of this
formulation follows from taking an Euler tour.

There is a substantial body of combinatorics work seeking sufficient
conditions for the existence of graph factors and walks; see Plummer’s survey
[Plu07], the book by Akiyama and Kano [AK11], or the survey by Kouider and
Vestergaard which focuses specifically on connected factors [KV05]. For
example, Gao and Richter showed that any $3$-connected planar graph is
$[1,2]\hHAM$ [GR94], and Schmid and Schmidt gave a polynomial-time algorithm
to find such a walk in which only the 3-separators are visited twice [SS18].
Several variants of the problem have also been consider from an algorithmic
complexity standpoint. Ganian et al consider the case where $a$ is nonconstant
in $n$, showing that $[a,a]\hHAM$ is $\NP$-hard for $a\leq
O(n^{1-\varepsilon})$, but in $\RP$ for $a\geq\Omega(n/\log n)$ [Gan+19].
Nishiyama et al show that there is a polynomial-time algorithm to determine
whether a graph has a walk visiting every vertex an odd number of times, but
that the problem becomes $\NP$-hard when each edge can be traversed at most
$3$ times [Nis+18].

In this work, we will study the complexity of $[a,b]\hHAM$ in regular graphs
and graphs of constant maximum degree. Prior papers have investigated degree
conditions sufficient to guarantee $[a,b]\hHAM$ — for instance Kouider and
Vestergaard showed that, for $a\geq 2$, any 2-connected graph with minimum
degree $an/(a+b)$ is $[a,b]\hHAM$ [KV04], and independent papers by Gao and
Richter, Jin and Li respectively showed that any $2$-connected graph with
maximum degree $2b-2$ is $[1,b]\hHAM$ [JL04, Kai+07]. However, to our
knowledge we are the first to consider the algorithmic complexity of
$[a,b]\hHAM$ in general bounded degree graphs.

###  1.2 Results

Our main results are tight characterizations for the hardness of $[a,b]\hHAM$
in regular graphs, graphs of bounded max-degree, and bounded max-degree
digraphs. Interestingly, the thresholds for which $a,b$ lead to $\NP$-hardness
are very different in each of these settings. In regular graphs, we find that
hardness is determined by the maximum visit count $b$ in comparison to the
degree $d$, where the parity of $d$ is very important:

######  1.

When restricted to $d$-regular graphs, $[a,b]\hHAM$ is -hard if either $d$ is
even and $b<d/2$, or $d$ is odd and $b<d$. Otherwise, $[a,b]\hHAM\in\P$.

In graphs of bounded max degree, we find instead that hardness is determined
by the ratio of $b$ to $a$ in comparison to the max degree $d$, and that $a=1$
is a special case:

######  2.

When restricted to graphs of maximum degree $d$, $[a,b]\hHAM$ is -hard if
either $a=1$ and $b<d$, or $a>1$ and $\frac{b}{a}<d-1$. Otherwise,
$[a,b]\hHAM\in\P$.

For directed graphs, $[a,b]\hHAM$ turns out to always be hard in graphs of
maximum degree $4$, and hard in graphs of maximum degree $3$ unless $a=b$ or
$b=1$:

######  3.

In directed graphs of maximum degree $3$, for $1\leq a\leq b$,
$[a,b]\hHAM\in\P$ if $a=b>1$, and $\NP$-hard otherwise.

######  4.

For all $b\geq a\geq 1$, $[a,b]\hHAM$ is $\NP$-hard in directed graphs of
maximum degree 4.

The hardness proofs for maximum degree digraphs easily extend to show hardness
in regular digraphs.

###  1.3 Preliminaries

##### Introducing Depletors

Now we introduce the notion of a depletor gadget which will be used in all of
our hardness reductions. We introduce this notion by showing that $[a,b]\hHAM$
is hard in unrestricted graphs.

######  Lemma 1 (Broersma, Göbel [BG90]).

In unrestricted graphs, for any constants $1\leq a\leq b$, $[a,b]\hHAM$ is
-hard.

###### Proof.

We reduce from $[1,1]\hHAM$ (i.e. the standard Hamiltonian cycle problem).
Given a graph $G$, we build a new graph $G^{\prime}$ by gluing to each vertex
$b-1$ triangles, as shown in Figure 1. In any $[a,b]\hHAM$ cycle each of these
triangles must be visited — this accounts for $b-1$ of the visits for each of
the vertices in $G$, so the rest of the walk when restricted to $G$ must be a
Hamiltonian cycle. For the other direction, note that it is possible to
satisfy the visit requirements of the each triangle by stepping up to it,
walking back and forth $a-1$ times, and then stepping back down, contributing
only $1$ additional visit to the vertex we attached the triangles to. So, if
$G$ is Hamiltonian then $G^{\prime}$ is $[a,b]\hHAM$. ∎

Figure 1: Reducing $[1,1]\hHAM$ to $[3,3]\hHAM$.

In general a depletor gadget is some small graph that we glue to the starting
graph $G$ that forces vertices to be visited many times. In 1, triangles are
serving as depletors, since they each contribute a visit to the vertex they’re
glued to. In future sections, we will need depletors with stronger properties,
such as forcing an attachment edge to be traversed many times.

##### Introducing Labellings

Given an $[a,b]\hHAM$ cycle, we can label each edge of the graph $G$ with the
number of times it’s traversed in the cycle. These labels satisfy the
following properties:

  * •

the sum of the labels on the edges adjacent to each vertex is an even number
at least $2a$ and at most $2b$, and

  * •

the subgraph on edges with non-zero labels is connected.

Now, given such a labeling, we could create a multigraph by including each
edge with multiplicity given by its label. Since all vertices in this
multigraph have even degree, we can (efficiently) find an Eulerian cycle in
the multigraph, which is then an $[a,b]\hHAM$ cycle in the original graph. So,
finding a labeling with these properties is equivalent to finding an
$[a,b]\hHAM$ cycle; this perspective will make the problem easier to reason
about.

##### A Technical Note

Finally, we remark that, throughout this paper, degree bounds will be assumed
to be greater than or equal to $3$. All problems we consider are trivial in
graphs of maximum degree $2$, and so we will refrain from mentioning this
special case. We will use “maximum degree” to refer to any upper bound on the
degrees of a graph. In particular, a graph with no degree larger than $d$ is a
max-degree $d$ graph even if it does not have a vertex achieving that degree.
In directed graphs, degree refers to the sum of in-degree and out-degree.

Another piece of notation that is important to note is that we will write
$x\mod y$ to denote the remainder when $x$ is divided by $y$ (as opposed to
the equivalence class $x+y\mathbb{Z}$).

##  2 Complexity characterization in $d$-regular graphs

###  2.1 Easiness

We claim that $[a,b]\hHAM$ can be solved in polynomial time for $d$-regular
graphs, as long as either $d$ is even and $b\geq d/2$, or $d$ is odd and
$b\geq d$. The reason for this is simple: the following two lemmas demonstrate
that _any_ connected $d$-regular graph is $[a,b]\hHAM$ for such $b$.

######  Lemma 2.

For even $d$, any $d$-regular graph is $[d/2,d/2]\hHAM$. For odd $d$, any
$d$-regular graph is $[d,d]\hHAM$.

###### Proof.

If $d$ is even, then the graph is Eulerian — taking an Euler tour will visit
every vertex exactly $d/2$ times. If $d$ is odd, we can duplicate all its
edges to get a $2d$-regular multigraph — an Euler tour in that multigraph
visits every vertex exactly $d$ times. ∎

Now we use Tutte’s two-factor theorem to extend 2 to more $[a,b]$.
Specifically, the form of Tutte’s two-factor theorem that we use is:

######  Fact 1.

If $H$ is a $2k$-regular multigraph, its edges can be partitioned into $k$
distinct $2$-factors (i.e. $2$-regular sub-multigraphs).

Using 1 we obtain:

######  Lemma 3 (Broersma, Göbel [BG90]).

If a graph $G$ is $[b,b]\hHAM$ for some $b$, then it’s also
$[b^{\prime},b^{\prime}]\hHAM$ for all $b^{\prime}>b$.

###### Proof.

Let $H$ be the multigraph corresponding to a $[b,b]\hHAM$ walk on $G$. This is
a $2b$-regular multigraph, so we can find a multigraph two-factor by Tutte’s
two-factor theorem. Duplicating all edges in that two-factor, we have a
multigraph corresponding to a $[b+1,b+1]\hHAM$ walk on $G$. Repeating this
process gives the desired claim. ∎

Since a $[b,b]\hHAM$ cycle is also an $[a,b]\hHAM$ cycle for $a<b$, we’ve
shown the easiness part of the claim.

###  2.2 Hardness

####  2.2.1 Depletors

The first step in the hardness argument is to construct depletors. We would
like a small structure that can always be part of an $[a,b]\hHAM$ cycle as
long as it’s visited at least once.

We will describe such a $d$-regular depletor for even $d$ with two attachment
edges and $2d$ vertices. Add an edge between $v_{i}$ and $v_{j}$ whenever
$(i-j)\mod 2d\in\\{-d/2,\dots,d/2\\}$. Now, cut the edges $(v_{2d},v_{3d/2})$
and $(v_{1},v_{d/2+1})$, and add the edge $(v_{3d/2},v_{d/2+1})$ — note that
this is in fact a new edge since

$(3d/2-d/2-1)\bmod 2d\not\in\\{-d/2,\dots,d/2\\}.$

So, if we add an edge leaving the gadget from each of $v_{2d}$ and $v_{1}$,
the construction will be $d$-regular.

Figure 2: Labellings corresponding to $[b,b]$ walks on 4-regular and 5-regular
depletors, respectively.

######  Lemma 4.

For any $b\geq a\geq 1$, there is a valid $[a,b]\hHAM$ traversal of this even-
regularity depletor in which each attachment edge is traversed exactly once.

###### Proof.

Assign each edge $(v_{i},v_{i+1})$ of the gadget to be traversed $b$ times,
and assign the edge $(v_{2d},v_{1})$ to be traversed $b-1$ times; see Figure
2. ∎

Note that this gadget required two attachment edges. This is a necessary
consequence of the regularity constraint: since $d$ is even, there must be an
even number of half-edges within the gadget, meaning that the number of edges
leaving the gadget must be even.

When $d$ is odd, we can construct a $d$-regular depletor needing only one
leaving edge. Start with the complete graph $K_{d+1}$, and then delete all
edges $(v_{i},v_{i+(d+1)/2})$ except for the edge $(v_{1},v_{(d+1)/2+1})$. At
this point, every vertex has degree $(d-1)$, except for $v_{1}$ and
$v_{(d+1)/2+1}$, which have degree $d$. So, we add a $(d+2)$-th vertex
$v^{*}$, with edges to every other vertex except $v_{1}$ and $v_{(d+1)/2+1}$,
and a single edge leaving the construction — note that the result is now
$d$-regular.

######  Lemma 5.

For any $b\geq 2$, there is a valid $[a,b]\hHAM$ traversal of this odd-
regularity depletor in which the attachment edge is traversed exactly twice.

###### Proof.

Assign all the edges in the loop passing through all vertices to be traversed
$b-1$ times, and then add one more traversal to the edges
$(v_{i},v_{(i+1)\bmod d+2})$; see Figure 2. ∎

####  2.2.2 Reductions

These depletor gadgets let us use the construction from 1 to resolve the case
of even $d$.

######  Lemma 6.

For even $d$, if $a\leq b<d/2$, then $[a,b]\hHAM$ is $\NP$-hard in $d$-regular
graphs.

###### Proof.

We reduce from $[1,1]\hHAM$ in $(d-2b+2)$-regular graphs, which is known to be
$\NP$-hard as long as $(d-2b+2)>2$ — i.e. as long as $b<d/2$. Given a
$(d-2b+2)$-regular graph $G$, we construct $G^{\prime}$ by attaching $(b-1)$
copies of the $d$-regular depletor of 4 to each vertex. Recall that this
depletor required two attachment edges, so $G^{\prime}$ is $d$-regular. But
now, note that in the process of visiting each depletor gadget once, each
vertex from $G$ must be visited at least $b-1$ times, leaving room for only
$1$ additional visit. So, if $G$ was not Hamiltonian, $G^{\prime}$ is not
$[a,b]$-Hamiltonian for any $a$. Conversely, if $G$ was Hamiltonian, then by 4
we can extend the Hamiltonian cycle to a $[b,b]\hHAM$ cycle by visiting each
depletor exactly once. ∎

This argument is not immediately sufficient for the case of odd regularity,
however. Applying the same construction would yield the following:

######  Lemma 7.

For odd $d$, if $a\leq b<d-1$, then $[a,b]\hHAM$ is -hard in $d$-regular
graphs.

To be tight with our easiness results, however, we would like to show hardness
of $[a,b]\hHAM$ when $b<d$. The gap here is coming from our base case: the
hard problem we have to reduce from in $3$-regular graphs is $[1,1]\hHAM$,
whereas we need to show that even $[1,2]\hHAM$ and $[2,2]\hHAM$ are hard.
Fortunately, a slightly more involved reduction closes this gap.

######  Lemma 8.

For odd $d$, if $a\leq d-1$, then $[a,d-1]\hHAM$ is -hard in $d$-regular
graphs.

###### Proof.

We reduce from $[1,1]\hHAM$ in $3$-regular graphs. Let $G$ be a $3$-regular
graph; we construct $G^{\prime}$ as follows:

  * •

Glue $d-3$ depletors to each vertex in $G$.

  * •

Trisect each of $G$’s original edges — that is, replace them with paths
containing $2$ intermediate nodes.

  * •

Glue $d-2$ depletors to each of the intermediate nodes just added.

Using the $d$-regular depletors of 5, this construction is $d$-regular. We
would like to show that $G^{\prime}$ is $[d-1,d-1]$ Hamiltonian if $G$ is
Hamiltonian, and otherwise not even $[1,d-1]$ Hamiltonian — this suffices to
prove the lemma.

Figure 3: Reduction from $[1,1]\hHAM$ in $3$-regular graphs to $[4,4]\hHAM$ in
$5$-regular graphs. Red outgoing edges represent depletors.

First, note that if you ignore the depletors, each intermediate node must be
visited exactly once, since the depletors contribute $d-2$ of the $d-1$
allowed visits. Thus, each edge gadget must be labeled either $1,1,1$ or
$2,0,2$; see Figure 4.

Figure 4: The two possible labelings of the edge gadget.

The depletors contribute $d-3$ visits to each of the original vertices, so
each has an additional label budget of only $4$; this means that for every
original vertex, exactly two of the three incident edge gadgets must be
labeled $1,1,1$. So, the edges of $G$ corresponding to $1,1,1$ edge gadgets in
$G^{\prime}$ form a 2-factor; see Figure 5. But now, suppose this $2$-factor
had multiple connected components. Since $2,0,2$ edges do not create
connectivity, this would mean that the labeling of $G^{\prime}$ was not
connected, and so couldn’t correspond to a $[1,d-1]\hHAM$ walk. Thus,
$G^{\prime}$ can be $[1,d-1]\hHAM$ only if $G$ had a connected 2-factor, i.e.
a Hamiltonian cycle.

Figure 5: The edge gadgets labeled $1,1,1$ must correspond to a Hamiltonian
path.

The reverse direction follows by the same logic: given a Hamiltonian cycle in
$G$, we label all edge gadgets corresponding to the cycle $1,1,1$ and all edge
gadgets not in the cycle $2,0,2$; visiting each depletor once gives a
$[d-1,d-1]\hHAM$ labeling.

∎

Combining the above lemmas gives a complete characterization of the hardness
of $[a,b]\hHAM$ in regular graphs.

######  Theorem 1.

When restricted to $d$-regular graphs, $[a,b]\hHAM$ is -hard if either $d$ is
even and $b<d/2$, or $d$ is odd and $b<d$. Otherwise, $[a,b]\hHAM\in\P$.

##  3 Complexity characterization in graphs of max-degree $d$

We now have a tight understanding of when $[a,b]\hHAM$ is hard in regular
graphs. If, instead, we just cared about graphs with constant maximum degree,
the hardness results would translate, but easiness would not. We show in this
section that in fact the true threshold for hardness in this setting looks
very different: complexity is determined not by $b$ but by the ratio
$\frac{b}{a}$.

For our easiness result, we will note that testing $[a,b]$-Hamiltonicity is
easy in trees, and then show that when $\frac{b}{a}\leq d-1$, for $a>1$, any
failure of $[a,b]$-Hamiltonicity is witnessed by a tree-like subgraph. To show
hardness, we will exploit a few low-degree vertices to construct and fine-tune
highly efficient depletor gadgets.

###  3.1 Easiness

First, we observe that without loss of generality an $[a,b]\hHAM$ walk never
traverses a given edge more than $2a$ times:

######  Lemma 9.

Let $G$ be a graph. If $G$ has an $[a,b]\hHAM$ labeling, it has such a
labeling with maximum label at most $2a$.

###### Proof.

Take such an $[a,b]\hHAM$ walk, and consider an edge with label more than
$2a$. Each of the vertices incident to that edge is therefore visited at least
$a+1$ times by the walk — so, if we subtract $2$ from the label of that edge,
each of them will still be visited at least $a$ times, and the labeling will
still be valid. ∎

Now, we give an algorithm for $[a,b]\hHAM$ in trees, which will be an
important component of our algorithm for $[a,b]\hHAM$ in general graphs.

######  Lemma 10.

Let $b\geq a\geq 1$, and let $G$ be a tree. There is a linear-time algorithm
to determine whether $G$ is $[a,b]\hHAM$.

###### Proof.

Arbitrarily root the tree. We will work from the bottom-up, recording for each
edge the set of label values that can extend to a valid labeling in the
subtree below it. In fact, we will show that for each edge $e$ the set of
labels for $e$ that can extend to a valid labelling in the subtree below $e$
is of the form $\left\\{\ell_{e},\ell_{e}+2,\ldots,u_{e}\right\\}$ for even
integers $\ell_{e},u_{e}$. Thus, it will suffice to record for each edge $e$
the minimum and maximum labels $\ell_{e},u_{e}$ which can extend to valid
labellings in the subtree below $e$.

Start by setting $\ell_{e}=2a,u_{e}=2b$ for each edge $e$ incident to a leaf
of the tree: these edges must be traversed at least $2a$ times in order to
visit the leaves $a$ times. Now we repeatedly apply the following process to
find $u_{e},\ell_{e}$ for all edges in the tree:

Find a vertex $v$ such that all edges in the subtree rooted at $v$ have been
labelled. Let $L_{v},U_{v}$ be the sum of $\ell_{e^{\prime}},u_{e^{\prime}}$
respectively over edges $e^{\prime}$ going down from $v$. Let $e$ be the edge
going up the tree from $v$. We claim that the valid labels for $e$ are
precisely the even numbers in the interval $[\ell_{e},u_{e}]$ defined by

$\ell_{e}=\max(2,2a-U_{v}),\quad u_{e}=2b-L_{v}.$

First we argue that labelling for $e$ must lie in this set; then we will argue
that any labels in this set can be extending to labellings on the subtree. The
label on $e$ must be even because all of the edges going down from $v$ have
even labels (by induction). The label on $e$ cannot be zero, or else the
labelling is not connected. The label on $e$ must be at least $2a-U_{v}$ or
else vertex $v$ is not visited enough times. The label on $e$ cannot be larger
than $2b-L_{v}$ or else vertex $v$ is visited too many times. It is clear that
for any even $k\in[\ell_{e},u_{e}]$, if we give $e$ label $k$, then there is a
compatible labelling of the subtree rooted at $v$.

If at any step in the process an edge $e$ is given $\ell_{e}>u_{e}$, then we
deduce that there is no valid labelling of the tree. Otherwise, the process
will terminate with every edge having $\ell_{e},u_{e}$ with $\ell_{e}\leq
u_{e}$. To finish our check of whether the tree is $[a,b]\hHAM$ we simply
iterate over all possible ways of assigning labels to the edges incident to
the root, taken from their corresponding allowed sets $[\ell_{e},u_{e}]\cap
2\mathbb{Z}$. If there is any combination of labels of the edges incident to
the root that satisfies the root, then by construction of the allowed label
sets, we can extend the labellings given to each $e$ incident to the root to
the entire subtree below $e$. Thus, we can label the entire tree. ∎

We now use this procedure for trees as part of an algorithm for $[a,b]\hHAM$
in general graphs in the case $a>1$. Afterwards we will analyze the case
$a=1$, which is simple but (somewhat surprisingly) meaningfully different from
the case $a>1$.

######  Lemma 11.

For any $d$ and any $b\geq a>1$ such that $\frac{b}{a}\geq(d-1)$, there exists
a polynomial-time algorithm to test whether a graph $G$ of max degree $d$ is
$[a,b]\hHAM$.

###### Proof.

The first step of the algorithm is to search for tree derivations. Call an
edge $e\in E(G)$ dangerous if it does not belong to any cycle in $G$ (the set
of dangerous edges can be compute easily using connectivity tests on modified
versions of the graph). The tree derivation stage will assign labels to all
dangerous edges.

The means of performing a derivation is exactly as described in 10. The set of
dangerous edges forms a forest, so for each tree in the forest we run the
algorithm from 10 to find an $[a,b]\hHAM$ labeling that satisfies all vertices
except possibly the root. If any of these tree derivations fail, $G$ cannot be
$[a,b]\hHAM$ — the failure of a tree derivation gives a set of vertices that
cannot be mutually satisfied under any labeling, since there can’t be any more
edges into this set.

Figure 6: The algorithm performs all tree derivations, then labels disjoint
cycles, then merges paths into those cycles, and finally labels all remaining
edges with $2$.

If none of these tree derivations fail, we have a labeling of all dangerous
edges that satisfies all vertices not involved in any cycle. Call a vertex
good if it’s involved in at least one cycle. The next step of our argument is
to show that, no matter what labeling we choose for the dangerous edges, there
is always an assignment to the remaining edges that visits each good vertex
between $a$ and $(d-1)a\leq b$ times, showing that $G$ is necessarily
$[a,b]\hHAM$ unless a tree derivation fails.

##### Existence of a labelling, given that tree derivations succeed

We now give a procedure which finds a labelling of the remainder of the graph
once all tree derivations have succeeded; we stress that we don’t actually run
this procedure in our algorithm, it is an analysis tool to demonstrate the
existence of a labelling. The procedure is as follows:

  * •

Find an arbitrary cycle in the graph, and label all of its edges with $a$.
Mark the vertices involved in that cycle happy.

  * •

While there remains a cycle involving only unhappy vertices, repeat the above
step with that cycle.

  * •

Now, suppose there still exists an unhappy good vertex. Since good vertices
are involved in cycles, there must exist a path that starts and ends in happy
vertices but otherwise contains only unhappy good vertices. (Here, we’re
allowing that “path” to potentially start and end at the same happy vertex —
this is a slight abuse of terminology.) Find such a path. If $a$ is even,
label all edges in the path with $a$. Otherwise, give the edges in the path
alternating labels of $a+1$ and $a-1$. Mark all vertices along the path happy.

  * •

Repeat the above step until all good vertices are happy. Then, label all
unlabeled edges of the graph with $2$.

Now we analyze the procedure. First, note that all edges are assigned nonzero
weight, so this construction is connected111This is the place where the
argument fails for $a=1$. In that case, the edges assigned $a-1$ would be
given zero weight, and so we wouldn’t ensure connectivity.. Labeling a full
cycle with $a$’s increases every vertex label sum by either $0$ or $2a$, and
all other labels used in this construction are even values, so this labeling
gives even sums into every vertex. So, the only point to argue is that every
vertex is given sum between $2a$ and $2b$. This holds for the non-good
vertices by virtue of the tree derivations succeeding. Now, note that for each
good vertex, at some point we label two of its incident edges either $a$ and
$a$ or $a+1$ and $a-1$. In either case, this ensures that they have total
weight at least $2a$. By 9, we can decrease all labels assigned while
performing tree derivations to be at most $2a$. Thus, the sum of the labels
incident to any good vertex is at most

$2a+(d-2)2a=(d-1)2a\leq 2b.$

∎

The final point to note in this section is the following, covering the $a=1$
case:

######  Lemma 12.

Every connected graph of maximum degree $d$ is $[1,d]\hHAM$

###### Proof.

Label all edges $2$. This visits each vertex at least once, and at most $d$
times. ∎

Together, 11 and 12 give our easiness results. Note that we have easiness for
$[a,b]\hHAM$ whenever $\frac{b}{a}\geq d-1$, unless $a=1$, in which case we
need $\frac{b}{a}\geq d$. The first thing we will observe in the next section
is that $[1,d-1]\hHAM$ is in fact $\NP$-hard, so this distinction is
necessary.

###  3.2 Hardness

######  Lemma 13.

$[1,d-1]\hHAM$ is $\NP$-hard in graphs of maximum degree $d$.

###### Proof.

When $d$ is odd, this follows by our hardness results in 8 — a $d$-regular
graph is in particular a graph of maximum degree $d$. When $d$ is even, we can
use the exact same construction as in the proof of that lemma, but just use
3-regular depletors instead of $d$-regular depletors, since we’re no longer
concerned with regularity. ∎

When $a>1$, though, we will show hardness for much larger values of $b$ than
are hard in $d$-regular graphs. Proving this claim will require a new depletor
construction, which we call a chain depletor, since it’s composed of a long
chain of subunits:

######  Lemma 14.

Let $a,b$ be integers with $1\leq a\leq b<a(d-1)$. For any integer
$2k\in[2,2a]$, there exists a gadget of maximum degree $d$ and with a single
attachment edge, which can be part of an $[a,b]\hHAM$ cycle if the attachment
edge is labeled $2k$, but cannot be satisfied if the attachment edge is
labeled $<2k$.

###### Proof.

Consider the gadget shown in Figure 7 — a $3$-edge path on two intermediate
vertices, with depletors of total depletion $D$ attached to the second
intermediate vertex.

Figure 7: A “chainlink” gadget, forcing $y\leq x+(2b-2a-D)$

Gadgets of this form will serve as the links in the chain. Let $x$ be the
label leaving the first intermediate vertex, $y$ be the label leaving the
second intermediate vertex, and $m$ be the label on the edge between the two
vertices. In order to satisfy the visit counts of the first vertex, we must
have $x+m\geq 2a$, and in order to satisfy the visit counts of the second
vertex we must have $y+m+D\leq 2b$. Adding these constraints together, we find
that if $y>x+(2b-2a-D)$, there is no setting of $m$ that satisfies both of
them. On the other hand, if $x\in[2,2a-2]$, then setting $m=2a-x$ and
$y=x+(2b-2a-D)$ not only satisfies all visit count constraints, but also
preserves connectivity _so long as $y\geq 2$_. So, this gadget forces its
“outgoing” edge to have label at least $(2b-2a-D)$ more than its “incoming”
edge, and is satisfied by an outgoing label exactly that large as long as its
incoming edge had label between $2$ and $2a-2$.

Of course, in constructing this link gadget, we assumed we were able to
deplete a vertex by $D$. So if we want to use these gadgets for anything, we
first need some sort of depletors to start with. Fortunately we do have some
depletors: using for instance the $3$-regular depletor of 5 (or an edge with a
triangle on the end) gives $2$ depletion, and gluing a single vertex along an
edge gives $2a$ depletion. The overall goal of the chain depletor construction
is to get a single gadget with depletion in between $2$ and $2a$, since for
our reductions we will need to fine-tune the depletion exactly.

For our construction, we chain together multiple copies of the link gadget,
identifying the outgoing edge of one with the incoming edge of the next, and
finally ending in a single vertex, as shown in Figure 8:

Figure 8: A chain of link gadgets forcing
$x+\sum_{i=1}^{\ell}(2b-2a-D_{i})\geq y\geq 2a$.

Suppose the link gadgets are constructed with depletions
$D_{1},\dots,D_{\ell}$, and let $x$ and $y$ be the labels assigned to the
attachment edge and final edge of the chain, respectively. By our analysis of
the link gadget, this construction is unsatisfiable if the final edge has
label $y>x+\sum_{i=1}^{\ell}(2b-2a-D_{i})$. We would therefore like to choose
the depletions $D_{i}$ such that $\sum_{i=1}^{\ell}(2b-2a-D_{i})=2a-2k$, since
then if the incoming edge has too small a label $x<2k$, this will make setting
$y\geq 2a$ impossible, and so ensure that the vertex at the end of the chain
can’t be satisfied. We also want to make sure that the chain _is_ satisfiable
if the incoming edge is labeled $x=2k$; to guarantee that, it suffices by our
analysis of the link gadgets to ensure that
$2k+\sum_{i=1}^{j}(2b-2a-D_{i})\in[2,2a-2]$ for all $j<\ell$, since then the
construction is satisfied by greedily labeling each edge, from attachment edge
to the final edge, with the smallest allowable value.

We will now show that, except in the case where $b$ is a multiple of $a$,
which we will handle slightly differently, it is always possible to construct
such a sequence of $D_{i}$. Let $M=\left\lfloor\frac{b}{a}-1\right\rfloor$ and
$L=2b\mod 2a$, so that $2b=2a(M+1)+L$. We will use three kinds of links, with
the following depletions:

  * •

$D_{\text{large}}=2a(M+1)$, created by gluing $(M+1)$ single edges. We have

$(2b-2a-D_{\text{large}})=L-2a.$

  * •

$D_{\text{medium}}=2aM+2$, created by gluing $M$ single edges and one
3-regular depletor. We have

$(2b-2a-D_{\text{medium}})=L-2.$

  * •

$D_{\text{small}}=2aM$, created by gluing $M$ single edges. We have

$(2b-2a-D_{\text{small}})=L.$

To verify that these links are well defined, we must check that the maximum
degree in the link is at most $d$. Note that $\frac{b}{a}<d-1$ by assumption.
Thus, $M\leq d-3$, so the degree constraint allows us to glue $M+1$ depletors
to a vertex in our link gadget.

As long as $b$ is not a multiple of $a$, we have that $L$ is positive, $L-2a$
is negative, and $\gcd(L,L-2,L-2a)=2$. By Bezout’s lemma, there must therefore
exist non-negative integers $w_{1},w_{2},w_{3}$ such that

$w_{1}(L-2a)+w_{2}(L-2)+w_{3}L=2a-2k.$

So, we have constructed a multiset of links with the desired sum. Now we give
an ordering of the links in the multiset such that such that

$2k+\sum_{i=1}^{j}(2b-2a-D_{i})\in[2,2a-2]$

for all $j<\ell$. We construct the ordering greedily. Let $S$ be the multiset
of links we found above. While

$2k+\sum_{i=1}^{j}(2b-2a-D_{i})\neq 2a,$

we choose an element $D^{*}$ of $S$ such that

$(2b-2a-D^{*})+2k+\sum_{i=1}^{j}(2b-2a-D_{i})\in[2,2a],$

set $D_{j+1}=D^{*}$, and remove $D^{*}$ from $S$. We now show that such a
$D^{*}$ necessarily exists.

Suppose $S$ is nonempty, and adding a large link brings the sum outside the
desired interval. That is,

$(L-2a)+2k+\sum_{i=1}^{j}(2b-2a-D_{i})\leq 0.$

Then, since adding all remaining elements of $S$ would bring the sum to $2a$,
we know that $S$ cannot consist only of large links. $L$ and $L-2$ are both
non-negative, and we know

$L+2k+\sum_{i=1}^{j}(2b-2a-D_{i})\leq 0+2a=2a,$

so adding either a medium or a small link would be valid. If, on the other
hand, adding a large link would be valid, then either $S$ contains a large
link and we can add that, or $S$ contains only small and medium links, in
which case since $L$ and $L-2$ are both non-negative we can add them in any
order. Repeating this argument on $S$ until we reach a sum of $2a$ will give a
greedy construction for the link sequence $D^{*}$.

We have established the lemma in the case that $a\nmid b$; we now deal with
the case where $b$ is a multiple of $a$. Here, $L=0$, so now none of $L$,
$L-2$, and $L-2a$ are positive. In this case, we will build our chain using
$k-1$ copies of the $D_{\text{medium}}$ link, and feed the final edge into a
$3$-regular depletor as opposed to a single vertex, as in Figure 9.

Figure 9: A chain of link gadgets forcing $x-2(k-1)\geq y\geq 2$.

If the attachment edge is labeled $2k$, then the final edge can be labeled at
least $2$ and so this is satisfiable. However if the attachment edge is
labeled $x<2k$, then the final edge can’t have positive label, and so the
final depletor is not visited. ∎

Now that we have these fine-tunable depletors, we can glue them to the
vertices of a graph to contribute a specific number of artificial visits.
However, in order to contribute _enough_ visits in our reduction, it is
sometimes necessary to also deplete along the edges.

######  Lemma 15.

Let $a,b$ be constants with $1\leq a\leq b<a(d-1)$. For any integer
$2k\in[2,2a-2]$, there exists a gadget of maximum degree $d$ and with two
attachment edges with the following properties:

  * •

The gadget can be satisfied if both attachment edges are labeled $2k$.

  * •

The gadget cannot be satisfied if an attachment edge is labeled less than
$2k$.

  * •

The gadget can be both satisfied and connected if both attachment edges are
labeled $2k+1$.

  * •

The gadget cannot be connected if an attachment edge is labeled less than
$2k+1$.

###### Proof.

Consider the gadget shown in Figure 10: a path on $4$ intermediate vertices,
where the $2$ middle vertices each have $2b-2a+2k$ worth of depletion glued to
them — this can be constructed using the chain depletors of 14.

Figure 10: An edge gadget that is satisfiable if both inputs are $2k$,
satisfiable and connected if both inputs are $2k+1$.

The middle edge can be assigned non-negative label only if both attachment
edges are labeled at least $2k$, and can be assigned positive label only if
both attachment edges are labeled at least $2k+1$. ∎

We can think of this edge gadget as effectively providing $2k$ depletion to
both sides. So, we can now give a reduction to show our complete complexity
characterization:

######  Theorem 2.

When restricted to graphs of maximum degree $d$, $[a,b]\hHAM$ is -hard if
either $a=1$ and $b<d$, or $a>1$ and $\frac{b}{a}<d-1$. Otherwise,
$[a,b]\hHAM\in\P$.

###### Proof.

The easiness results were established in Section 3.1, and the case of $a=1$ in
13. So, it suffices to show a reduction from $[1,1]\hHAM$ in a $3$-regular
graph $G$ to $[a,b]\hHAM$ in a max-degree $d$ graph $G^{\prime}$ when $1<a\leq
b<(d-1)a$. By replacing the edges of $G$ with the edge gadgets of 15, we can
introduce up to $3(2a-1)$ depletion at each vertex, and by gluing up to
$(d-3)$ additional chain depletors to each original vertex, we can introduce
up to $2a(d-3)$ more. Since

$3(2a-1)+2a(d-3)\geq 2b-2,$

and all of these depletors are fully fine-tunable, we can ensure exactly
$2b-2$ depletion on each original vertex of $G$. This means that up to but no
more than $2$ of the edge gadgets incident to each original vertex can be
connected; thus, $G^{\prime}$ is $[a,b]\hHAM$ if and only if $G$ has a
connected $2$-factor. ∎

##  4 Complexity characterization in directed graphs

In contrast to the case of undirected graphs, where we found that sufficiently
large size of the $[a,b]$ range compared to degree made $[a,b]\hHAM$ easy, we
will show that in directed graphs every case is hard, except when the $[a,b]$
range is very small (contains only a single element) and $d=3$.

Just as in the directed case, we can think of the problem of $[a,a]\hHAM$ as
finding labels. More precisely, a directed graph is $[a,a]\hHAM$ if and only
if there is a connected labeling of the edges such that every vertex has in-
label sum $a$ and out-label sum $a$. As in the directed case the equivalence
of these notions follows from taking an Euler tour on the multigraph generated
by viewing the labels as multiplicities for edges.

###  4.1 Easiness

First we give a simple algorithm for the easy cases of $[a,b]\hHAM$ in
directed graphs.

######  Lemma 16.

For $a>1$, there exists a polynomial-time algorithm to decide $[a,a]\hHAM$ in
directed graphs of maximum degree $3$.

###### Proof.

Fix a directed graph of maximum degree $3$. If any vertex has in-degree or
out-degree $3$ we immediately deduce that the graph is not $[a,a]\hHAM$; in
the remainder of the proof we assume there are no vertices with in-degree or
out-degree $3$.

Our algorithm for $[a,a]\hHAM$ begins as follows: while there exists a vertex
$v$ in the graph with only a single unlabeled out-edge, or only a single
unlabeled in-edge, assign that edge the unique label that satisfies $v$. When
that process terminates, each vertex must have either zero or two unlabeled
in-edges, and either zero or two unlabeled out-edges. So, if we look at the
subgraph on unlabeled edges, and think of them as undirected, we must have a
union of even-length cycles. For each of those cycles, assign labels by
alternating between $\left\lfloor\frac{a}{2}\right\rfloor$ and
$\left\lceil\frac{a}{2}\right\rceil$. Now, check whether the assigned labels
represent an $[a,a]\hHAM$ labeling; if so accept, if not reject.

Since
$\left\lfloor\frac{a}{2}\right\rfloor+\left\lceil\frac{a}{2}\right\rceil=a$,
if our labeling violates a vertex visit constraint, that constraint must have
been violated during the forced initial phase. Similarly, since this process
only labels edges with $0$ during the initial phase, if connectivity fails
then no labeling can achieve connectivity. ∎

###  4.2 Hardness

####  4.2.1 Max degree $3$

We now show hardness of $[a,a+1]\hHAM$. We will argue by induction. The
following lemma constitutes the inductive step of the argument.

######  Lemma 17.

Fix $k\geq 1$. Suppose that $[1,k]\hHAM$ is -hard in $3$-regular digraphs.
Then, for any $a\geq 1$, $[a,a+k]\hHAM$ is -hard in $3$-regular digraphs.

###### Proof.

Let $G$ be a $3$-regular digraph. We construct $G^{\prime}$ by replacing each
vertex of $G$ with a vertex gadget consisting of three hub vertices connected
by bridge gadgets, as shown in Figure 11.

Figure 11: A vertex gadget. Note that the specific structure of the bridge
gadgets is just to preserve $3$-regularity; what’s important is that they are
acyclic. The labelings shown here are the two possible $[a,a+1]\hHAM$
traversals — in a similar manner, any way to enter and leave the gadget at
most $k$ times can be turned into an $[a,a+k]\hHAM$ traversal.

We claim that $G$ is $[1,k]\hHAM$ if and only if $G^{\prime}$ is
$[a,a+k]\hHAM$. First we show that if $G^{\prime}$ is $[a,a+k]\hHAM$ then $G$
must be $[1,k]\hHAM$. Each of the bridge gadgets must be visited at least $a$
times, contributing at least $a$ of the in-label and out-label of each of the
hub vertices. Thus, the edges entering and leaving the vertex gadget can be
traversed at most $k+a-a$ times. That is, each vertex gadget is visited at
most $k$ times and at least once in an $[a,a+k]\hHAM$ tour of $G^{\prime}$. If
this is possible, then $G$ must be $[1,k]\hHAM$.

For the other direction, if $G$ is $[1,k]\hHAM$ we can create labelling of
$G^{\prime}$ proving that $G^{\prime}$ is $[a,a+k]\hHAM$ as follows. First,
copy the labels on the edges in $G$ to the edges that enter and exit the
vertex gadgets. Now, label the edges internal to the vertex gadgets as
follows: start by assigning all edges in the gadget label $a$. Then, increase
the edges in the first bridge gadget by one for every traversal of the first
edge out of the vertex in $G$. Then, increase the labels of edges in both the
first and second bridge gadgets by one for each traversal of the second edge
leaving the vertex in $G$. This labeling visits each interval vertex at least
$a$ times and at most $a+k$ times, as desired. Thus, $G^{\prime}$ is
$[a,a+k]\hHAM$. ∎

Now, by applying this construction recursively, we can show our full hardness
result:

######  Lemma 18.

For any $1\leq a<b$, $[a,b]\hHAM$ is $\NP$-hard in $3$-regular digraphs.

###### Proof.

We will argue by induction on $k$ that for all constants $a\geq 1,k\geq 1$,
$[a,a+k]\hHAM$ is -hard. Using the classic theorem that $[1,1]\hHAM$ is -hard
in $3$-regular digraphs, by 17 we deduce $[a,a+1]\hHAM$ is -hard for all
$a\geq 1$; this will serve as the base case of our induction. Now, assume that
$[a,a+k]\hHAM$ is -hard for any constant $a$. In particular this means that
$[1,1+k]$ is -hard. Then, applying 17 we conclude that $[a,a+k+1]\hHAM$ is
-hard for all $a\geq 1$. ∎

16 and 18 together establish 3:

######  Theorem 3.

In directed graphs of maximum degree $3$, for $1\leq a\leq b$,
$[a,b]\hHAM\in\P$ if $a=b>1$, and $\NP$-hard otherwise.

####  4.2.2 Max degree 4

The hardness for max degree $3$ digraphs immediately gives that $[a,b]\hHAM$
is hard in max degree $4$ digraphs as long as $b>a$. In this section, we will
take a different reduction approach to show that $[a,a]\hHAM$ is also hard. We
will use the following depletor-like construction, which we call an at-
least-$k$ gadget:

######  Lemma 19.

For any $k\in[1,a]$, there exists a gadget of max degree $4$ with one incoming
edge and one outgoing edge that can be part of an $[a,a]\hHAM$ cycle as long
as it’s traversed at least $k$ times and at most $a$ times.

###### Proof.

First, as a base case, consider the construction in Figure 12. It is clear
that this is an at-least-$1$ gadget.

Figure 12: A gadget that can be traversed between $1$ and $a$ times.

Now, suppose we know how to build an at-least-$(k-1)$ gadget. Then, the
construction in Figure 13 is an at-least-$k$ gadget.

Figure 13: A gadget that can be traversed between $k$ and $a$ times.

∎

By using at-least-$(a-1)$ gadgets, we can give our desired reduction.

######  Lemma 20.

For any $a\geq 1$, $[a,a]\hHAM$ is $\NP$-hard in directed graphs of maximum
degree $4$.

###### Proof.

We reduce from $[1,1]\hHAM$ in max degree $3$ digraphs. Let $G$ be a max
degree $3$ digraph. We will make two copies, $V_{\text{in}}$ and
$V_{\text{out}}$, of the vertex set, and add the edge
$(u_{\text{out}},v_{\text{in}})$ for every edge $(u,v)\in E(G)$. We will also
add the edges $(v_{\text{in}},v_{\text{out}})$ for all $v\in V(G)$. Finally,
for every $v\in V(G)$, we will add an at-least-$(a-1)$ gadget from
$v_{\text{out}}$ to $v_{\text{in}}$. This construction is shown in Figure 14.

Figure 14: Reducing $[1,1]\hHAM$ in max degree $3$ digraphs to $[a,a]\hHAM$ in
max degree $4$ digraphs.

The at-least-$(a-1)$ gadget consumes all but $1$ of $v_{\text{out}}$’s
available out-label, and all but $1$ of $v_{\text{in}}$’s available in-label,
so at most one other edge out of $v_{\text{out}}$ can be given nonzero label,
and at most one other edge into $v_{\text{in}}$ can be given nonzero label.
Thus, in order to maintain connectivity between all $v$, the labeling in
$G^{\prime}$ must correspond to a Hamiltonian cycle in $G$. ∎

This establishes 4:

######  Theorem 4.

For all $b\geq a\geq 1$, $[a,b]\hHAM$ is $\NP$-hard in directed graphs of
maximum degree 4.

##  5 Conclusion and open questions

We now have full characterizations of which $a$ and $b$ make $[a,b]\hHAM$
-hard in $d$-regular graphs and graphs of max degree $d$. One question of
further potential interest would be to extend this analysis to low-dimensional
grid graphs (i.e. induced subgraphs of a square lattice). It’s known that
$[1,1]\hHAM$ is -hard in 2-dimensional grid graphs [IPS82], but not clear
whether one should expect $[1,2]\hHAM$ to be hard as well, for example.
Another problem worth considering would be hardness of approximation — for
instance, when is it possible to distinguish between $[a,a]\hHAM$ graphs and
graphs that aren’t even $[a^{\prime},a^{\prime}]\hHAM$, for some
$a^{\prime}>a$?

## Acknowledgments

This paper was initiated during open problem solving in the MIT class
“Algorithmic Lower Bounds: Fun with Hardness Proofs” (6.5440) taught by Erik
Demaine in Fall 2023. We thank the other participants of that class for
helpful discussions and providing an inspiring atmosphere.

## References

  * [AK11] Jin Akiyama and Mikio Kano  “Factors and Factorizations of Graphs Proof Techniques in Factor Theory”  In _Lecture Notes in Mathematics -Springer-verlag-_ 2031, 2011  DOI: 10.1007/978-3-642-21919-1
  * [BG90] H.J. Broersma and F. Göbel  “k-Traversable graphs”  In _Ars combinatoria_ 29A Charles Babbage Research Centre, 1990, pp. 141–153
  * [Gan+19] Robert Ganian et al.  “On the Complexity Landscape of Connected f-Factor Problems”  In _Algorithmica_ 81 Springer, 2019, pp. 2606–2632
  * [GJT76] M.. Garey, D.. Johnson and R. Tarjan  “The Planar Hamiltonian Circuit Problem is NP-Complete”  In _SIAM Journal on Computing_ 5.4, 1976, pp. 704–714  DOI: 10.1137/0205049
  * [GR94] ZC Gao and R Bruce Richter  “2-walks in circuit graphs”  In _Journal of Combinatorial Theory, Series B_ 62.2 Elsevier, 1994, pp. 259–267
  * [IPS82] Alon Itai, Christos Papadimitriou and Jayme Szwarcfiter  “Hamilton Paths in Grid Graphs”  In _SIAM J. Comput._ 11, 1982, pp. 676–686  DOI: 10.1137/0211056
  * [JL04] Zemin Jin and Xueliang Li  “On a conjecture on k-walks of graphs”  In _Australasian Journal of Combinatorics_ 29 CENTRE FOR COMBINATORICS, 2004, pp. 135–142
  * [JW90] Bill Jackson and Nicholas Charles Wormald  “k-walks in graphs”  In _Australasian Journal of Combinatorics_ 2, 1990, pp. 135–146
  * [Kai+07] Tomas Kaiser, Roman Kuzel, Hao Li and Guanghui Wang  “A note on k-walks in bridgeless graphs”  In _Graphs and Combinatorics_ 23.3 Citeseer, 2007, pp. 303–308
  * [KV04] Mekkia Kouider and Preben Dahl Vestergaard  “Even [a,b]-factors in graphs”  In _Discussiones Mathematicae Graph Theory_ 24.3, 2004, pp. 431–441  URL: http://eudml.org/doc/270159
  * [KV05] Mekkia Kouider and Preben Dahl Vestergaard  “Connected factors in graphs-a survey”  Aalborg Universitetsforlag, 2005
  * [Nis+18] Hiroshi Nishiyama et al.  “The parity Hamiltonian cycle problem”  In _Discrete Mathematics_ 341.3, 2018, pp. 606–626  DOI: https://doi.org/10.1016/j.disc.2017.10.025
  * [Plu07] Michael D Plummer  “Graph factors and factorization: 1985–2003: a survey”  In _Discrete Mathematics_ 307.7-8 Elsevier, 2007, pp. 791–821
  * [SS18] Andreas Schmid and Jens M. Schmidt  “Computing 2-Walks in Polynomial Time”  In _ACM Trans. Algorithms_ 14.2 New York, NY, USA: Association for Computing Machinery, 2018  DOI: 10.1145/3183368