# Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_{2}$ Lattice
Gauge Theory

Xiaopeng Cui  Department of Physics & State Key Laboratory of Surface Physics,
Fudan University, Shanghai 200433, China  Yu Shi<EMAIL_ADDRESS>Department of Physics & State Key Laboratory of Surface Physics, Fudan
University, Shanghai 200433, China

###### Abstract

The Hamiltonian cycle (HC) problem in graph theory is a well-known NP-complete
problem. We present an approach in terms of $\mathbb{Z}_{2}$ lattice gauge
theory (LGT) defined on the lattice with the graph as its dual. When the
coupling parameter $g$ is less than the critical value $g_{c}$, the ground
state is a superposition of all configurations with closed strings of spins in
a same single-spin state, which can be obtained by using an adiabatic quantum
algorithm with time complexity
$O(\frac{1}{g_{c}^{2}}\sqrt{\frac{1}{\varepsilon}N_{e}^{3/2}(N_{v}^{3}+\frac{N_{e}}{g_{c}}}))$,
where $N_{v}$ and $N_{e}$ are the numbers of vertices and edges of the graph
respectively. A subsequent search for a HC among those closed-strings solves
the HC problem. For some random samples of small graphs, we demonstrate that
the dependence of the average value of $g_{c}$ on $\sqrt{N_{hc}}$, $N_{hc}$
being the number of HCs, and that of the average value of $\frac{1}{g_{c}}$ on
$N_{e}$ are both linear. It is thus suggested that for some graphs, the HC
problem may be solved in polynomial time. A possible quantum algorithm using
$g_{c}$ to infer $N_{hc}$ is also discussed.

In computational complexity, an important yet unproven conjecture for
classical computing is P $\neq$ NP, where P represents the class of problems
that can be solved in times polynomial in the sizes of the inputs, while NP is
the shorthand for nondeterministic polynomial, representing the class of
problems the solutions of which can be verified in polynomial times. P is a
subset of NP. The factoring problem, which is to find the prime factors of an
odd number, is in class NP, but is conjectured not to be in class P.

In quantum computing, the factoring problem is in class P, as it can be solved
by using Shor’s algorithm in polynomial times Shor (1994), suggesting that
quantum computing is more powerful than classical computing. However, it
cannot be concluded that P=NP in quantum computing, because factoring, as a
specific NP problem, is not a NP-complete (NPC) problem, to which any NP
problem can be reduced to in polynomial time. If any NPC problem can be solved
in polynomial time, so do all the NP problems and consequently P=NP.

Therefore, if there is a quantum algorithm of polynomial time for any NPC
problem, it can be concluded that P=NP in quantum computing. It is thus
important to find quantum speedup of any NPC problem.

A well-known NPC problem is the HC problem van Leeuwen (1991). On an
undirected graph, which is made up of a number of vertices connected by a
number of edges without directions Garey and Johnson (1990), a HC is a cycle
that visits each vertex exactly once. HC problem is to determine whether such
a HC exists. So far the best classical algorithms include the so-called
dynamic programming algorithm of time complexity $O({N_{v}}^{2}2^{N_{v}})$
Bellman (1962) and a Monte Carlo algorithm of time complexity
$O(1.657^{N_{v}})$ Björklund (2010), both of which are exponential in the
number of vertices $N_{v}$. Up to now there is neither quantum algorithm with
P time complexity Mahasinghe  _et al._ (2019).

In this paper, we propose a new approach to HC problem and thus the problem of
P versus NP. We transform the HC problem to a problem in quantum
$\mathbb{Z}_{2}$ LGT Kogut (1979); Sachdev (2018). Gauge theory is the
framework describing the fundamental interactions in particle physics, as well
as strong correlations in condensed matter physics. LGT is an approach to
gauge theories by discretizing the spacetime or space to a lattice.
$\mathbb{Z}_{2}$ LGT is the simplest LGT. Recently quantum simulation has
become a new approach to LGT, including $\mathbb{Z}_{2}$ LGT Lloyd (1996);
Zohar  _et al._ (2017); Cui  _et al._ (2020); Lamm  _et al._ (2019).

We regard a graph as the dual of a lattice, on which the $\mathbb{Z}_{2}$ LGT
is defined. Thus each vertex of the graph maps to a plaquette in the lattice,
each edge in the graph crosses a link in the lattice, and two adjacent
vertices in the graph correspond to two adjacent plaquettes in the lattice.
The length is not defined for each edge in the graph or each link in the
lattice, therefore the lattice can be deformed when needed. Thus an undirected
unweighted graph of $N_{v}$ vertices becomes the dual lattice of a lattice
with $N_{v}$ palquettes. Depicted in Fig. 1 is an example, in which the graph
becomes the dual lattice of a $3\times 3$ square lattice, with periodic
boundary condition, i.e. a topologically torus lattice.

Figure 1: Correspondence between a graph and the torus lattice. (a) A graph
corresponding to the $3\times 3$ tours lattice shown in (b). (b) $3\times 3$
torus lattice, where the black solid lines are links of the lattice, the blue
dotted lines correspond to the edges of the graph in (a), the numbers in black
denote the edges of the lattice, and the numbers in blue correspond to those
for the vertices in the graph in (a).

In this way, HC in a graph becomes HC in the dual lattice of a lattice. By
connecting the last with the first visited vertices in the graph, an HC in the
dual lattice becomes a closed string or loop passing through all the
plaquettes of the lattice with periodic boundary condition, as shown in Fig.
2. Hence HC problem becomes the search for a closed string that visits each
vertex of the dual lattice one. This is much easier, since the set of all the
closed strings is much smaller than the set of all paths.

Figure 2: Identification of the cycles on a certain graph as the closed
strings on the dual lattice of a square lattice. (a) A HC of the graph,
depicted as a red path in (a) becomes a closed string passing through all the
plaquettes on the lattice, as depicted in red in (b). (b) A configuration of
closed strings at the ground state of quantum $\mathbb{Z}_{2}$ LGT at $g=0$.
There is only one closed string, depicted as a red path. The orange edge is in
the $\ket{0}$ state, and the green edge is in the $\ket{1}$ state. (c) Two
cycles, depicted in red, in the graph. (d) A closed string configuration in
the quantum $\mathbb{Z}_{2}$ LGT ground state at g = 0, with two closed
strings, depicted as red paths, corresponding to the two cycles in the graph.
The orange edge is in the $\ket{0}$ state, and the green edge is in the
$\ket{1}$ state.

Furthermore, the search for a HC among the closed strings can be significantly
accelerated by the topological quantum phase transition (TQPT) in the quantum
$\mathbb{Z}_{2}$ LGT. At the critical value $g_{c}$ of the coupling parameter
$g$, a TQPT occurs separating the confined phase for $g>g_{c}$ and the
deconfined phase for $g<g_{c}$, in which there is proliferation of the closed
strings of down spins, called closed-string condensation, as the ground state
becomes a closed-string condensate, which is a quantum superposition of all
configurations of closed strings of down spins (in the convention described
below) Levin and Wen (2005); Wen (2005). $g_{c}$ depends on the properties of
the graph, including $N_{hc}$, hence can be used to reveal $N_{hc}$.
Therefore, reaching TQPT in a quantum adiabatic simulation becomes the key
step in the present approach to HC problem. The dependence of $g_{c}$ on
$N_{hc}$ suggests low time complexity, and to a new approach to the problem of
P versus NP. This method applies to any graph, which can always be regarded as
a dual lattice of a lattice, on which the $\mathbb{Z}_{2}$ LGT can always be
defined.

Quantum $\mathbb{Z}_{2}$ LGT and closed strings.—-The Hamiltonian of the
quantum $\mathbb{Z}_{2}$ LGT Cui  _et al._ (2020); Sachdev (2018); Wegner
(1971) is

$H=Z+gX$ (1)

with

$X=-\sum_{l}{\sigma_{l}^{x}},\,Z=\sum_{\square}{Z_{\square}},\,Z_{\square}=-\prod_{l\in\square}{\sigma_{l}^{z}}$
(2)

where the spins (qubits) occupy the links $l$’s, $\square$ represents the
elementary plaquette of the lattice. Single-spin states $|0\rangle$ and
$|1\rangle$ correspond to $\sigma_{l}^{z}=1$ (up) and $\sigma_{l}^{z}=-1$
(down), respectively. The ground state at $g=0$ is

$\ket{\psi_{0}}=\sum_{i=1}^{S_{0}}{\ket{\phi_{i}}},$ (3)

where each ${\ket{\phi_{i}}}$ is with $Z_{\square}=-1$ for any $\square$ and
thus $Z=-9$. In the $M\times N$ torus lattice, there are $N_{v}\equiv MN$
plaquettes, $N_{e}\equiv 2N_{v}$ links. Hence the number of configurations
with $Z=-9$ is $S_{0}\equiv 2^{N_{e}}/(2^{N_{v}-1})$, where $2^{N_{e}}$ is the
number of all possible configurations of spins, while $1/2^{N_{v}-1}$ is the
probability that $Z_{\square}=-1$ for each $\square$.

On the dual lattice, one can regard a spin with $\sigma_{l}^{z}=-1$ as
occupied by a string while a link with $\sigma_{l}^{z}=1$ as unoccupied.
Occupied links can be connected to form a longer string, which may be open or
closed, then $\ket{\phi_{i}}$ can be regarded as a configuration of closed
strings. When $g<g_{c}$, the ground state can be represented as a closed-
string condensate, which is a superposition of $S_{0}$ configurations of
closed strings. Especially, when $g=0$, the superposition is of equal
amplitude Freedman (2003); Levin and Wen (2005); Fradkin (2013), Among the
$S_{0}$ configurations of closed strings, two examples are as shown in the
Fig. 2, where in (a), a single closed string passes through all $N_{v}$
plaquettes of the lattice, and is thus a HC, while in (b), there are two
closed strings, each passing through a part of the $N_{v}$ plaquettes, so
there is no HC.

Therefore, in order to solve HC problem, one only needs to search for HCs in
the $S_{0}$ configurations of closed strings, rather than $N_{v}!$
configurations in the original configuration space Garey and Johnson (1990).
This greatly reduces complexity.

Quantum Algorithm for HC problem.—-The complexity of this quantum algorithm
comes from the two consecutive processes. The first is to obtain the closed-
string condensate, and the second is to search for HCs in it.

The initial state is the ground state at $g=+\infty$, which is the equal
superposition of all product states of $|0\rangle$ and $|1\rangle$. With $g$
decreased adiabatically towards $g\leq g_{c}$, the closed-string condensate is
obtained. This process is equivalent to adiabatically evolve
$H_{\lambda}=\lambda Z+X$, with $\lambda=\frac{1}{g}$, from $\lambda=0$
towards $\lambda_{c}=\frac{1}{g_{c}}$.

The adiabatic condition implies that the time scale is $t=O(\sqrt{N_{e}})$ for
a 2-dimensional lattice Hamma and Lidar (2008). Hence the time scale is
$t=O(\sqrt{N_{e}})\lambda_{c}$ for an lattice of an unknown $\lambda_{c}$.

For the adiabatic evolution, we use the symmetric Trotter decomposition to
decompose the unitary evolution, which is more efficient than the original
Trotter decomposition Trotter (1959); Childs  _et al._ (2019). The error for
each step in the adiabatic simulation is
$\varepsilon_{s}(t,n,g)=|e^{-i(A+B)t}-(e^{-iA\frac{t}{2n}}e^{-iB\frac{t}{n}}e^{-iA\frac{t}{2n}})^{n}|=|e^{-i(A+B)t}-e^{-iA\frac{t}{2n}}(e^{-iB\frac{t}{n}}e^{-iA\frac{t}{n}})^{n-1}e^{-iB\frac{t}{n}}e^{-iA\frac{t}{2n}}|\leqslant(\frac{1}{12}g^{2}N_{v}n_{l}^{2}+\frac{1}{24}gN_{e}*n_{p}^{2})\frac{t^{3}}{n^{2}}$,
where $A=Z$ and $B=gX$ are the two terms in the Hamiltonian, $t$ is time of
the step, $n$ is number of symmetric Trotter substeps, $n_{l}$ is the number
of links surrounding each plaquette, $n_{p}$ is the number of vertices
connected by each edge or is the number of plaquettes sharing each link Cui
_et al._ (2020). Then the cumulative error from the start to the phase
transition point $\lambda_{c}$ can be obtained as

$\varepsilon=O(\frac{1}{N_{ss}^{2}}N_{e}^{3/2}(N_{v}^{3}+N_{e}\lambda_{c})\lambda_{c}^{4}),$
(4)

where $N_{ss}$ is the total number of symmetric Trotter substeps. Therefore,
the time complexity required in the adiabatic quantum simulation of the
quantum $\mathbb{Z}_{2}$ LGT is

$O_{1}=O(\sqrt{\frac{1}{\varepsilon}N_{e}^{3/2}(N_{v}^{3}+N_{e}\lambda_{c})\lambda_{c}^{4}})=O(\frac{1}{g_{c}^{2}}\sqrt{\frac{1}{\varepsilon}N_{e}^{3/2}(N_{v}^{3}+\frac{N_{e}}{g_{c}}})),$
(5)

where $\varepsilon$ is reinterpreted as the precision required for the quantum
simulation. In a connected undirected graph, $N_{v}\leq N_{e}\leq
N_{v}(N_{v}-1)/2$, $g_{c}$, $\lambda_{c}$ are fixed quantities for a given
graph.

Subsequently, a quantum search algorithm searches for HCs in the closed-string
condensate, which is is a superposition of $S_{0}=O(2^{N_{e}}/2^{N_{v}})$
components, including those with HCs. The time complexity is
$O_{2}\sim\frac{S_{0}}{N_{hc}}$, since the probability of obtaining a state
with a HC in a measurement is $\frac{N_{hc}}{S_{0}}$. The relationship between
$N_{hc}$ and $N_{e}$ of some sample graphs is shown in figure 10 (b). It is
possible to develop a better quantum search algorithm finding HCs in the
closed-string condensates. The time complexity for the whole process is
$O=O_{1}\cdot O_{2}$.

Quantum Algorithm of finding $g_{c}$.—-$g_{c}$ depends on and thus may reveal
some properties of the graph, for example, $N_{hc}$. After reaching the TQPT,
a measurement of $g_{c}$ contributes additional time complexity $O_{M}$.
According to the phase estimation method Cui  _et al._ (2020), $O_{M}$ is of
the same order of magnitude as $O_{1}$. Thus with adiabatic algorithm followed
by measurement, we have a quantum algorithm of finding $g_{c}$, with time
complexity $O^{\prime}=O_{1}+O_{M}\sim O_{1}$.

Relations between $g_{c}$ and the graph properties.—-Because the complexity
$O_{1}$ depends on $\lambda_{c}\equiv\frac{1}{g_{c}}$, we need to investigate
the relations between $g_{c}$ and the graph properties, e.g. $N_{hc}$ and
$N_{e}$.

We work on this problem using the classical demonstration of the quantum
adiabatic simulation, in terms of the QuEST simulator Jones  _et al._ (2019).
The hardware we use is the Nvidia GPU Tesla V100-SXM2-32GB Cui  _et al._
(2020).

We first randomly generate four graphs with $N_{v}=9$ and $N_{e}=18$, as shown
in Fig. 3(a-d). The fourth corresponds to the $3\times 3$ torus lattice.
$N_{hc}$ of the four graphs are 0, 10, 30, 48, respectively. For such small
graphs, we use measurement method, as described in Cui  _et al._ (2020), to
obtain the ground state $\ket{\psi_{0}}$ at $g=0$, as given in (3). Note that
this method is not feasible for larger graphs, as in our discussion on the
quantum algorithm for HC problems.

Figure 3:  Four different graphs used in calculating the critical parameters
of the TQPT of $\mathbb{Z}_{2}$ LGT. (a) $G_{1}:N_{v}=9,N_{e}=18,N_{hc}=0$.
(b) $G_{2}:N_{v}=9,N_{e}=18,N_{hc}=10$. (c)
$G_{3}:N_{v}=9,N_{e}=18,N_{hc}=30$. (d) $G_{4}$: the graph corresponding to
the $3\times 3$ torus lattice, $N_{v}=9,N_{e}=18,N_{hc}=48$.

Then we adiabatically increase $g$ from 0 to 1, in steps with
$g_{s}=0.001,t_{s}=0.1,n=100$, where $g_{s}$ is the variation of $g$, $t_{s}$
and $n$ are the time and the number of the symmetric Trotter substeps within
each step, respectively. The total cumulative error is
$\varepsilon_{all}=\sum_{g=g_{s}}^{1}{\varepsilon_{s}(t,n,g)}$, which is less
than $0.135\%$ for the graphs studied here. We study quantum phase transitions
on the lattices corresponding to these graphs. First, $\braket{H}$,
$\braket{Z}$ and $\braket{Z}$ are obtained as functions of $g$. Then we define
two critical parameters, which are easily determined, to represent the
critical parameter $g_{c}$. One is the extremal point $g_{c}^{H}$ of the
second derivative of $\braket{H}$, the other is the extremal point $g_{c}^{Z}$
of the first derivative of $\braket{Z}$.
$\lambda_{c}^{H}=\frac{1}{g_{c}^{H}}$, $\lambda_{c}^{Z}=\frac{1}{g_{c}^{Z}}$.
As can be observed in Fig. 4(c-d), $g_{c}^{H}$ and $g_{c}^{Z}$ both increase
with $N_{hc}$. This verifies that the properties of the graph directly affect
the characteristics of the quantum phase transition.

Figure 4: (a) $\langle H\rangle$ for four graphs denoted in terms of $N_{hc}$.
(b) $\langle Z\rangle$ and $\langle X\rangle$ for four graphs denoted in terms
of $N_{hc}$. (c) The second derivatives of $\langle H\rangle$ for the four
graphs, which can be used to determine the values of $g_{c}^{H}$. (d) The
first derivative of $\langle Z\rangle$ for the four graphs, which can be used
to determine the values of $g_{c}^{Z}$.

In order to study how $g_{c}^{H}$ and $g_{c}^{Z}$ depend on $N_{hc}$, we
prepare two groups of undirected and unweighted connected graphs with
$N_{v}=9$. The first group consists of 1000 samples, each with $N_{e}=18$. We
make the classical GPU demonstration of the adiabatic quantum simulation, and
obtained $N_{hc}$ for each graph. The distribution of $N_{hc}$ is shown in
Fig. 5(a). The second group consists of $200$ graphs for each value of $N_{e}$
varying from $16$ to $22$. The distribution of $N_{hc}$ is shown in the Fig.
5(b).

Figure 5:  Distribution of the $N_{hc}$ among samples of graphs. $n_{s}$
represents the number of the samples. (a) The case in which $N_{e}=18$ in each
sample. There are 1000 samples in total. (b) The case in which $N_{e}$ varying
from $16$ to $22$. There are 200 samples with each value of $N_{e}$, and 1400
samples in total.

It can be seen from Fig. 6 that the average value of $g_{c}^{H}$ and
$g_{c}^{Z}$ increase steadily with $N_{hc}$ when $N_{e}$ is fixed. Especially,
when $N_{hc}$ = 0, $g_{c}^{H}$ and $g_{c}^{Z}$ are very small. This shows that
$N_{hc}$ has a significant effect on $g_{c}$. This effect can help determine
$N_{hc}$ without searching the HCs of the graph. The time complexity required
to reach TQPT is $O_{1}$. $g_{c}^{H}$ and $g_{c}^{Z}$ may decrease linearly
with $N_{e}$, as discussed below. Together with $N_{v}\leq N_{e}\leq
N_{v}(N_{v}-1)/2$, these properties imply that HC problem in these small
graphs can be solved in polynomial time.

Figure 6:  Dependence of the critical parameters on $N_{hc}$. (a) Dependence
of $g_{c}^{H}$ on $N_{hc}$ in graphs with $N_{e}=18$. (b) Dependence of
$g_{c}^{Z}$ on $N_{hc}$ in graphs with $N_{e}=18$. (c) Dependence of
$g_{c}^{H}$ on $N_{hc}$ in graphs with $N_{e}$ varying from $16$ to $22$. (d)
Dependence of $g_{c}^{Z}$ on $N_{hc}$ in graphs with $N_{e}$ varying from $16$
to $22$.

We have also studied the effect of $N_{e}$ on the critical parameters, by
using the second group of graphs with the same $N_{v}$ value but different
$N_{e}$ values. As can be seen in the Fig. 7, the average values of
$g_{c}^{H}$ and $g_{c}^{Z}$ decrease steadily with $N_{e}$ when $N_{v}$ is
fixed. The larger the $N_{e}$ value, the smaller the critical parameters. In
other words, the average value of $\lambda_{c}=\frac{1}{g_{c}}$ increase
linearly with $N_{e}$ when $N_{v}$ is fixed. Thus $O_{1}$ increases with
$N_{e}$ polynomially. On average, when $N_{v}$ is fixed, the connectivity
between vertices of a graph is proportional to $N_{e}$.

Figure 7:  The dependence of the critical parameters on $N_{e}$. (a) The
dependence of $g_{c}^{H}$ on $N_{e}$ in the samples with $N_{e}$ varying from
$16$ to $22$. (b) The dependence of $g_{c}^{Z}$ on $N_{e}$ in the samples with
$N_{e}$ varying from $16$ to $22$. (c) The dependence of $\lambda_{c}^{H}$ on
$N_{e}$ in the samples with $N_{e}$ varying from $16$ to $22$. (d) The
dependence of $\lambda_{c}^{Z}$ on $N_{e}$ in the samples with $N_{e}$ varying
from $16$ to $22$.

As can be seen in Fig. 8, when $N_{e}$ and $N_{v}$ are fixed, the average
values of the critical parameters decrease with the maximal degree of the
vertices $Max(Deg)$, while increases with the minimal degree of the vertices
$Min(Deg)$. On average, when $N_{v}$ and $N_{e}$ are fixed, the larger
$Max(Deg)$, the smaller $(Min(Deg))$. So the results in Fig. 8(a,c) and Fig.
8(b,d) are consistent.

Figure 8:  The dependence of the critical parameters on the degree of
vertices. (a) The dependence of $g_{c}^{H}$ on $Max(Deg)$ in the samples with
$N_{e}=18$. (b) The dependence of $g_{c}^{H}$ on $Min(Deg)$ in the samples
with $N_{e}=18$. (c) The dependence of $g_{c}^{H}$ on $Max(Deg)$ in the
samples with $N_{e}$ varying from $16$ to $22$. (d) The dependence of
$g_{c}^{Z}$ on $Min(Deg)$ in the samples with $N_{e}$ varying from $16$ to
$22$.

Furthermore, we find that the relation between the average values of
$g_{c}^{H}$ and $N_{hc}$ can be very well fitted quantitatively as

$g_{c}^{H}=A\sqrt{N_{hc}}+B,$ (6)

as shown in Fig. 9 for the two groups of graph samples. On the other hand, the
relation between $\lambda_{c}^{H}$ and $N_{e}$ can be very well fitted as

$\lambda_{c}^{H}=0.1513*N_{e}+0.007536,$ (7)

as shown in Fig.10. (6) and (7) are consistent. Due to the limitation of
computing power, $N_{e}$ is still relatively small in our simulated graphs, so
the linear relationship needs verification in larger graphs.

Figure 9:  The average value of $g_{c}^{H}$ as a function of $N_{hc}$, fitted
by $g_{c}^{H}=A\sqrt{N_{hc}}+B$. (a) The samples with $N_{e}=18$.
$A=0.0049005$, $B=0.345178$. (b) The sample with $N_{e}$ varying from $16$ to
$22$, with $A$ and $B$ depending on $N_{e}$. (c) Dependence of $A$ in (b) on
$N_{e}$. (d)Dependence of $B$ in (b) on $N_{e}$.

Figure 10:  (a) $\lambda_{c}^{H}$ as a function of $N_{e}$, fitted by
$\lambda_{c}^{H}=0.1513*N_{e}+0.07536$. $N_{e}$ varies from $16$ to $22$. (b)
The dependence of the average value of $N_{hc}$ on $N_{e}$, which varies from
$16$ to $22$.

In conclusion, we develop a novel approach to graph problem, by defining
$\mathbb{Z}_{2}$ LGT on the lattice of which the graph is the dual lattice.
Moreover, we present a quantum adiabatic algorithm with time complexity
$O(\frac{1}{g_{c}^{2}}\sqrt{\frac{1}{\varepsilon}N_{e}^{3/2}(N_{v}^{3}+\frac{N_{e}}{g_{c}}}))$,
to obtain the closed-string condensate emerging at the TQPT of the
$\mathbb{Z}_{2}$ LGT, and find that the HC number $N_{hc}$ of in the graph has
a significant effect on the TQPT critical parameter $g_{c}$, providing a novel
quantum algorithm for HC problem. Thereby a new approach to HC problem and P
versus NP in quantum computing is proposed. Given the importance of graph
theory in mathematics and computer science, our approach may also be useful
to, say, deep learning, represented by deep neural networks and are being
integrated with graphical models Johnson  _et al._ (2016); Wang and Yeung
(2016), as well as quantum deep learning Amin  _et al._ (2018); Biamonte  _et
al._ (2017). This work also suggests a new direction of research connecting
graph problems with topological quantum matter.

This work was supported by National Natural Science Foundation of China (Grant
No. 12075059).

## References

  * Shor (1994) P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in  _Proceedings 35th Annual Symposium on Foundations of Computer Science_ (1994) pp. 124–134.
  * van Leeuwen (1991) J. van Leeuwen, ed.,  _Handbook of Theoretical Computer Science (Vol. B): Formal Models and Semantics_ (MIT Press, Cambridge, MA, USA, 1991).
  * Garey and Johnson (1990) M. R. Garey and D. S. Johnson,  _Computers and Intractability; A Guide to the Theory of NP-Completeness_ (W. H. Freeman & Co., USA, 1990).
  * Bellman (1962) R. Bellman, “Dynamic programming treatment of the travelling salesman problem,” J. ACM 9, 61 (1962).
  * Björklund (2010) A. Björklund, “Determinant sums for undirected hamiltonicity,” in  _2010 IEEE 51st Annual Symposium on Foundations of Computer Science_ (2010) pp. 173–182.
  * Mahasinghe  _et al._ (2019) Anuradha Mahasinghe, Richard Hua, Michael J. Dinneen, and Rajni Goyal, “Solving the hamiltonian cycle problem using a quantum computer,” in  _Proceedings of the Australasian Computer Science Week Multiconference_, ACSW 2019 (Association for Computing Machinery, New York, NY, USA, 2019).
  * Kogut (1979) J. B. Kogut, “An introduction to lattice gauge theory and spin systems,” Rev. Mod. Phys. 51, 659 (1979).
  * Sachdev (2018) S. Sachdev, “Topological order, emergent gauge fields, and fermi surface reconstruction,” Rep. Prog. Phys. 82, 014001 (2018).
  * Lloyd (1996) S. Lloyd, “Universal quantum simulators,” Science 273, 1073 (1996).
  * Zohar  _et al._ (2017) E. Zohar, A. Farace, B. Reznik, and J. I. Cirac, “Digital quantum simulation of z(2) lattice gauge theories with dynamical fermionic matter,” Phys. Rev. Lett. 118, 5 (2017).
  * Cui  _et al._ (2020) X. Cui, Y. Shi, and J. C. Yang, “Circuit-based digital adiabatic quantum simulation and pseudoquantum simulation as new approaches to lattice gauge theory,” J. High Energy Phys 2020, 160 (2020).
  * Lamm  _et al._ (2019) H. Lamm, S. Lawrence, and Y. Yamauchi (NuQS Collaboration), “General methods for digital quantum simulation of gauge theories,” Phys. Rev. D 100, 034518 (2019).
  * Levin and Wen (2005) M. A. Levin and X. G. Wen, “String-net condensation: A physical mechanism for topological phases,” Phys. Rev. B 71, 045110 (2005).
  * Wen (2005) X. G. Wen, “An introduction to quantum order, string-net condensation, and emergence of light and fermions,” Ann. Phys. 316, 1 (2005).
  * Wegner (1971) F. J. Wegner, “Duality in generalized ising models and phase transitions without local order parameters,” J. Math. Phys. 12, 2259 (1971).
  * Freedman (2003) M. Freedman, “A magnetic model with a possible chern-simons phase,” Commun. Math. Phys. 234, 129183 (2003).
  * Fradkin (2013) E. Fradkin,  _Field Theories of Condensed Matter Physics_ (Cambridge University Press, Cambridge, 2013).
  * Hamma and Lidar (2008) A. Hamma and D. A. Lidar, “Adiabatic preparation of topological order,” Phys. Rev. Lett. 100, 4 (2008).
  * Trotter (1959) H. F. Trotter, “On the product of semi-groups of operators,” Proc. Am. Math. Soc. 10, 545 (1959).
  * Childs  _et al._ (2019) A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, “A Theory of Trotter Error,” arXiv e-prints , arXiv:1912.08854 (2019).
  * Jones  _et al._ (2019) T. Jones, A. Brown, I. Bush, and S. C. Benjamin, “QuEST and High Performance Simulation of Quantum Computers,” Sci. Rep. 9, 10736 (2019).
  * Johnson  _et al._ (2016) M. J. Johnson, D. Duvenaud, A. B. Wiltschko, S. R. Datta, and R. P. Adams, “Composing graphical models with neural networks for structured representations and fast inference,” arXiv e-prints , arXiv:1603.06277 (2016).
  * Wang and Yeung (2016) H. Wang and D. Yeung, “Towards bayesian deep learning: A framework and some existing methods,” IEEE Trans. Knowl. Data Eng. 28, 3395 (2016).
  * Amin  _et al._ (2018) M. H. Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and R. Melko, “Quantum boltzmann machine,” Phys. Rev. X 8, 021050 (2018).
  * Biamonte  _et al._ (2017) J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, “Quantum machine learning,” Nature 549, 195–202 (2017).


# Re-Evaluating LiDAR Scene Flow

Nathaniel Chodosh
Carnegie Mellon University
<EMAIL_ADDRESS>Deva Ramanan
Carnegie Mellon University
<EMAIL_ADDRESS>Equal contribution. Simon Lucey∗
University of Adelaide
<EMAIL_ADDRESS>
###### Abstract

Popular benchmarks for self-supervised LiDAR scene flow (stereoKITTI, and
FlyingThings3D) have unrealistic rates of dynamic motion, unrealistic
correspondences, and unrealistic sampling patterns. As a result, progress on
these benchmarks is misleading and may cause researchers to focus on the wrong
problems. We evaluate a suite of top methods on a suite of real-world datasets
(Argoverse 2.0, Waymo, and NuScenes) and report several conclusions. First, we
find that performance on stereoKITTI is negatively correlated with performance
on real-world data. Second, we find that one of this task’s key components –
removing the dominant ego-motion – is better solved by classic ICP than any
tested method. Finally, we show that despite the emphasis placed on learning,
most performance gains are caused by pre- and post-processing steps:
piecewise-rigid refinement and ground removal. We demonstrate this through a
baseline method that combines these processing steps with a learning-free
test-time flow optimization. This baseline outperforms every evaluated method.

Figure 1: Recent self-supervised scene flow methods[60, 30, 26, 17] typically
focus on performance on stereoKITTI[35]. We call attention to several
problematic aspects of its semi-synthetic construction. When evaluated on
real-world datasets (Waymo, Argoverse, NuScenes) we find a negative
correlation with stereoKITTI performance. For each method and LiDAR dataset,
we plot a point corresponding to the self-reported end-point error on
stereoKITTI versus the end-point error on dynamic points of that method
trained on real data. For each dataset, we plot the best-fit line to visualize
the correlation.

##  1 Introduction

Research is often guided by improving benchmark performance, but we show that
popular scene flow benchmarks may be guiding research in the wrong direction.
Scene flow, the 3D analog of optical flow [54], can help autonomous vehicles
identify moving objects. Most autonomous vehicles use LiDAR sensors for 3D
perception, creating interest in estimating the dynamic motion between
successive scans [35, 6, 4, 17, 41, 27]. If this task can be accomplished
without relying on labeled data, it can give autonomous vehicles awareness of
moving objects outside the detection taxonomy[43]. The potential for label-
free detection has led to significant interest in self-supervised scene flow
methods [60, 41, 4, 26]. We focus on this self-supervised setting and show
that the standard benchmarks have several fundamental flaws. When evaluated
more realistically, apparent benchmark improvements correspond to stalled or
even decreasing real-world performance (Fig. 1).

Most work follows the evaluation framework from FlowNet3D [35], which
primarily measures the average end-point-error (EPE) across FlyingThings3D
[37] and KITTI-SF [39] (now typically referred to as stereoKITTI). These
datasets have several issues: (1) stereoKITTI samples dynamic objects with an
artificial pattern that differs from the pattern on static objects,
inadvertently providing part of the “answer” to learning-based approaches. (2)
Both FlyingThings3D and stereoKITTI ensure successive point clouds are in one-
to-one correspondence, which is never the case for actual scans. (3) Both
datasets contain an unrealistically high percentage of dynamic points. In
contrast, real-world data is dominated by the background.

Together these issues obfuscate the main challenges of LiDAR scene flow:
identifying the few non-static points and estimating their motions robustly
given the lack of correspondences. We demonstrate the impact of these issues
by evaluating a suite of top methods on several large-scale real-world
datasets (Argoverse, NuScenes, Waymo), finding that performance is _negatively
correlated_ with performance on the standard benchmarks.

We also believe these benchmarks have led researchers to ignore the virtues of
classic optimization-based approaches. Many learning-based methods have been
proposed for first estimating and removing ego-motion[53, 17], but we show
that none outperform Iterative Closest Point (ICP). Furthermore, we show that
the common pre- and post-processing steps of ground removal and enforcing
piecewise-rigidity have a larger impact on performance than any learning
strategy. We show this through a baseline method that combines these steps
with a test-time optimization flow method. This baseline, without any
learning, outperforms every method in our suite and outperforms all self-
supervised methods on the self-reported NuScenes [37] and lidarKITTI [17]
benchmarks. This leads to the conclusion that current learning methods fail to
extract information not present in a single example despite using large
amounts of data.

In summary, our main contributions are:

  * •

An investigation of the weakness of current self-supervised scene flow
evaluations.

  * •

A _dataless_ flow method which gives state-of-the-art results.

  * •

A standard evaluation protocol and codebase along with a “model-zoo” of top
methods as well as flow labels for Argoverse 2.0111Code, weights, and outputs
for all the evaluated methods will be released.

##  2 Related Work

Scene Flow: Scene flow was introduced by [55], who posed the problem in the
stereo RGB setting and spawned a large body of subsequent work [3, 8, 19, 22,
20, 38, 48, 47, 57, 58]. A related problem is non-rigid registration [1, 10,
32, 24, 46], which is focused on fitting dense point clouds or meshes. We are
interested in the setting without images, based purely on sparse LiDAR point
clouds.

Optimization based LiDAR Scene Flow: Dataless LiDAR scene flow estimation was
first proposed by Dewan _et al_. [11]. Inspired by a non-rigid registration
method regularized by the graph Laplacian [13], Pontes _et al_. [49] created
an improved method. Their results were further improved upon by Li _et al_.
[34] with the implicit regularization of coordinate networks [2, 9, 40, 45,
52]. We use [34] as the backbone of our baseline and additionally employ
coordinate networks for height-map estimation. Apart from these, the vast
majority of recent methods have focused on deep learning based solutions.

Self and Weakly-Supervised LiDAR Scene Flow: “Just Go with the Flow” [41]
demonstrated that using a combination of nearest-neighbor and cycle
consistency losses was enough to train the FlowNet3D network, avoiding the
reliance on labeled data. This led to many other works which adopted similar
losses [60, 53, 30, 4]. Others made use of easier to acquire sources of
supervision such as foreground/background segmentation masks [17, 12] or
addressed the synthetic to real domain gap [26]. Of particular relevance are
those methods which make use of ego-motion estimation and piecewise rigid
representations [17, 12, 33]. We show that these steps are critical to good
performance, but find that ICP vastly outperforms learned approaches and that
piecewise rigidity is more effective as a post-processing step than as a loss
regularizer.

Ground Segmentation: In robotics, ground segmentation has been studied as a
subset of general dataless segmentation [42], traversable area identification
[21], and as a pre-processing step for object detection, classification and
tracking [61, 44, 25, 31]. Current scene flow methods do not make use of these
sophisticated methods and instead rely on basic plane fitting [4, 18, 43]. In
order to show how even small improvements to pre- and post- processing steps
can drastically improve scene flow estimation, we propose a simple
segmentation method based on coordinate networks.

##  3 Benchmark Issues

Most self-supervised flow estimation works inherit their evaluation protocol
from [35], which is based on the synthetic FlyingThings3D [37] and stereoKITTI
[39, 16]. Both were created for evaluating RGB-based flow methods and [35]
extended them to point clouds by lifting the optical flow and depth
annotations to 3D. These datasets and protocols suffer from three main
deficiencies.

Figure 2: The correlation between performance on stereoKITTI and performance
on real datasets as a function of how much those datasets violate the one-to-
one correspondence assumption present in stereoKITTI. The more a dataset
violates this assumption (higher chamfer distance due to sparser pointclouds),
the worse the correlation with stereoKITTI performance.

The one-to-one correspondence assumption removes the main challenge of working
with LiDAR data. Since both FlyingThings3D and stereoKITTI are created by
lifting optical flow annotations, the point clouds for each input pair are in
one-to-one correspondence. For each 3D point $\mathbf{p}_{i}$ and ground truth
3D flow $\mathbf{f}_{i}$ in the first frame, there exists a 3D point
$\mathbf{q}_{i}$ in the second frame such that
$\mathbf{p}_{i}+\mathbf{f}_{i}=\mathbf{q}_{i}$. Real-world LiDAR scans do not
have this property. The presence of correspondences fundamentally changes the
LiDAR scene flow problem into a point-matching problem. It has been claimed
that randomly sub-sampling the input breaks this correspondence. However,
given the total number of points in each scan (90k) and the number of sub-
sampled points (8192), there are still an expected 745 corresponding points in
the input. Since each example has only a handful of independent motions, these
correspondences are enough to constrain the solution.

This problem is especially severe for self-supervised scene flow methods
trained using the chamfer distance, a symmetric extension of the nearest
neighbor distance[41]. Essentially, each method deforms the first point cloud
using the predicted flows and then computes the distance to the second point
cloud. The chamfer distance is an excellent self-supervised objective for
point clouds with one-to-one correspondences since the ground truth flow
achieves the minimum distance of 0. However, for real-world point clouds with
no correspondences the chamfer distance becomes a weaker proxy, and even the
ground truth flow will have a non-zero distance. We can quantify this effect
by computing the chamfer distance of the ground truth flows for several real-
world datasets. In Fig. 2 we show the relationship between that quantity and
the slopes of the best-fit lines shown in Fig. 1. As can be seen, the more a
dataset violates the one-to-one assumption, the more _good_ performance on
stereoKITTI indicates _poor_ performance on that dataset.

Figure 3: The performance of ICP and NSFP versus the ratio of dynamic points
in each example. The green region indicates the ratio found in real data and
the red region indicates the ratio found in the stereoKITTI dataset. The
unrealistic dynamic ratio of stereoKITTI causes ICP to appear to perform worse
than it does on real-world data such as Argoverse. Figure 4: An analysis of
the motion profile of points found in various autonomous driving datasets. The
leftmost column is the percentage of points belonging to any tracked object.
The right three columns show those points separated by their speed once ego-
motion has been removed. All three datasets have a very low rate of dynamic
foreground points, in contrast to the typical stereoKITTI benchmark.

Current benchmarks’ unrealistic rates of dynamic motion make estimating ego-
motion seem harder than it is. In any scene, some portion of the measured
points belong to the static background rather than dynamically moving objects.
In real-world LiDAR scans such as those in NuScenes [7], Waymo [27], or
Argoverse 2 [59], the percentage of static points is very high, ranging from
85-100% (Fig. 4). In contrast, FlyingThings3D has 0% static points since it
consists of flying things, and the KITTI-SF dataset has approximately 75-85%
static points. Dealing with this data imbalance is one of the key difficulties
of self-supervised flow estimation but it is not present in the popular
benchmarks. This discrepancy also explains why ICP has been ignored as a
technique for ego-motion estimation[35].

In order to understand why recent methods have neglected ICP, we need to
understand how the amount of dynamic points in a scene affects the performance
of ICP. We manually re-sampled each example in the Argoverse 2.0 validation
dataset to take a specified number of dynamic and static points and then ran a
test-time optimisation scene flow method [34] and ICP [8]. The results (Fig.
3) show that when looking at the total EPE averaged over the entire dataset,
like most evaluations, the performance of ICP steadily degrades as the
percentage of dynamic points increases. At 20% dynamic points, double the rate
of real-world data but approximately the same ratio as KITTI-SF, ICP’s
performance has degraded to significantly below the performance of NSFP. This
explains why early methods which did include ICP in their comparisons [35]
were able to outperform it, leading future methods to leave it out even as
more realistic data became available.

Figure 5: Comparison of sampling patterns from KITTI-SF (left) versus the
corresponding real LiDAR scan (right). KITTI-SF uses dense CAD models for
foreground objects, which makes it easier for learning-based methods to find
them among the sparse LiDAR background points.

Figure 6: An example ground truth segmentation from KITTI-SF (left) compared
with (right) an example prediction from our local model. Note how the model
can even identify parked vs moving cars since only moving vehicles have the
dense sampling pattern.

The sampling pattern of dynamic objects in stereoKITTI gives away the answer
in the input. The ground truth flow and disparity of KITTI-SF were created by
fitting 3D models to the LiDAR points and 2D annotations [38]. This gives the
dynamic objects a distinctive dense sampling pattern that separates them from
the background (see Fig. 5). However, determining which points belong to
moving objects is one of the main challenges and the sampling pattern
effectively gives away the answer in the input. We demonstrate that learning-
based system can simply identify moving objects by the sampling pattern
without learning anything about the motion.

Model: We use a model that takes a small amount of local context and _no
information from the second frame_ , to predict motion segmentation for a
point $\mathbf{p}$. That is, the input to our network is the set of vectors
$\\{\mathbf{q}-\mathbf{p}\mid\forall\mathbf{q}\in\mathcal{N}_{r}(\mathbf{p})\\}$
where $\mathcal{N}_{r}$ is a ball of radius $r$ centered at $\mathbf{p}$. We
use $r=\qty{0.05}{}$ in our experiment. Then we use a standard PointNet
architecture to predict a binary label for the point.

Training: We train our model on the first 150 examples of KITTI-SF and test on
the remaining 50. Note this is essentially the split used by FlowNet3D[35] and
the recent RigidFlow[33] for fine-tuning. We train our network using a cross-
entropy loss weighted by the inverse frequency of each label. For comparison,
we perform the same experiment on real LiDAR scans from Argoverse. We sample
150 scans from the train set and 50 scans from the validation set.

Results: Using only information in a 5cm ball around each point we are able to
segment KITTI-SF with high accuracy. We achieve a mean intersection over union
on the foreground of 0.83 and 0.97 on the foreground. An example is visualized
in Fig. 6. In comparison when we attempt this on real LiDAR scans that do not
have a biased sampling pattern, we achieve foreground and background mean
intersection over union scores of 0.16 and 0.81 respectively. This
demonstrates that the sampling pattern of KITTI-SF makes it trivial to
identify foreground points and should not be used for training or validation.

###  3.1 Real-World Flow Evaluation

Due to these deficiencies, recent works have made progress on improving
results on these benchmarks without improving results on real-world data (Fig.
1). Some of the problems could perhaps be addressed through re-sampling, but
doing so requires modifying the data based on the ground truth static-vs-
dynamic labels. This runs counter to the goal of creating methods that operate
on raw, unlabeled data.

Some works have evaluated on real LiDAR data by transferring synthetic labels
[17], or more commonly by computing flows from object-level tracks [4, 27, 26,
34]. However, those evaluations have been presented as auxiliary results [4,
34] with limited comparisons to existing methods, or without comparison
entirely [27]. As a result, KITTI-SF and FlyingThing3D remain the standard
benchmarks. We argue that evaluating on real-data should be the “gold-
standard” for scene flow as opposed to synthetic benchmarks.

To further emphasise how top learning-based methods fail when evaluated
properly on real data, we also demonstrate that they can be outperformed by a
simple test-time optimization baseline. We construct this baseline by making
small improvements to standard pre- and post-processing steps and wrapping
them around neural scene flow prior.

##  4 Baseline

Figure 7: Our proposed pipeline for LiDAR scene flow based largely on
classical pre- and post-processing.

Our pipeline (Fig. 7), consists mainly of pre- and post-processing steps
around the test-time flow optimization method of [34].

Figure 8: Comparison between NSFP with our proposed pre and post processing
steps (left) and standard NSFP (right). In the (bottom) views points are color
coded by EPE. The (top) detail views show the first and second frames aligned
by the predicted flow. NSFP struggles to represent both foreground and
background motion. We find that first using ICP to remove ego-motion greatly
improves the estimates on dynamic points.

Motion Compensation: Since real-world scenes consist mostly of static
background objects, removing the ego-motion of the sensor makes estimating the
dynamic motion significantly easier (Fig. 8). For datasets such as Argoverse
or Waymo, the ego-motion is provided and we transform the first scan into the
coordinate frame of the second. NuScenes and lidarKITTI also have this
information but previous work has opted to not use it. In this case, we use
ICP [8, 56] to first estimate the ego-motion. We demonstrate experimentally
that this is much more effective than learned approaches.

Figure 9: An example of our ground removal technique on a Waymo [27] scene
with a non-planar ground. In all images, color coding indicates the height of
each point. From left to right: the input point cloud, the result of
thresholding, our result.

Ground Removal: The sampling pattern of a LiDAR sensor creates “swimming”
artifacts as the sensor moves. These artifacts create the appearance of motion
and present a large problem for the nearest neighbor loss function used by
almost all self-supervised methods. The largest artifacts come from the
ground, leading most methods to remove them by height thresholding or by
fitting a plane [4, 35]. This can fail when the ground changes elevation
either from hills or even sidewalks, see Fig. 9. We propose an improvement
based on analyzing the assumptions behind the current approaches. These
assumptions are:

  1. 1.

The sensor has been calibrated such that the ground can be represented as a
height map $h=f(x,y)$.

  2. 2.

Except for a small number of noise returns, all measured points $(x,y,z)$
satisfy $z\geq f(x,y)$

  3. 3.

The ground function $f(x,y)$ is in some way “simple”. Existing methods make
use of this assumption by requiring $f(x,y)=c$ for thresholding or
$f(x,y)=ax+by+c$ for plane fitting.

The issue comes from an overly strict application of assumption (3). Instead,
we allow our height map to be _piecewise linear_ rather than linear. To
represent our piecewise linear height map we use a 3-layer coordinate network
with ReLU activations and 64 hidden units per layer. To fit it we use
assumption (2) to design a one-sided robust loss:

$\mathcal{L}_{height}(h,z)=\begin{cases}(h-z)^{2}&z<h\\\
\text{Huber}(h,z)&h\leq z\end{cases}.$ (1)

The Huber function [23] allows the loss to ignore points high above the
ground. For each point cloud the parameters of our height-map $\theta_{h}$ are
found by optimizing

$\min\limits_{\theta_{h}}\sum\limits_{i=1}^{N}\mathcal{L}_{height}(f_{\theta_{h}}(x_{i},y_{i}),z_{i}).$
(2)

Finally, any points which are less than 0.3m above our predicted ground are
removed.

Scene Flow Estimation: Once the ego-motion and ground points have been
removed, we estimate the scene flow using the method of Li _et al_. [34].
Briefly, this means that we represent the forwards and backward flow using two
coordinate networks $f_{\theta_{fw}},f_{\theta_{bw}}\in\mathbb{R}^{N\times
3}\to\mathbb{R}^{N\times 3}$ which are optimized with gradient descent on the
objective:

$\min\limits_{\theta_{fw},\theta_{bw}}\mathcal{C}(g_{\theta_{fw}}(\mathbf{P}^{t}),\mathbf{P}^{t+\Delta})+\mathcal{C}(g_{\theta_{bw}}(g_{\theta_{fw}}(\mathbf{P}^{t})),\mathbf{P}^{t}).$
(3)

For compactness, we have let $g(\mathbf{X})=f(\mathbf{X})+\mathbf{X}$ and
$\mathcal{C}$ be the truncated symmetric chamfer distance as described in
[34]. We differ from the original method in that we do not use $\ell_{2}$
regularization on the weights. We find that when combined with motion
compensation that regularization leads to zero flow predictions everywhere.

Figure 10: Optimizing for the standard nearest neighbor self-supervised loss
can cause mis-predictions in the presence of strong occlusions. Here, the bed
of the truck is collapsed into the cab by NSFP (left). Our RANSAC non-rigid
refinement step can fix this type of error (right).

Rigid Refinement: Piecewise rigidity has been a common choice of prior for
scene flow estimation and has been widely used for LiDAR scene flow [17, 12,
4]. Many learning-based methods require differentiable rigid refinement for
loss functions, but we show that simply fitting rigid motion to the final
predictions performs better. This is similar to the method of [17] but we use
RANSAC to filter outliers. First we use DBSCAN [14] to produce a set of
clusters $\\{\mathcal{V}_{j}=\\{\mathbf{p}_{k}\\}_{k=1}^{K}\\}_{j=1}^{J}$.
Then for each cluster, we use RANSAC [15] to fit a rigid model to flow
predictions for that cluster. That is for each RANSAC iteration we randomly
sample 3 points $\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{p}_{3}$ (the minimum
required to get a unique solution) and their associated flow vectors
$\mathbf{f}_{1},\mathbf{f}_{2},\mathbf{f}_{3}$ and then fit rigid motion
parameters by solving:

$\min_{\mathbf{R}\in
SO(3),\mathbf{t}\in\mathbb{R}^{3}}\sum_{i=1}^{3}\lVert\mathbf{R}\mathbf{p}_{i}+\mathbf{t}-(\mathbf{p}_{i}+\mathbf{f}_{i})\rVert_{2}^{2},$
(4)

with the Kabsch algorithm [28]. We then compute the norm of the difference
between the raw and rigid flows, considering any below a threshold to be
inliers. At the end of $T$ iterations the rigid parameters with the highest
number of inliers are selected and the parameters are recomputed with respect
to the inlier set producing $\mathbf{R}^{*},\mathbf{t}^{*}$. Since we know
that with motion-compensated inputs the vast majority of flows should be zero,
we further refine the flows by setting the rigid motion parameters to the
identity transform if $\left\lVert\mathbf{t}^{*}\right\rVert_{2}$ is below a
threshold. Then all points in the cluster are assigned the flow
$\mathbf{f}_{i}=\mathbf{R}^{*}\mathbf{p}_{i}+\mathbf{t}^{*}-\mathbf{p}_{i}$.
Points that were not assigned to any cluster by DBSCAN have their predictions
unchanged. The effect of this step can be seen in Fig. 10.

| Supervision | EPE | AccR | AccS
---|---|---|---|---
| Avg | Dynamic | Static | Dynamic | Dynamic
|  | FG | FG | BG | FG | FG
Gojcic [17] | Weak | 0.083 | 0.155 | 0.064 | 0.032 | 0.650 | 0.368
EgoFlow [53] | Weak | 0.205 | 0.447 | 0.079 | 0.090 | 0.111 | 0.018
Sim2Real [26] | Synth | 0.157 | 0.229 | 0.106 | 0.137 | 0.565 | 0.254
PPWC [60] | Self | 0.130 | 0.168 | 0.092 | 0.129 | 0.556 | 0.229
FlowStep3D [30] | Self | 0.161 | 0.173 | 0.132 | 0.176 | 0.553 | 0.248
Odometry | None | 0.198 | 0.583 | 0.010 | 0.000 | 0.108 | 0.002
ICP [8] | None | 0.204 | 0.557 | 0.025 | 0.028 | 0.112 | 0.015
NSFP [34] | None | 0.088 | 0.193 | 0.033 | 0.039 | 0.542 | 0.327
Ours | None | 0.055 |  0.105 | 0.033 | 0.028 | 0.777 | 0.537
Table 1: Quantitative results on Argoverse 2. Our baseline predicts the motion of dynamic objects by 30% over [17], despite that method using ground truth foreground masks for training. We also see from the static background EPE that ICP outperforms learning-based methods at predicting ego-motion. | Supervision | EPE | AccR | AccS
---|---|---|---|---
| Avg | Dynamic | Static | Dynamic | Dynamic
|  | FG | FG | BG | FG | FG
Gojcic [17] | Weak | 0.084 | 0.145 | 0.060 | 0.047 | 0.714 | 0.436
EgoFlow [53] | Weak | 0.236 | 0.520 | 0.074 | 0.114 | 0.105 | 0.022
Sim2Real [26] | Synth | 0.214 | 0.305 | 0.143 | 0.194 | 0.426 | 0.155
PPWC [60] | Self | 0.156 | 0.197 | 0.097 | 0.173 | 0.468 | 0.183
FlowStep3D [30] | Self | 0.156 | 0.155 | 0.090 | 0.224 | 0.660 | 0.370
ICP | None | 0.176 | 0.450 | 0.033 | 0.046 | 0.151 | 0.047
NSFP | None | 0.088 | 0.130 | 0.034 | 0.101 | 0.711 | 0.447
Ours | None | 0.055 | 0.061 | 0.020 | 0.083 | 0.891 | 0.681
Table 2: Quantitative results on NuScenes. Our baseline halves the EPE on dynamic objects when compared to the next best method (NSFP). Since our baseline also uses NSFP as its backbone, this indicates that pre- and post-processing steps can have an enormous impact. Again we also see that ICP has the best ego-motion prediction. | Supervision | EPE | AccR | AccS
---|---|---|---|---
| Avg | Dynamic | Static | Dynamic | Dynamic
|  | FG | FG | BG | FG | FG
Gojcic [17] | Weak | 0.059 | 0.108 | 0.045 | 0.025 | 0.844 | 0.584
EgoFlow [53] | Weak | 0.183 | 0.390 | 0.069 | 0.089 | 0.178 | 0.046
Sim2Real [26] | Synth | 0.132 | 0.180 | 0.075 | 0.142 | 0.497 | 0.217
PPWC [60] | Self | 0.132 | 0.180 | 0.075 | 0.142 | 0.497 | 0.217
FlowStep3D [30] | Self | 0.169 | 0.152 | 0.123 | 0.232 | 0.708 | 0.405
ICP | None | 0.192 | 0.498 | 0.022 | 0.055 | 0.172 | 0.047
NSFP | None | 0.100 | 0.171 | 0.021 | 0.108 | 0.539 | 0.331
Ours | None | 0.041 | 0.073 | 0.013 | 0.039 | 0.877 | 0.726
Table 3: Quantitative results on Waymo. Our baseline outperforms all tested methods but notably in this instance [17] performs better than ICP at predicting the background ego-motion. | Moving | Static | 50-50
---|---|---|---
| EPE | Accuracy Relax | EPE | EPE
Zero | 0.6381 | 0.1632 | 0.5248 | 0.5814
ICP | 0.2101 | 0.6151 | 0.0290 | 0.1196
PPWC | 0.3539 | 0.2543 | 0.1974 | 0.2756
EgoFlow | 0.7399 | 0.0000 | 0.0570 | 0.3985
SLIM (U) | 0.1050 | 0.7365 | 0.0925 | 0.0987
Ours | 0.0625 | 0.894 | 0.0660 | 0.064
SLIM (S) | 0.0702 | 0.8921 | 0.0499 | 0.0600
Table 4: The results of our baseline on NuScenes as evaluated by Baur _et al_. [4]. U and S refer to the unsupervised and fully-supervised versions of their method. Our dataless baseline outperforms all self-supervised methods and even achieves comparable and superior results to the fully supervised network. | Supervision | EPE | AccS | AccR
---|---|---|---|---
PPWC [60] | Full | 0.710 | 0.114 | 0.219
FLOT [50] | Full | 0.773 | 0.084 | 0.177
MeteorNet [36] | Full | 0.277 | / | /
Gojcic [17] | Weak | 0.133 | 0.460 | 0.746
Gojcic++ | Weak | 0.102 | 0.686 | 0.819
Dong (Waymo Open) [12] | Weak | 0.077 | 0.812 | 0.906
Dong (Semantic KITTI) | Weak | 0.065 | 0.857 | 0.940
Ours | None | 0.061 | 0.917 | 0.962
Table 5: Results of our method on lidarKITTI w/ ground [17]. We outperform all
existing methods without using any training data.

##  5 Evaluation

Our central claim is that the use of popular benchmarks causes leading methods
to degrade in quality when evaluated on real-world data. The main result in
support of this is shown in Fig. 1; here we detail the procedure used to
select, train, and evaluate the tested methods (Sec. 5.1). We also discuss the
performance of our baseline, which we find outperforms all the tested methods,
as well as validate these results through comparison to other authors’s self-
reported metrics on NuScenes and lidarKITTI (Sec. 5.2). Finally, we evaluate
our ground segmentation method (Sec. 5.3).

###  5.1 Training and Evaluation Protocol

Evaluation Metrics: We use a set of standard metrics:

  * •

EPE: Average end-point-error _i.e_. the $\ell_{2}$ norm of the difference
between predicted and ground truth flow.

  * •

Accuracy Relax: Ratio of predictions with absolute EPE less than 0.1m or
relative error below 0.1.

  * •

Accuracy Strict: Same as Accuracy Relax but with a threshold of 0.05.

Rather than averaging these metrics over the entire dataset, we break them
into three classes of points: dynamic foreground, static foreground, and
static background. Points are considered belonging to the foreground if they
are contained in the bounding box of some tracked object and they are
considered dynamic if they have a flow magnitude of at least
$0.5\text{\,}\mathrm{m}\text{\,}{\mathrm{s}}^{-1}$. The choice of threshold is
discussed in the supplement. Separating the metrics in this way is vital due
to the low ratio of dynamic to static points, without it the metrics are
dominated by performance on the static background. In order to produce a
single number for ranking purposes we combine the EPE results on the classes
into a three-way average similar to [4]. In order to save computation we
evaluate on a subset on of each dataset’s validation split. We use the entire
NuScenes validation set, and every 5th frame of the Argoverse and Waymo
validation sets.

Method Selection: We chose to evaluate 6 methods to serve as a thorough
exploration of recent research. Methods were chosen if they presented a self
or weakly supervised method, appeared in a recent conference, and made
available a working implementation of their method. This led us to choose:
PointPWC Net [60], EgoFlow [53], FlowStep3D [30], NSFP [34], Sim2Real [26],
and Gojcic _et al_. [17]. Additionally, we include as baselines an off-the-
shelf ICP [5] implementation [56]. Most of the baseline methods clip points to
a depth of 35m [60, 26, 53, 30]. To make comparisons fair we only include
points contained in a 70m square around the sensor as was done in [4].

Training Procedure: As much as possible we attempted to use the same training
strategy as the original authors, but we also wished to enforce
standardization on the amount of computing resources allocated to each method.
As a result, we chose to adopt the two-stage training regime from [60]. First,
we train for seven days on a quarter of the whole training set followed by
five days of fine-tuning on the entire dataset. Each method was trained using
the largest batch size possible on a single NVIDIA T4 GPU (some methods were
not set up for multi-GPU training), and using the authors’ optimizer and
learning rate schedule. Methods that were able to include ground truth ego-
motion in their loss formulation were also given that information. We also
used ground truth foreground/background masks to train the weakly supervised
method [17]. The only method that required substantial changes was [26] as its
training is based on transferring information from a synthetic labeled
dataset. The synthetic data comes from a virtual depth camera, so we clip the
LiDAR points to match the field of view.

Results: Our results can be found in tables 1, 2, and 3. The main result in
Fig. 1 was created by taking the dynamic foreground error for each learning
method/dataset combination and plotting it against their self-reported
stereoKITTI error. We use the dynamic foreground EPE since this is the hardest
and most important component of the real-world scene flow problem. We remove
EgoFlow from these plots since it is a large outlier in terms of both real-
world dynamic EPE and stereoKITTI EPE.

We also claim that synthetic benchmarks are causing researchers to focus on
the wrong problems, which we test by comparing the tested methods to our
simple test-time optimization baseline. Validating this claim, we can observe
that our baseline outperforms all tested methods despite not using any
training data; even Gojcic _et al_. who use ground truth foreground masks.
Each tested method claims some learning-based novelty as its main
contribution, which is then shown to be effective through experiments on
KITTI-SF and FlyingThings3D. However, none can outperform a carefully designed
baseline when evaluated on real data. Further validating this claim is the
fact that no method was able to match the performance of ICP at predicting the
ego-motion. This is in spite of the fact that several of the methods [17, 4,
53] explicitly claim ego-motion predictions as a benefit of their
architectures. As discussed in Sec. 3, this results from the unrealistic
dynamic ratio found in the standard benchmarks. Gojcic _et al_. comes the
closest to outperforming ICP and does so on Waymo. However, this is because it
essentially incorporates ICP as a part of its final test-time refinement of
the ego-motion.

###  5.2 Existing Benchmark Comparison

There may be some concern that the tested methods performed poorly compared to
the baseline due to a lack of tuning of hyperparameters. To address this
concern, we also compare our baseline to self-reported metrics on two real-
world datsets: NuScenes as evaluted in [4] and lidarKITTI which was introduced
by the Gojcic _et al_. [17].

NuScenes: The authors of SLIM [4] also reported numbers on real-world data. As
can be seen in Tab. 4 our method vastly outperforms SLIM and the other methods
they tested on the main 50-50 EPE metric, dynamic EPE, and dynamic accuracy.
Again, ICP performs far better than every other method on static points. We
also include the SLIM results when trained in a supervised manner and show
that we achieve comparable and some superior results, despite not using any
training data.

lidarKITTI: lidarKITTI [17] was generated by associating KITTI-SF labels with
the raw LiDAR scans. We use the version with ground points as ground removal
is a component of our method. Ground point flow is set to the ego-motion. The
results are shown in Tab. 5 and further confirm that our baseline performs
well even compared to self-reported numbers. It substantially outperforms all
but one of the existing self- and weakly-supervised methods.

###  5.3 Ground Segmentation

We close with an evaluation of our ground segmentation method. First, we
present a qualitative example (Fig. 9) showing our method effectively handling
a scene with a non-planar ground. To quantitatively analyze our method we need
to consider what constitutes failure. The subtlety lies in the ill-defined
nature of the ground, making it impossible to define normal precision and
recall metrics. Given that our goal is motion estimation, the failure we are
most concerned with is classifying a dynamic point as belonging to the ground.
Therefore we look at the rate at which we make this error. On NuScenes we find
that 99.3% of the time points which are classified as ground are in fact
static and achieve a rate of 99.4% on Waymo.

##  6 Conclusion

We re-examined the evaluations of self- and weakly- supervised scene flow
methods in the context of autonomous driving and found several deficiencies.
We claimed that these deficiencies are impacting the quality and types of
recently proposed methods. To provide evidence for this claim we evaluated a
large number of top methods on several real-world datasets. We found a
negative correlation between performance on the standard stereoKITTI benchmark
and performance on all of the real-world datasets. Additionally, we proposed a
dataless estimation technique that far outperformed the existing approaches,
demonstrating that focus on the current benchmarks is causing researchers to
ignore effective methods. Given that our baseline is based on pre- and post-
processing techniques, we believe that other methods not based on test-time
optimization will also benefit from them.

## References

  * [1] Brian Amberg, Sami Romdhani, and Thomas Vetter.  Optimal step nonrigid icp algorithms for surface registration.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 1–8. IEEE, 2007\.
  * [2] Matan Atzmon and Yaron Lipman.  Sal: Sign agnostic learning of shapes from raw data.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 2565–2574, 2020\.
  * [3] Tali Basha, Yael Moses, and Nahum Kiryati.  Multi-view scene flow estimation: A view centered variational approach.  Int. J. Comput. Vis., 101(1):6–21, 2013.
  * [4] Stefan Andreas Baur, David Josef Emmerichs, Frank Moosmann, Peter Pinggera, Björn Ommer, and Andreas Geiger.  Slim: Self-supervised lidar scene flow and motion segmentation.  In Int. Conf. Comput. Vis., pages 13126–13136, 2021.
  * [5] Albert E Beaton and John W Tukey.  The fitting of power series, meaning polynomials, illustrated on band-spectroscopic data.  Technometrics, 16(2):147–185, 1974.
  * [6] Aseem Behl, Despoina Paschalidou, Simon Donné, and Andreas Geiger.  Pointflownet: Learning representations for rigid motion estimation from point clouds.  In Int. Conf. Comput. Vis., pages 7962–7971, 2019.
  * [7] Holger Caesar, Varun Bankiti, Alex H Lang, Sourabh Vora, Venice Erin Liong, Qiang Xu, Anush Krishnan, Yu Pan, Giancarlo Baldan, and Oscar Beijbom.  nuscenes: A multimodal dataset for autonomous driving.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 11621–11631, 2020\.
  * [8] Yang Chen and Gérard Medioni.  Object modelling by registration of multiple range images.  Img. Vis. Comput., 10(3):145–155, 1992.
  * [9] Zhiqin Chen and Hao Zhang.  Learning implicit fields for generative shape modeling.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 5939–5948, 2019\.
  * [10] Haili Chui and Anand Rangarajan.  A new point matching algorithm for non-rigid registration.  Comput. Vis. Img. Und., 89(2-3):114–141, 2003.
  * [11] Ayush Dewan, Tim Caselitz, Gian Diego Tipaldi, and Wolfram Burgard.  Rigid scene flow for 3d lidar scans.  In Int. Conf. Intel. Rob. Sys., pages 1765–1770. IEEE, 2016.
  * [12] Guanting Dong, Yueyi Zhang, Hanlin Li, Xiaoyan Sun, and Zhiwei Xiong.  Exploiting rigidity constraints for lidar scene flow estimation.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 12776–12785, 2022\.
  * [13] Marvin Eisenberger, Zorah Lahner, and Daniel Cremers.  Smooth shells: Multi-scale shape registration with functional maps.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 12265–12274, 2020\.
  * [14] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu.  A density-based algorithm for discovering clusters in large spatial databases with noise.  In Int. Conf. Know. Disc. Data Min., KDD’96, page 226–231. AAAI Press, 1996.
  * [15] Martin A Fischler and Robert C Bolles.  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  Comm. ACM, 24(6):381–395, 1981.
  * [16] Andreas Geiger, Philip Lenz, and Raquel Urtasun.  Are we ready for autonomous driving? the kitti vision benchmark suite.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 3354–3361. IEEE, 2012.
  * [17] Zan Gojcic, Or Litany, Andreas Wieser, Leonidas J Guibas, and Tolga Birdal.  Weakly supervised learning of rigid 3d scene flow.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 5692–5703, 2021\.
  * [18] Xiuye Gu, Yijie Wang, Chongruo Wu, Yong Jae Lee, and Panqu Wang.  Hplflownet: Hierarchical permutohedral lattice flownet for scene flow estimation on large-scale point clouds.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 3254–3263, 2019\.
  * [19] Simon Hadfield and Richard Bowden.  Kinecting the dots: Particle based scene flow from depth sensors.  In Int. Conf. Comput. Vis., pages 2290–2295. IEEE, 2011.
  * [20] Simon Hadfield and Richard Bowden.  Scene particles: Unregularized particle-based scene flow estimation.  IEEE Trans. Pattern Anal. Mach. Intell., 36(3):564–576, 2013.
  * [21] Michael Himmelsbach, Felix V Hundelshausen, and H-J Wuensche.  Fast segmentation of 3d point clouds for ground vehicles.  In Intel. Veh. Symp. IV, pages 560–565. IEEE, 2010.
  * [22] Michael Hornacek, Andrew Fitzgibbon, and Carsten Rother.  Sphereflow: 6 dof scene flow from rgb-d pairs.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 3526–3533, 2014\.
  * [23] Peter J Huber.  Robust estimation of a location parameter.  In Breakthroughs in statistics, pages 492–518. Springer, 1992.
  * [24] Shahram Izadi, David Kim, Otmar Hilliges, David Molyneaux, Richard Newcombe, Pushmeet Kohli, Jamie Shotton, Steve Hodges, Dustin Freeman, Andrew Davison, and Andrew Fitzgibbon.  Kinectfusion: Real-time 3d reconstruction and interaction using a moving depth camera.  In User Int. Soft. Tech., ’11, page 559–568, New York, NY, USA, 2011. Association for Computing Machinery.
  * [25] Víctor Jiménez, Jorge Godoy, Antonio Artuñedo, and Jorge Villagra.  Ground segmentation algorithm for sloped terrain and sparse lidar point cloud.  IEEE Access, 9:132914–132927, 2021.
  * [26] Zhao Jin, Yinjie Lei, Naveed Akhtar, Haifeng Li, and Munawar Hayat.  Deformation and correspondence aware unsupervised synthetic-to-real scene flow estimation for point clouds.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 7233–7243, 2022\.
  * [27] Philipp Jund, Chris Sweeney, Nichola Abdo, Zhifeng Chen, and Jonathon Shlens.  Scalable scene flow from point clouds in the real world.  IEEE Rob. Aut. Letters, 7(2):1589–1596, 2021.
  * [28] Wolfgang Kabsch.  A solution for the best rotation to relate two sets of vectors.  Acta Crystallographica Section A: Crystal Physics, Diffraction, Theoretical and General Crystallography, 32(5):922–923, 1976.
  * [29] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [30] Yair Kittenplon, Yonina C Eldar, and Dan Raviv.  Flowstep3d: Model unrolling for self-supervised scene flow estimation.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 4114–4123, 2021\.
  * [31] Seungjae Lee, Hyungtae Lim, and Hyun Myung.  Patchwork++: Fast and robust ground segmentation solving partial under-segmentation using 3d point cloud.  In Int. Conf. Intel. Rob. Sys., pages 13276–13283. IEEE, 2022.
  * [32] Hao Li, Robert W Sumner, and Mark Pauly.  Global correspondence optimization for non-rigid registration of depth scans.  In Comput. Graph. For., volume 27, pages 1421–1430. Wiley Online Library, 2008.
  * [33] Ruibo Li, Chi Zhang, Guosheng Lin, Zhe Wang, and Chunhua Shen.  Rigidflow: Self-supervised scene flow learning on point clouds by local rigidity prior.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 16959–16968, 2022\.
  * [34] Xueqian Li, Jhony Kaesemodel Pontes, and Simon Lucey.  Neural scene flow prior.  Adv. Neural Inform. Process. Syst., 34:7838–7851, 2021.
  * [35] Xingyu Liu, Charles R Qi, and Leonidas J Guibas.  Flownet3d: Learning scene flow in 3d point clouds.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 529–537, 2019\.
  * [36] Xingyu Liu, Mengyuan Yan, and Jeannette Bohg.  Meteornet: Deep learning on dynamic 3d point cloud sequences.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 9246–9255, 2019\.
  * [37] Nikolaus Mayer, Eddy Ilg, Philip Hausser, Philipp Fischer, Daniel Cremers, Alexey Dosovitskiy, and Thomas Brox.  A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 4040–4048, 2016\.
  * [38] Moritz Menze and Andreas Geiger.  Object scene flow for autonomous vehicles.  In Int. Conf. Comput. Vis., pages 3061–3070, 2015.
  * [39] Moritz Menze, Christian Heipke, and Andreas Geiger.  Joint 3d estimation of vehicles and scene flow.  ISPRS Annals Photo. Rem. Sens. Spat. Inf. Sci., 2:427, 2015.
  * [40] Lars Mescheder, Michael Oechsle, Michael Niemeyer, Sebastian Nowozin, and Andreas Geiger.  Occupancy networks: Learning 3d reconstruction in function space.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 4460–4470, 2019\.
  * [41] Himangi Mittal, Brian Okorn, and David Held.  Just go with the flow: Self-supervised scene flow estimation.  In IEEE Conf. Comput. Vis. Pattern Recog., June 2020.
  * [42] Frank Moosmann, Oliver Pink, and Christoph Stiller.  Segmentation of 3d lidar data in non-flat urban environments using a local convexity criterion.  In Intel. Veh. Symp. IV, pages 215–220. IEEE, 2009.
  * [43] Mahyar Najibi, Jingwei Ji, Yin Zhou, Charles R Qi, Xinchen Yan, Scott Ettinger, and Dragomir Anguelov.  Motion inspired unsupervised perception and prediction in autonomous driving.  In Eur. Conf. Comput. Vis., pages 424–443. Springer, 2022.
  * [44] Patiphon Narksri, Eijiro Takeuchi, Yoshiki Ninomiya, Yoichi Morales, Naoki Akai, and Nobuo Kawaguchi.  A slope-robust cascaded ground segmentation in 3d point cloud for autonomous vehicles.  In Int. Conf. Intel. Trans. Sys., pages 497–504. IEEE, 2018.
  * [45] Jeong Joon Park, Peter Florence, Julian Straub, Richard Newcombe, and Steven Lovegrove.  Deepsdf: Learning continuous signed distance functions for shape representation.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 165–174, 2019\.
  * [46] Mark Pauly, Niloy J Mitra, Joachim Giesen, Markus H Gross, and Leonidas J Guibas.  Example-based 3d scan completion.  In Symp. Geom. Proc., pages 23–32, 2005.
  * [47] Jean-Philippe Pons, Renaud Keriven, and Olivier Faugeras.  Multi-view stereo reconstruction and scene flow estimation with a global image-based matching score.  Int. J. Comput. Vis., 72(2):179–193, 2007.
  * [48] J-P Pons, Renaud Keriven, O Faugeras, and Gerardo Hermosillo.  Variational stereovision and 3d scene flow estimation with statistical similarity measures.  In Int. Conf. Comput. Vis., volume 2, pages 597–597. IEEE Computer Society, 2003.
  * [49] Jhony Kaesemodel Pontes, James Hays, and Simon Lucey.  Scene flow from point clouds with or without learning.  In Int. Conf. 3D Vis., pages 261–270. IEEE, 2020.
  * [50] Gilles Puy, Alexandre Boulch, and Renaud Marlet.  Flot: Scene flow on point clouds guided by optimal transport.  In Eur. Conf. Comput. Vis., pages 527–544. Springer, 2020.
  * [51] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 652–660, 2017\.
  * [52] Vincent Sitzmann, Julien Martel, Alexander Bergman, David Lindell, and Gordon Wetzstein.  Implicit neural representations with periodic activation functions.  Adv. Neural Inform. Process. Syst., 33:7462–7473, 2020.
  * [53] Ivan Tishchenko, Sandro Lombardi, Martin R Oswald, and Marc Pollefeys.  Self-supervised learning of non-rigid residual flow and ego-motion.  In Int. Conf. 3D Vis., pages 150–159. IEEE, 2020.
  * [54] Sundar Vedula, Simon Baker, Peter Rander, Robert Collins, and Takeo Kanade.  Three-dimensional scene flow.  In IEEE Conf. Comput. Vis. Pattern Recog., volume 2, pages 722–729. IEEE, 1999.
  * [55] Sundar Vedula, Simon Baker, Peter Rander, Robert Collins, and Takeo Kanade.  Three-dimensional scene flow.  In Int. Conf. Comput. Vis., volume 2, pages 722–729. IEEE, 1999\.
  * [56] Ignacio Vizzo, Tiziano Guadagnino, Benedikt Mersch, Louis Wiesmann, Jens Behley, and Cyrill Stachniss.  KISS-ICP: In Defense of Point-to-Point ICP – Simple, Accurate, and Robust Registration If Done the Right Way.  IEEE Robotics and Automation Letters (RA-L), 8(2):1029–1036, 2023\.
  * [57] Christoph Vogel, Konrad Schindler, and Stefan Roth.  3d scene flow estimation with a rigid motion prior.  In Int. Conf. Comput. Vis., pages 1291–1298. IEEE, 2011.
  * [58] Christoph Vogel, Konrad Schindler, and Stefan Roth.  Piecewise rigid scene flow.  In Int. Conf. Comput. Vis., pages 1377–1384, 2013.
  * [59] Benjamin Wilson, William Qi, Tanmay Agarwal, John Lambert, Jagjeet Singh, Siddhesh Khandelwal, Bowen Pan, Ratnesh Kumar, Andrew Hartnett, Jhony Kaesemodel Pontes, et al.  Argoverse 2: Next generation datasets for self-driving perception and forecasting.  In Neur. Inform. Process. Syst. Data. Bench. Track, 2021.
  * [60] Wenxuan Wu, Zhi Yuan Wang, Zhuwen Li, Wei Liu, and Li Fuxin.  Pointpwc-net: Cost volume on point clouds for (self-) supervised scene flow estimation.  In Eur. Conf. Comput. Vis., pages 88–107. Springer, 2020.
  * [61] Dimitris Zermas, Izzat Izzat, and Nikolaos Papanikolopoulos.  Fast segmentation of 3d point clouds: A paradigm on lidar data for autonomous vehicle applications.  In Int. Conf. Rob. Aut., pages 5067–5073. IEEE, 2017.

##  Appendix A Expected Number of Correspondences

In Sec. 3 of the main paper, we point out that randomly subsampling
stereoKITTI’s input point clouds does not fix the one-to-one correspondence
issue because there are still an expected 745 points with correspondences.
Here, we explain how we arrived at that number. Each example in stereoKITTI
comprises approximately 90,000 pairs of points $(p_{i},q_{i})$. Many methods
uniformly sample 8192 points from the $p_{i}$’s, and the $q_{i}$’s separately.
For each chosen $p_{i}$ there is some probability that its corresponding
$q_{i}$ is also chosen as input, and there is a random variable $X$, which is
the number of times this happens. We are interested in computing the
expectation of this random variable. Let $\Phi$ be the indices of the 8192
points chosen for the first frame. Now let $x_{i}$ be an indicator random
variable that is 1 if $q_{i}$ is chosen as input and 0 otherwise. Observe that
$X=\sum_{i\in\Phi}x_{i}$ and $\mathbb{E}[x_{i}]=p(q_{i}\text{ is
chosen})=\frac{8192}{90000}$. By the linearity of expectation:
$\mathbb{E}[X]=\sum_{i\in\Phi}\mathbb{E}[x_{i}]=8192\cdot\frac{8192}{90000}\approx
745$.

##  Appendix B Label Creation

Multiple authors have used ground truth multi-object tracks to scene-flow
labels[4, 27]. We follow the same procedure to create labels for Argoverse
2.0.

Problem Statement: We assume as input two point clouds
$\mathbf{P}^{t}\in\mathbb{R}^{N\times
3},\mathbf{P}^{t+\Delta}\in\mathbb{R}^{M\times 3}$. The superscript indicates
that these point clouds are separated by a small time delta (usually $\Delta$
= 0.1s), and the variables $N,M$ indicate that the two point clouds have
different numbers of points. The goal is to predict a set of flow vectors
$\\{\mathbf{f}_{i}\in\mathbb{R}^{3}\\}_{i=1}^{N}$ which describe the motion of
each point from time $t$ to time $t+\Delta$. Some datasets also give access to
the ego-motion of the sensor since in the autonomous vehicle setting this
information is available from odometry or GPS.

Flow Label Creation: For each point cloud in a MOT dataset we have a set of
oriented bounding boxes $\\{B_{i}^{t}\\}_{i=1}^{K}$. For each $B_{i}^{t}$, if
the second frame at time $t+\Delta$ contains a corresponding bounding box
$B^{t+\Delta}_{j}$, we can extract the rigid transformation
$\mathbf{R}_{i}^{t},\mathbf{t}_{i}^{t}$ that transforms points in the first
box to the second. For each point $\mathbf{p}_{j}$ inside the bounding box we
assign it the flow
$\mathbf{f}_{j}=\mathbf{R}_{i}\mathbf{p}_{j}+\mathbf{t}_{i}$. Points not
belonging to any bounding box are assigned the ego-motion as flow. For objects
which only appear in one frame, we cannot compute the ground truth flow and so
they are ignored for evaluation purposes but included in the input.

Limitations: This procedure for producing flow labels has two drawbacks. First
is that all the points inside a bounding box may not be moving rigidly. While
it is important to be aware of this we believe the errors introduced are small
since most objects are rigid vehicles and the sampling rate of 10Hz prevents
large deviations from the model. Second, there can exist objects that are not
captured by the tracking labels but are nonetheless dynamic. This second
limitation is the main reason for our interest in self- and un-supervised
methods as existing work has demonstrated degradation of supervised
performance on objects not included in the training labels [27]. However, it
is supervised training that creates the correlation between performance on an
object class and its presence in the labels. For self-supervised methods we
expect performance on tracked objects to correlate with those that may be
missing.

##  Appendix C Local Dynamic Segmentation Model Details

Figure 11: Our local segmentation model only uses information about the
relative position of points in a local neighborhood around the predicted
point. The local and global MLPs each have two hidden layers of 64 units.

In Sec. 3 of the main paper, we use a local classification model to
demonstrate how the sampling pattern of dynamic objects in stereoKITTI makes
it trivial to identify moving vs. static objects. Here we give details of the
architecture of that model. The architecture is shown in Fig. 11 and is
essentially a very simple version of PointNet[51] with the transform modules
removed. The key component of this model is that the input contains only the
relative positions of the query point’s neighbors, so no global information is
available to the network.

##  Appendix D Optimization Details

Our baseline uses 6 parameters, which we detail here. In general, the same
parameters are used across all datasets (Arogverse, Waymo, NuScenes,
lidarKITTI). However, due to the large variations in sparsity in both Waymo
and NuScenes two parameters were adjusted: the early stopping criterion, and
the DBSCAN epsilon parameter. These adjustments were not found through a
parameter search, but by visually inspecting the flow results and clusters
respectively.

Neural Prior Parameters: The forwards and backward flow networks have the same
structure as [34] and we optimize them with the Adam[29] optimizer using a
learning rate of 0.004 and no weight decay. We stop the optimization when no
progress is made for 100 iterations (200 when optimizing on Waymo).

RANSAC Parameters: For all clusters, we do 250 RANSAC iterations and we use an
inlier threshold of 0.2. When thresholding on the translation component, we
use the same threshold as the dataset’s dynamic threshold:
$0.5\text{\,}\mathrm{m}\text{/}\mathrm{s}$.

DBSCAN Parameters: For Argoverse, Waymo and lidarKITTI we use an epsilon
parameter of 0.4 but for NuScenes we increase this to 0.8 due to the sparsity.
For all datasets, we use a minimum point threshold of 10.

##  Appendix E Ablation

To test the components of our method, we performed an ablation study on
Argoverse. The results are shown in Tab. 6 and show that both Motion
Compensation and Rigid Refinement play key roles in improving the performance
of the backbone scene flow method. Motion Compensation has the largest impact
on estimating dynamic motion since it allows the network to simply assign zero
to all background points. The rigid refinement step improves dynamic motion
estimates as well, but also has a large impact on static points. This is due
to it fixing phantom motion estimates on walls caused by “swimming” artifacts.

| EPE | AccR | AccS
---|---|---|---
| Avg | Dynamic | Static | Dynamic | Dynamic
|  | FG | FG | BG | FG | FG
Backbone | 0.088 | 0.193 | 0.033 | 0.039 | 0.542 | 0.327
w/ Motion Compensation | 0.066 | 0.112 | 0.042 | 0.046 | 0.756 | 0.515
w/ Motion & w/ Rigid Refinement | 0.055 | 0.105 | 0.033 | 0.028 | 0.777 | 0.537
Table 6: Ablation of the two main components of our model, motion compensation
and rigid refinement.


# Proof of the Caccetta-Häggkvist conjecture for digraphs with small
independence number

Patrick Hompe

###### Abstract

For a digraph $G$ and $v\in V(G)$, let $\delta^{+}(v)$ be the number of out-
neighbors of $v$ in $G$. The Caccetta-Häggkvist conjecture states that for all
$k\geq 1$, if $G$ is a digraph with $n=|V(G)|$ such that $\delta^{+}(v)\geq
n/k$ for all $v\in V(G)$, then G contains a directed cycle of length at most
$k$. In [2], N. Lichiardopol proved that this conjecture is true for digraphs
with independence number equal to two. In this paper, we generalize that
result, proving that the conjecture is true for digraphs with independence
number at most $(k+1)/2$.

##  1 Introduction and definitions

For the rest of the paper, we use the words cycle and path to refer to a
directed cycle and directed path, respectively, and every graph considered is
a digraph. Furthermore, every digraph $G$ is simple, meaning it has no loops
or parallel edges. Let the girth $g(G)$ of a digraph $G$ be the length of its
shortest cycle, and for a vertex $v\in V(G)$, let $\delta^{+}(v)$ denote the
number of out-neighbors of $v$ in $G$. Let
$\Delta^{+}(G)=\displaystyle\min_{v\in V(G)}\delta^{+}(v)$ be the minimum out-
degree of a vertex in $G$. For vertices $u,v\in V(G)$, let the distance
$d(u,v)$ from $u$ to $v$ be the length of the shortest path from $u$ to $v$
(define this to be zero if $u=v$). For $v\in V(G)$ and $i\geq 1$, let
$N_{i}^{+}(v)$ be the set of vertices $u$ with $d(v,u)=i$, and let
$N_{i}^{-}(v)$ be the set of vertices $u$ with $d(u,v)=i$. For a digraph $G$,
call a set of vertices $H\subset V(G)$ independent if there are no edges
between any two vertices of $H$. Let the independence number $\alpha(G)$ of a
digraph $G$ be the size of the largest independent set $H\subset V(G)$. For
disjoint sets $S_{1},S_{2}\subset V(G)$, say that $S_{1}$ is stable with
$S_{2}$ if there are no edges between a vertex in $S_{1}$ and a vertex in
$S_{2}$.

We begin with the following simple observation.

###### Lemma 1.1

Suppose that $G$ is a digraph containing a cycle; then $g(G)\leq
2\alpha(G)+1$.

Proof. Let $C$ be a cycle of $G$ with minimum length, and suppose $C$ has at
least $2\alpha(G)+2$ vertices. Then there exists a subset $S\subset V(C)$ of
size $\alpha(G)+1$ such that no pair of vertices of $S$ are adjacent in $C$.
Then there is an edge in $G$ between some pair of vertices in $S$, which gives
a shorter cycle in $G$, a contradiction. This proves Lemma 1.1.

The next lemma immediately follows from Lemma 1.1, and is used repeatedly
throughout the paper.

###### Lemma 1.2

Suppose $G$ is a digraph with $g(G)\geq 2\alpha(G)$, and that $H\subset G$ is
a subgraph of $G$ with $\alpha(H)\leq\alpha(G)-1$. Then $H$ is acyclic.

Proof. If $H$ contains a cycle, then Lemma 1.1 shows that $H$ contains a cycle
of length at most $2\alpha(G)-1$, which is a contradiction. This proves Lemma
1.2.

In this paper, we deal with the following formulation of the Caccetta-
Häggkvist conjecture, which was introduced in [References]:

######  Conjecture 1.1 (Caccetta-Haggkvist)

For $d\geq 1$, $k\geq 1$, if $G$ is a digraph with $n=|V(G)|\leq kd$ and
$\Delta^{+}(G)\geq d$, then $g(G)\leq k$.

For $k=1$ and $k=2$ it follows that the digraph is not simple, a
contradiction. So, to prove Conjecture 1.1, we can assume $k\geq 3$.

Now, Lemma 1.1 gives that Conjecture 1.1 is true for $\alpha(G)\leq(k-1)/2$.
In this paper, we prove that Conjecture 1.1 is true for
$\alpha(G)\leq(k+1)/2$.

##  2 Main Results

We need the following two lemmas.

###### Lemma 2.1

Suppose that $G$ is an acyclic digraph; then for all $v\in V(G)$, there exists
a path of length at most $2\alpha(G)-1$ to a vertex of out-degree zero in $G$.

Proof. Since $G$ is acyclic, there exists a path from $v$ to a vertex of out-
degree zero in $G$. Let $P=(v,v_{2},\cdots,v_{k})$ be a shortest such path.
Then $P$ is induced, so if $k\geq 2\alpha(G)+1$ then
$\\{v,v_{3},\cdots,v_{k}\\}\subset V(G)$ is an independent set of size at
least $\alpha(G)+1$, which is a contradiction. Thus $P$ has length at most
$2\alpha(G)-1$, as desired. This proves Lemma 2.1.

###### Lemma 2.2

Let $G$ be an simple digraph with minimum out-degree $d\geq 1$, $\alpha(G)\geq
3$, and $g(G)\geq 2\alpha(G)$. Set $p=2\alpha(G)-3$, and suppose $v\in V(G)$
is a vertex with $\delta^{+}(v)=d$. For odd $1\leq i\leq p$, let $S_{i}$ be
the subgraph of $G$ induced by the vertex set
$V(G)\setminus(N_{1}^{+}(v)\cup\\{v\\}\cup\left(\bigcup_{i=1}^{p}N_{i}^{-}(v)\right)$.
Then, for each odd $1\leq i\leq p$, there exists a unique vertex $v_{i}\in
S_{i}$ such that $N_{1}^{+}(v_{i})\subset N_{i}^{-}(v)$. Furthermore,
$|V(G)\setminus S_{p}|\geq(2\alpha(G)-2)d+1$.

Proof. Every $w\in N_{1}^{+}(v)$ has $N_{1}^{+}(w)\subset N_{1}^{+}(v)\cup
S_{p}$, since otherwise we obtain a cycle of length at most $2\alpha(G)-1$, a
contradiction. Since $|N_{1}^{+}(v)|=d$, it follows that
$V(S_{i})\neq\emptyset$ for odd $1\leq i\leq p$.

Now, for odd $1\leq i\leq p$, we iteratively choose $v_{i}\in S_{i}$ such that
$N_{1}^{+}(v_{i})\subset N_{i}^{-}(v)$. Let $\\{v_{1},v_{3},\cdots,v_{i-2}\\}$
be vertices such that $N_{1}^{+}(v_{j})\subset N_{j}^{-}(v)$ for all odd
$1\leq j\leq i-2$ (if $i=1$, this set of vertices is empty). The set
$T=\\{v,v_{1},v_{3},\cdots,v_{i-2}\\}$ (if $i=1$, then $T=\\{v\\}$) is stable
with $S_{i}$, so $\alpha(S_{i})\leq\alpha(G)-(i+1)/2$, and thus $S_{i}$ is
acyclic by Lemma 1.1. Thus there exists $v_{i}\in S_{i}$ with out-degree zero
in $S_{i}$.

Now, we claim that $N_{1}^{+}(v_{i})\subset N_{i}^{-}(v)$. If not, then
$v_{i}$ has an edge to a vertex $w_{1}\in N_{1}^{+}(v)$, which has an edge to
a vertex $w_{2}\in S_{i}$. Let $H$ be the subgraph of $S_{i}$ induced by the
set of vertices with no edge to $v_{i}$. We may assume $w_{2}\in H$. We have
that $\\{v,v_{1},\cdots,v_{i}\\}$ is stable with $H$, so
$\alpha(H)\leq\alpha(G)-(i+3)/2$. Then by Lemma $2.1$ there exists a path
$(w_{2}\cdots w_{j})$ of length at most $2\alpha(G)-i-4$ from $w_{2}$ to a
vertex $w_{j}\in H$ with out-degree zero in $H$. If $w_{j}$ has out-degree in
$S_{i}$ equal to zero, then since $|N_{1}^{+}(v)|=d$, it follows that $w_{j}$
has an out-neighbor in $N_{i}^{-}(v)$ and we obtain a cycle of length at most
$2\alpha(G)-1$, a contradiction. If instead $w_{j}$ has an out-neighbor to
$w_{j+1}\in S_{i}\setminus H$, then we again obtain a cycle of length at most
$2\alpha(G)-1$, a contradiction. It follows that $v_{i}$ has
$N_{1}^{+}(v_{i})\subset N_{i}^{-}(v)$ for odd $1\leq i\leq p$, as claimed.

Now, for odd $1\leq i\leq p$, let $V_{i}$ be the set of vertices $u\in S_{i}$
such that $u$ has out-degree zero in $S_{i}$. Let $H=\\{v\\}\cup V_{1}\cup
V_{3}\cup\cdots\cup V_{p}$. For $v_{i}\in V_{i}$, since
$N_{1}^{+}(v_{i})\subset N_{i}^{-}(v)$, it follows that $H$ is an independent
set, so $|V(H)|\leq\alpha(G)$. We also know that the $V_{i}$ are nonempty, so
$|V(H)|\geq\alpha(G)$. Thus $|V_{i}|=1$ for all odd $1\leq i\leq p$. This
proves the first part of the lemma, namely that for each odd $1\leq i\leq p$
there exists a unique vertex $v_{i}\in S_{i}$ with $N_{1}^{+}(v_{i})\subset
N_{i}^{-}(v)$. For the remainder of the proof, let
$\\{v_{1},v_{3},\cdots,v_{p}\\}$ be those unique vertices.

For odd $3\leq i\leq p$, define $X_{i}=N_{1}^{+}(v_{i})\subset N_{i}^{-}(v)$,
and let $T_{i}=N_{i}^{-}(v)\cup N_{i-1}^{-}(v)\setminus X_{i}$. $\\{v\\}$ is
stable with $X_{i}$, so by Lemma 1.2, $X_{i}$ is acyclic and contains a vertex
$u_{i}\in V(X_{i})$ with out-degree zero in $X_{i}$. We claim that
$N_{1}^{+}(u_{i})\subset T_{i}$, and consequently $|T_{i}|\geq d$. If not,
then there exists a path of length at most 2 from $u_{i}$ to a vertex
$w_{2}\in S_{i}$. Since $\\{v,v_{1},\cdots v_{i-2}\\}$ is stable with $S_{i}$,
$\alpha(S_{i})\leq\alpha(G)-(i+1)/2$. Lemma 2.1 gives a path from $w_{2}$ to
$v_{i}$ of length at most $2\alpha(G)-5$. These two paths together form a
cycle in $G$ of length at most $2\alpha(G)-2$, which is a contradiction.

Thus, for odd $3\leq i\leq p$, we have $|X_{i}|+|T_{i}|\geq 2d$. Also,
$N_{1}^{+}(v_{i})\subset N_{1}^{-}(v)$ gives $|N_{1}^{-}(v)|\geq d$, and by
the definition of $v$ we have $|N_{1}^{+}(v)|=d$. Together with the vertex
$v$, these give:

$|V(G)\setminus S_{p}|\geq(p-1)d+2d+1=(2\alpha(G)-2)d+1$

as desired. This proves Lemma 2.2.

Lemma 2.2 is used to prove the following two theorems.

###### Theorem 2.1

Suppose that $G$ is a digraph with minimum out-degree $d\geq 1$ and
$n=|V(G)|\leq 2\alpha(G)d$; then $g(G)\leq 2\alpha(G)$.

Proof. As mentioned above, it suffices to consider simple digraphs $G$ with
$\alpha(G)\geq 2$. The case $\alpha(G)=2$ is proved in [References], so we may
further assume that $\alpha(G)\geq 3$. Now, for the sake of contradiction,
suppose that $g(G)\geq 2\alpha(G)+1$. Then Lemma 2.2 implies that
$|V(G)\setminus S_{p}|\geq(2\alpha(G)-2)d+1$, which together with $|V(G)|\leq
2\alpha(G)d$ gives $|S_{p}|\leq 2d-1$. $H=\\{v,v_{1},v_{3},\cdots,v_{p-2}\\}$
is stable with $S_{p}$, so $\alpha(S_{p})=1$ and $S_{p}$ is a transitive
tournament. Let $(w_{1}\cdots w_{r})$ be the unique Hamiltonian path of the
transitive tournament $S_{p}$.

Now, $J=\\{v_{1},v_{3},\cdots,v_{p}\\}$ is stable with $N_{1}^{+}(v)$, so
$N_{1}^{+}(v)$ is a transitive tournament. Let its unique Hamiltonian path be
$(u_{1}\cdots u_{d})$. $N_{1}^{+}(u_{d})\subset S_{p}$, so there is an out-
neighbor $w_{k}$ of $u_{d}$ with $k\geq d$. It follows that $w_{k}$ has an
edge to a vertex not in $S_{p}$. An edge from $w_{k}$ to $v$ or to
$w^{\prime}\in N_{i}^{-}(v)$ for some $1\leq i\leq p$ yields a cycle of length
at most $2\alpha(G)$, a contradiction. If, instead, $w_{k}$ has an edge to
$u^{\prime}\in N_{1}^{+}(v)$, then $u^{\prime}$ has an edge to $u_{d}$, and we
obtain a cycle of length at most three, a contradiction. This proves Theorem
2.1.

###### Theorem 2.2

Suppose $G$ is a digraph with minimum out-degree $d\geq 1$ and
$n=|V(G)|\leq(2\alpha(G)-1)d$; then $g(G)\leq 2\alpha(G)-1$.

Proof. As mentioned above, it suffices to consider simple digraphs $G$ with
$\alpha(G)\geq 2$. The case $\alpha(G)=2$ is proved in [References], so we
further assume that $\alpha(G)\geq 3$. For the sake of contradiction, suppose
$g(G)\geq 2\alpha(G)$. Lemma 2.2 gives a set of vertices $\\{v_{i}\\}$ indexed
by odd $1\leq i\leq p$ such that $N_{1}^{+}(v_{i})\subset N_{i}^{-}(v)$.
$v_{1}$ is stable with $N_{1}^{+}(v)$ (otherwise we obtain a cycle of length
four), so Lemma 1.2 gives that $N_{1}^{+}(v)$ is acyclic. So, there exists
$u\in N_{1}^{+}(v)$ with out-degree zero in $N_{1}^{+}(v)$. If $u$ has an edge
to any vertex not in $S_{p}$, we obtain a cycle of length at most
$2\alpha(G)-1$, a contradiction. Thus, we must have $N_{1}^{+}(u)\subset
S_{p}$ and it follows that $|S_{p}|\geq d$.

But Lemma 2.2 also gives that $|V(G)\setminus S_{p}|\geq(2\alpha(G)-2)d+1$,
which together with $|S_{p}|\geq d$ implies that
$|V(G)|\geq(2\alpha(G)-1)d+1$, contradicting the assumption that
$|V(G)|\leq(2\alpha(G)-1)d$. This proves Theorem 2.2.

###### Theorem 2.3

Conjecture 1.1 is true for digraphs $G$ with $\alpha(G)\leq(k+1)/2$.

Proof. Theorem 2.1 and Theorem 2.2 together with Lemma 1.1 give the desired
result. This proves Theorem 2.3.

## References

  * [1] L. Caccetta, R. Häggkvist, “On minimal digraphs with given girth”, Congr. Numer., 21:181-187, 1978.
  * [2] N. Lichiardopol, “Proof of the Caccetta-Häggkvist conjecture for oriented graphs with positive minimum out-degree and of independence number two”, Discrete Math, 313(14):1540-1542, 2013.