# On the complexity of counting feedback arc sets

Kevin Perrot

###### Abstract

In this note we study the computational complexity of feedback arc set
counting problems in directed graphs, highlighting some subtle yet common
properties of counting classes. Counting the number of feedback arc sets of
cardinality $k$ and the total number of feedback arc sets are
${\mathsf{\\#P}}$-complete problems, while counting the number of minimum
feedback arc sets is only proven to be ${\mathsf{\\#P}}$-hard. Indeed, this
latter problem is ${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$-complete, hence if
it belongs to ${\mathsf{\\#P}}$ then ${\mathsf{P}}={\mathsf{NP}}$.
N.B.: Despite some bibliographic investigations I haven’t found these results
stated anywhere, though they are derived from fairly standard methods and may
be useful. If they are already published please let me know: name.surname@lis-
lab.fr!

##  1 Introduction

Feedback arc sets are natural objects to consider in digraphs, and deciding,
given a digraph $G$ and an integer $k$, whether it contains a feedback arc set
of cardinality at most $k$ is one of Karp’s 21 ${\mathsf{NP}}$-complete
problems [5] (with a reduction not parsimonious). In this note we study the
computational complexity of various feedback arc set counting problems.
Section 2 gives the required definitions, in Section 3 we prove that counting
the number of feedback arc sets of cardinality $k$ and counting the total
number of feedback arc sets are ${\mathsf{\\#P}}$-complete problems, in
Section 4 we study the special case of counting the number of minimum feedback
arc set (which is not in ${\mathsf{\\#P}}$ unless
${\mathsf{P}}={\mathsf{NP}}$), and Section 5 remarks that we can derive
identical results on counting feedback vertex sets.

##  2 Preliminaries

We denote $[n]$ the set of integers $\\{1,\dots,n\\}$. We call graph an
undirected graph $G=(V,E)$ with $E\subseteq\\{\\{u,v\\}\mid u,v\in V\\}$, and
digraph a directed graph $G=(V,A)$ with $A\subseteq V\times V$. We consider
all our graphs and digraphs to be loopless. A vertex cover $C\subseteq V$ of a
graph $G=(V,E)$ is a subset of vertices intersecting every edges of $G$, i.e.
verifying $\forall e\in E:e\cap C\neq\emptyset$. A cycle of length $k$ in a
digraph $G=(V,A)$ is a $k$-tuple of arcs
$((u_{1},v_{1}),(u_{2},v_{2}),\dots,(u_{k},v_{k}))$ such that
$(u_{i},v_{i})\in A$ for all $i\in[k]$, $v_{i}=u_{i+1}$ for all $i\in[k-1]$,
and $u_{1}=v_{k}$. Let $\mathcal{C}(G)$ denote the set of cycles of $G$. If
$\mathcal{C}(G)=\emptyset$ then $G$ is called acyclic. A feedback arc set
$F\subseteq A$ of a digraph $G=(V,A)$ is a subset of arcs intersecting every
cycles of $G$, i.e. verifying $\forall c\in\mathcal{C}(G):c\cap
F\neq\emptyset$. Let $\mathcal{F\\!\\!AS}(G)$ (resp. $\mathcal{VC}(G)$) denote
the set of feedback arc sets (FAS) (resp. vertex covers (VC)) of $G$.

Valiant defined the class of counting problems ${\mathsf{\\#P}}$ in [12, 13].
It is the class of functions counting the number of certificates of decision
problems in ${\mathsf{NP}}$, i.e. problems of the form “given $x$, compute
$f(x)$”, where $f$ is the number of accepting paths of a nondeterministic
Turing machine taking $x$ as input and running in polynomial time. We denote
$f\leq^{p}_{\text{parsi}}g$ when there exists a polynomial parsimonious
reduction from counting problem $f$ on alphabet $\Sigma_{f}$ to counting
problem $g$ on alphabet $\Sigma_{g}$, i.e. a transformation
$r:\Sigma_{f}^{*}\to\Sigma_{g}^{*}$ computable by a deterministic Turing
machine running in polynomial time such that $\forall
x\in\Sigma_{f}^{*}:f(x)=g(r(x))$. We denote $f\leq^{p}_{T}g$ when there exists
a polynomial Turing reduction from $f$ to $g$, i.e. a deterministic Turing
machine computing $f$ with oracle $g$, and running in polynomial time (hence
making a polynomial number of calls to its oracle). Of course $f\leq^{p}_{T}g$
implies $f\leq^{p}_{\text{parsi}}g$.

The hardness for ${\mathsf{\\#P}}$ is defined according to polynomial
parsimonious or polynomial Turing reductions without distinction. Let us
underline that, although they are suitable for ${\mathsf{\\#P}}$-hardness,
Turing reductions are too strong for counting classes above in the polynomial
counting hierarchy [11]. Furthermore, ${\mathsf{\\#P}}$ is known to be closed
for $\leq^{p}_{\text{parsi}}$, but this question is open for $\leq^{p}_{T}$
and known to be equivalent to ${\mathsf{P}}={\mathsf{NP}}$ (see Section 4).

The authors of [3] have developed a remedy to the difficulty of classifying
tightly some problems in ${\mathsf{\\#P}}$ (related to the unknown closure of
${\mathsf{\\#P}}$ for $\leq^{p}_{T}$), in particular minimality and maximality
counting problems, that we will apply in Section 4. It consists in the
counting class ${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$, which is defined in
terms of nondeterministic Turing machines accepting/rejecting and in the same
time outputting a number encoded in binary. We will call such machines
nondeterministic transducers. Then ${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$ is
the class of functions counting the number of accepting paths outputting the
minimal value among all accepting paths, for some nondeterministic transducer
running in polynomial time and outputting values whose binary encoding is of
length $\mathcal{O}(\log n)$ (the definitions of [3] are more general in order
to fit other levels of the polynomial counting hierarchy and other magnitudes
of output length). We will apply the notion of hardness for
${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$ according to polynomial parsimonious
reductions only.

Our complexity results will be derived by reduction from the following
problems.
Cardinality vertex cover (#Card-VC)
Input: A graph $G$ and an integer $k$. Output:
$|\\{C\in\mathcal{VC}(G)\mid|C|=k\\}|$.

######  Theorem 1 ([2, p. 169]).

#Card-VC is ${\mathsf{\\#P}}$-complete.

Minimum cardinality vertex cover (#Minimum-VC)
Input: A graph $G$. Output: $|\\{C\in\mathcal{VC}(G)\mid|C|=m\\}|$ with
$m=\min\\{|C|\mid C\in\mathcal{VC}(G)\\}$.

######  Theorem 2 ([9, by identity reduction from Problem 4]).

#Minimum-VC is ${\mathsf{\\#P}}$-hard.

######  Theorem 3 ([3, Theorem 11]).

#Minimum-VC is ${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$-complete.

##  3 ${\mathsf{\\#P}}$-complete feedback arc set problems

Cardinality feedback arc set (#Card-FAS)
Input: A digraph $G$ and an integer $k$. Output:
$|\\{F\in\mathcal{F\\!\\!AS}(G)\mid|F|=k\\}|$.
Feedback arc set (#FAS)
Input: A digraph $G$. Output: $|\mathcal{F\\!\\!AS}(G)|$.

The first reduction adapts the classical construction from Karp [5].

######  Theorem 4.

#Card-VC $\leq^{p}_{T}$ #Card-FAS, and #Card-FAS is
${\mathsf{\\#P}}$-complete.

###### Proof.

#Card-FAS is in ${\mathsf{\\#P}}$ since given $G=(V,A)$ and $k$, one can guess
nondeterministically a subset $F\subseteq A$ of size $k$, and then check in
polynomial time that the digraph $(V,A\setminus F)$ is acyclic.

For the ${\mathsf{\\#P}}$-hardness, as claimed we construct a polynomial
Turing reduction from #Card-VC which is ${\mathsf{\\#P}}$-hard (Theorem 1).
Given an instance $G=(V,E)$ and $k$ of #Card-VC, we consider an arbitrary
order $\prec$ on $V$ and the digraph
$G^{\prime}(\ell)=(V^{\prime}(\ell),A^{\prime}(\ell))$ with

$V^{\prime}(\ell)=\\{v_{i}\mid v\in V\text{ and
}i\in\\{0,1\\}\\}\cup\\{e_{i,j}\mid e\in E\text{ and }i\in\\{0,1\\}\text{ and
}j\in[\ell]\\},$ $\begin{array}[]{r}A^{\prime}(\ell)=\\{(v_{0},v_{1})\mid v\in
V\\}\cup\Big{\\{}(u_{1},\\{u,v\\}_{0,j}),(\\{u,v\\}_{0,j},v_{0}),(v_{1},\\{u,v\\}_{1,j}),(\\{u,v\\}_{1,j},u_{0})\mid\\\
\\{u,v\\}\in E\text{ and }u\prec v\text{ and }j\in[\ell]\Big{\\}},\end{array}$

for $\ell=k+1$ (the construction is illustrated on Figure 1).

$a$$b$$c$$d$$G=$$a_{0}$$a_{1}$$b_{0}$$b_{1}$$c_{0}$$c_{1}$$d_{0}$$d_{1}$$\\{a,b\\}_{0,i}$
for $i\in[3]$$G^{\prime}(3)=$$a\prec b\prec c\prec d$

Figure 1: Illustration of the construction $G^{\prime}(\ell)$ for $\ell=3$ in
the proof of Theorem 4.

First remark that $k$ is encoded in binary, but since $k\leq|V|$ the
construction is polynomial in size. The idea is to have, for each edge of $G$,
a large set of cycles in $G^{\prime}(\ell)$. In $G^{\prime}(\ell)$ there are
$4\ell|E|$ arcs corresponding to edges of $G$ that are “strictly less
interesting” (when111If $\ell=1$ then $k=0$ and the answer to the #Card-VC
instance is trivial. $\ell>1$) to construct an FAS than the $|V|$ arcs
corresponding to vertices of $G$. As a consequence, there is a one-to-one
correspondence between the minimum VC of $G$ and the minimum FAS of
$G^{\prime}(\ell)$. Let $C(\kappa)$ be the answer to #Card-VC on $G$ for some
integer $\kappa$, let $F(k^{\prime})$ be the answer to #Card-FAS on
$G^{\prime}(\ell)$ for some integer $k^{\prime}$, and let

$m=\min\\{|C|\mid C\in\mathcal{VC}(G)\\}=\\{|F|\mid
F\in\mathcal{F\\!\\!AS}(G^{\prime}(\ell))\\}.$

When $\ell>k^{\prime}\geq m$, an FAS of size $k^{\prime}$ of
$G^{\prime}(\ell)$ can be seen as:

  * •

$\kappa$ arcs corresponding to vertices of $G$ forming a vertex cover for some
$k^{\prime}\geq\kappa\geq m$,

  * •

$k^{\prime}-\kappa$ arcs corresponding to edges of $G$ (among the $4\ell|E|$),

because with $\ell>k^{\prime}$ it is not possible to intersect all cycles
corresponding to an edge of $G$ with only arcs corresponding to edges of $G$.
We can deduce the following relations between $C(\kappa)$ and $F(k^{\prime})$:

$\begin{array}[]{l}F(0)=C(0)=0\\\ \dots\\\ F(m-1)=C(m-1)=0\\\ F(m)=C(m)\\\
F(m+1)=C(m+1)+{4\ell|E|\choose 1}C(m)\\\ F(m+2)=C(m+2)+{4\ell|E|\choose
1}C(m+1)+{4\ell|E|\choose 2}C(m)\\\ \dots\\\
F(m+i)=C(m+i)+\sum_{j=0}^{i-1}{4\ell|E|\choose i-j}C(m+j).\end{array}$

It is therefore possible to compute inductively $C(\kappa)$ from oracle calls
to $F(1),\dots,F(\kappa)$ (corresponding to #Card-FAS instances
$G^{\prime}(\ell)$ with integers $k^{\prime}=1,\dots,\kappa$), and eventually
compute $C(k)$ after a polynomial time since all calls are done for
$k^{\prime}\leq k\leq|V|$. ∎

The second reduction employs the Vandermonde matrix method from [9, 12].

######  Theorem 5.

#Card-FAS $\leq^{p}_{T}$ #FAS, and #FAS is ${\mathsf{\\#P}}$-complete.

###### Proof.

Again #FAS is in ${\mathsf{\\#P}}$ since given $G=(V,A)$, one can guess
nondeterministically a subset $F\subseteq A$, and then check in polynomial
time that the digraph $(V,A\setminus F)$ is acyclic.

For the ${\mathsf{\\#P}}$-hardness, as claimed we construct a polynomial
Turing reduction from #Card-FAS which is ${\mathsf{\\#P}}$-hard (Theorem 4).
Given an instance $G=(V,A)$ and $k$ of #Card-FAS, we consider the family of
digraphs $H^{\prime}(\ell)=(V^{\prime}(\ell),A^{\prime}(\ell))$ with

$V^{\prime}(\ell)=V\cup\\{a_{i}\mid a\in A\text{ and }i\in[\ell-1]\\},$
$A^{\prime}(\ell)=\\{(u,a_{1}),(a_{1},a_{2}),\dots,(a_{\ell-2},a_{\ell-1}),(a_{\ell-1},v)\mid
a=(u,v)\in A\\}$

(the construction is illustrated on Figure 2).

$a$$b$$c$$d$$G=$$a$$b$$c$$d$$(a,b)_{i}$ for $i\in[3]$$G^{\prime}(4)=$

Figure 2: Illustration of the construction $H^{\prime}(\ell)$ for $\ell=4$ in
the proof of Theorem 5.

The idea is that an arc $a=(u,v)$ of $G$ is replaced with a path of $\ell$
arcs in $H^{\prime}(\ell)$ that we will denote

$P_{a}=\\{(u,a_{1}),(a_{1},a_{2}),\dots,(a_{\ell-2},a_{\ell-1}),(a_{\ell-1},v)\\}.$

Hence for each FAS $F$ of $G$ there corresponds a family $\Omega(F)$ of FAS of
$H^{\prime}(\ell)$, with elements of the form $\bigcup_{a\in A}S^{\prime}_{a}$
where

$\begin{array}[]{l}S^{\prime}_{a}\cap P_{a}\neq\emptyset\text{ if }a\in F\\\
S^{\prime}_{a}\cap P_{a}=\emptyset\text{ if }a\notin F.\end{array}$

The family $\Omega(F)$ consists of $(2^{\ell}-1)^{|F|}$ FAS, and the families
$\\{\Omega(F)\mid F\in\mathcal{F\\!\\!AS}(G)\\}$ partition
$\mathcal{F\\!\\!AS}(H^{\prime}(\ell))$. The number of FAS of
$H^{\prime}(\ell)$ is therefore

$\Gamma(\ell)=\sum_{i=0}^{|A|}F_{i}(G)(2^{\ell}-1)^{i}$

where $F_{i}(G)$ is the number of FAS of $G$ of cardinality
$i\in\\{0,\dots,|A|\\}$, i.e.

$F_{i}(G)=|\\{F\in\mathcal{F\\!\\!AS}(G)\mid|F|=i\\}|.$

The $(|A|+1)\times(|A|+1)$ matrix $M=(M_{\ell i})$ with entries $M_{\ell
i}=(2^{\ell}-1)^{i}\text{ for }\ell,i\in\\{0,\dots,|A|\\}$ is Vandermonde222A
matrix (or its transpose) is Vandermonde when its coefficient on the
$i^{\text{th}}$ row and $j^{\text{th}}$ column is of the form $\mu_{i}^{j}$
for some real numbers $\mu_{i}$ (indices start with $0$ hence coefficients
equal 1 on the first column). with bases distinct for all $\ell$, as a
consequence it is nonsingular and from $\Gamma(\ell)$ for
$\ell\in\\{0,\dots,|A|\\}$ we can compute $F_{i}(G)$ for
$i\in\\{0,\dots,|A|\\}$ in polynomial time (see [9, Lemma page 781]). ∎

Let us also mention the following variant.
Minimal feedback arc set (#Minimal-FAS)
Input: A digraph $G$. Output: $|\\{F\in\mathcal{F\\!\\!AS}(G)\mid\forall
F^{\prime}\subsetneq F:F^{\prime}\notin\mathcal{F\\!\\!AS}(G)\\}|$.
It is proven in [10] that #Minimal-FAS is ${\mathsf{\\#P}}$-complete, with a
parsimonious reduction from counting the number of acyclic orientations of an
undirected graph, itself proven to be ${\mathsf{\\#P}}$-hard in [6]. #Minimal-
FAS belongs to ${\mathsf{\\#P}}$ since the set of feedback arc sets is
obviously closed by arc addition, hence one can check in polynomial time that
for any $a\in F$ the digraph $(V,A\setminus(F\setminus\\{a\\}))$ is not
acyclic.

######  Theorem 6 ([10, Corollary 1]).

#Minimal-FAS is ${\mathsf{\\#P}}$-complete.

##  4 Counting minimum feedback arc sets

Minimum feedback arc set (#Minimum-FAS)
Input: A digraph $G$. Output: $|\\{F\in\mathcal{F\\!\\!AS}(G)\mid|F|=m\\}|$
with $m=\min\\{|F|\mid F\in\mathcal{F\\!\\!AS}(G)\\}$.

In contrast to counting the number of minimal objects, counting the number of
minimum objects reveals some subtle facts about counting complexity classes.
It is indeed not an obvious task at all to check in polynomial time whether a
feedback arc set $F$ is of minimum size (intuitively this would require to
compute $m$ in polynomial time, but deciding if $m\leq k$ for a given $k$ is
well known to be ${\mathsf{NP}}$-complete [5]). Fortunately the literature on
counting problems provides appropriate tools to characterize the complexity of
#Minimum-FAS.

From standard technics we derive the following.

######  Theorem 7.

#Minimum-VC $\leq^{p}_{\text{parsi}}$ #Minimum-FAS,
#Minimum-FAS is ${\mathsf{\\#P}}$-hard and ${\mathsf{\\#P}}$-easy.

###### Proof.

The construction $G^{\prime}(2)$ from the proof of Theorem 4 is a polynomial
parsimonious reduction from #Minimal-VC to #Minimum-FAS, which is therefore
${\mathsf{\\#P}}$-hard by Theorem 2. Indeed, a minimum FAS in $G^{\prime}(2)$
contains no arc corresponding to edges of $G$, hence there is a one-to-one
correspondence between minimum FAS in $G^{\prime}(2)$ and minimum VC in $G$.

For the ${\mathsf{\\#P}}$-easiness, there is a straightforward polynomial
Turing reduction to #Card-FAS which is in ${\mathsf{\\#P}}$ (Theorem 4): one
can simply call the oracle with the digraph $G=(V,A)$ for $k=0,1,\dots$ until
the first time its answer is not zero (which happens at least when $k=|V|$),
this is the number of minimum FAS. ∎

Although the class ${\mathsf{\\#P}}$ is closed for polynomial parsimonious
reductions (meaning that $A\leq^{p}_{\text{parsi}}B$ and $B\in{\mathsf{\\#P}}$
implies $A\in{\mathsf{\\#P}}$), the closure of ${\mathsf{\\#P}}$ for
polynomial Turing reductions is an open question333Note that the analogous
question regarding the closure of ${\mathsf{NP}}$ under polynomial Turing
reduction is also open, while ${\mathsf{NP}}$ is known to be closed under
polynomial many-one reductions. (and is equivalent to
${\mathsf{P}}={\mathsf{NP}}$, as we will see). For more on closure properties
of ${\mathsf{\\#P}}$ see [1, 7, 8, 11] The authors of [3] defined the
complexity class ${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$ (and analogous
classes for problems higher in the polynomial counting hierarchy) for which
minimality (or maximality) problems such as #Minimum-FAS are provably444More
precisely with a proof of appropriate difficulty, since all these are complete
if ${\mathsf{P}}={\mathsf{NP}}$… complete.

######  Theorem 8.

#Minimum-FAS is ${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$-complete.

###### Proof.

#Minimum-FAS is in ${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$ since given
$G=(V,A)$, one can guess nondeterministically a subset $F\subseteq A$, then
check in polynomial time that the digraph $(V,A\setminus F)$ is acyclic, and
reject or output the size of $F$ encoded in binary before accepting.

We already proved in Theorem 7 that #Minimum-VC $\leq^{p}_{\text{parsi}}$
#Minimum-FAS, hence from Theorem 3 #Minimum-FAS is
${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$-hard. ∎

Thanks to a result of [3] we can nicely complement Theorem 7.

######  Corollary 1.

If #Minimum-FAS is in ${\mathsf{\\#P}}$ then ${\mathsf{P}}={\mathsf{NP}}$.

###### Proof.

If #Minimum-FAS is in ${\mathsf{\\#P}}$ then ${\mathsf{\\#\\!\cdot\\!OptP[\log
n]}}={\mathsf{\\#P}}$ from Theorems 7 and 8 (it straightforwardly holds that
${\mathsf{\\#P}}\subseteq{\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$), hence the
result follows from a direct application of [3, Theorem 9] for $k=0$. ∎

##  5 Complexity of counting feedback vertex sets

There is a straightforward polynomial parsimonious reduction from counting
feedback arc sets to counting feedback vertex sets in a digraph. A feedback
vertex set (FVS) of a digraph $G$ is a subset of vertices intersecting every
cycle of $G$ (i.e. containing, for every cycle of $G$, at least one vertex
from its arcs). The reduction, as noted in [10], consists in considering the
line digraph of $G=(V,A)$, denoted $L(G)=(V^{\prime},A^{\prime})$ and defined
as

$V^{\prime}=A\text{, and }((u,v),(v,w))\in A^{\prime}\text{ for all }u,v,w\in
V\text{ such that }(u,v),(v,w)\in A.$

Indeed, there is one-to-one correspondence between the cycles of $G$ and
$L(G)$, and a one-to-one correspondence between the FAS of $G$ and the FVS of
$L(G)$. As a consequence (${\mathsf{\\#P}}$ and
${\mathsf{\\#\\!\cdot\\!OptP[\log n]}}$ being closed for
$\leq^{p}_{\text{parsi}}$), all the results of this note also apply to
counting the number of feedback vertex sets.

Remark that counting the number of minimum feedback vertex sets is known to be
${\mathsf{\\#P}}$-hard even when restricted to planar digraphs [4].

##  6 Acknowledgments

The author is thankful to Madhav Marathe for helpful correspondence. This work
received financial support from the _Young Researcher_ project
ANR-18-CE40-0002-01 “FANs”, the project ECOS-CONICYT C16E01, the project STIC
AmSud CoDANet 19-STIC-03 (Campus France 43478PD).

## References

  * [1] L. Fortnow and N. Reingold.  PP is closed under truth-table reductions.  Information and Computation, 124(1):1–6, 1996.
  * [2] M. R. Garey and D. S. Johnson.  Computers and Intractability; A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [3] M. Hermann and R. Pichler.  Complexity of counting the optimal solutions.  Theoretical Computer Science, 410(38):3814–3825, 2009.
  * [4] H. B. Hunt, M. V. Marathe, V. Radhakrishnan, and R. E. Stearns.  The complexity of planar counting problems.  SIAM Journal on Computing, 27:1142–1167, 1998.
  * [5] R. M. Karp.  Reducibility among combinatorial problems.  In Complexity of Computer Computations, pages 85–103, 1972.
  * [6] N. Linial.  Hard enumeration problems in geometry and combinatorics.  SIAM Journal on Algebraic Discrete Methods, 7:331–335.
  * [7] M. Ogihara, T. Thierauf, S. Toda, and O. Watanabe.  On closure properties of #P in the context of PF$\circ$#P.  Journal of Computer and System Sciences, 53(2):171–179, 1996.
  * [8] M. Ogiwara and L. A. Hemachandra.  A complexity theory for feasible closure properties.  Journal of Computer and System Sciences, 46(3):295–325, 1993.
  * [9] J. S. Provan and M. O. Ball.  The complexity of counting cuts and of computing the probability that a graph is connected.  SIAM Journal on Computing, 12:777–788.
  * [10] B. Schwikowski and E. Speckenmeyer.  On enumerating all minimal solutions of feedback problems.  Discrete Applied Mathematics, 117(1):253–265, 2002.
  * [11] S. Toda and O. Watanabe.  Polynomial-time 1-Turing reductions from #PH to #P.  Theoretical Computer Science, 100(1):205–221, 1992.
  * [12] L. G. Valiant.  The complexity of enumeration and reliability problems.  SIAM Journal on Computing, 8:410–421.
  * [13] L. G. Valiant.  The complexity of computing the permanent.  Theoretical Computer Science, 8(2):189–201, 1979.


# Electric field induced topological phase transition and large enhancements
of spin-orbit coupling and Curie temperature in two-dimensional ferromagnetic
semiconductors

Jing-Yang You  Kavli Institute for Theoretical Sciences, and CAS Center for
Excellence in Topological Quantum Computation, University of Chinese Academy
of Sciences, Beijing 100190, China  Xue-Juan Dong  School of Physical
Sciences, University of Chinese Academy of Sciences, Beijing 100049, China  Bo
Gu<EMAIL_ADDRESS>Kavli Institute for Theoretical Sciences, and CAS Center
for Excellence in Topological Quantum Computation, University of Chinese
Academy of Sciences, Beijing 100190, China  Physical Science Laboratory,
Huairou National Comprehensive Science Center, Beijing 101400, China  Gang Su
<EMAIL_ADDRESS>Kavli Institute for Theoretical Sciences, and CAS Center for
Excellence in Topological Quantum Computation, University of Chinese Academy
of Sciences, Beijing 100190, China  School of Physical Sciences, University of
Chinese Academy of Sciences, Beijing 100049, China  Physical Science
Laboratory, Huairou National Comprehensive Science Center, Beijing 101400,
China

###### Abstract

Tuning topological and magnetic properties of materials by applying an
electric field is widely used in spintronics. In this work, we find a
topological phase transition from topologically trivial to nontrivial states
at an external electric field of about 0.1 V/Å in MnBi2Te4 monolayer that is a
topologically trivial ferromagnetic semiconductor. It is shown that when
electric field increases from 0 to 0.15 V/Å, the magnetic anisotropy energy
(MAE) increases from about 0.1 to 6.3 meV, and the Curie temperature Tc
increases from 13 to about 61 K. The increased MAE mainly comes from the
enhanced spin-orbit coupling due to the applied electric field. The enhanced
Tc can be understood from the enhanced $p$-$d$ hybridization and decreased
energy difference between $p$ orbitals of Te atoms and $d$ orbitals of Mn
atoms. Moreover, we propose two novel Janus materials MnBi2Se2Te2 and
MnBi2S2Te2 monolayers with different internal electric polarizations, which
can realize quantum anomalous Hall effect (QAHE) with Chern numbers $C$=1 and
$C$=2, respectively. Our study not only exposes the electric field induced
exotic properties of MnBi2Te4 monolayer, but also proposes novel materials to
realize QAHE in ferromagnetic Janus semiconductors with electric polarization.

##  I Introduction

Quantum anomalous Hall effect (QAHE) as a novel topological phase has
attracted tremendous interest because of its potential applications in
dissipationless spintronics Haldane (1988); Onoda and Nagaosa (2003); Liu  _et
al._ (2008); Wu (2008); Yu  _et al._ (2010); Chang  _et al._ (2013); Wu  _et
al._ (2014); Mogi  _et al._ (2015); Chang  _et al._ (2015); Liu  _et al._
(2016); Si  _et al._ (2017); You  _et al._ (2019a); Ou  _et al._ (2017); He
_et al._ (2018); You  _et al._ (2019b); Li  _et al._ (2020a). The QAHE was
firstly realized experimentally in Cr-doped (Bi, Sb)2Te3 thin film at 30 mK
Chang  _et al._ (2013) and later in V-doped (Bi, Sb)2Te3 thin film at 25 mK
Chang  _et al._ (2015) and Cr-doped (Bi, Sb)2Te3 thin film at about 2 K Mogi
_et al._ (2015). Then, the QAHE was observed in a Cr- and V-codoped (Bi,
Sb)2Te3 system at about 300 mK Ou  _et al._ (2017). Since magnetic order that
is stable at high temperature is essential for QAHE, we need to increase the
ordering temperature of a magnetically-doped topological insulator.

MnBi2Te4 as a new platform to realize QAHE has gained extensive studies both
in theory and in experiments Otrokov  _et al._ (2017, 2019a). MnBi2Te4 is
composed of septuple Te–Bi–Te–Mn–Te–Bi–Te sequences, and exhibits a van der
Waals layered structure Lee  _et al._ (2013). Bulk MnBi2Te4 is an
antiferromagnetic insulator with the Ne$\acute{e}$l temperature of 25 K Cui
_et al._ (2019); Li  _et al._ (2020b), which presents the axion state Zhang
_et al._ (2019). Topological surface states with diminished gap forming a
characteristic Dirac cone attributed to multidomains of different
magnetization orientations were observed in antiferromagnetic topological
insulator MnBi2Te4 Chen  _et al._ (2019). The heterostructures
(Bi2Te3)n(MnBi2Te4) were extensively studied to realize QAHE. Vidal  _et al._
(2019); Aliev  _et al._ (2019); Deng  _et al._ (2020a); Lei  _et al._ (2020);
Rienks  _et al._ (2019); Hu  _et al._ (2020); Klimovskikh  _et al._ (2020).
MnBi2Te4 monolayer is a topologically trivial ferromagnetic semiconductor Li
_et al._ (2019a, b); Otrokov  _et al._ (2019b), while its multilayers host the
states alternating between QAH and zero plateau QAH for odd and even number of
monolayers, respectively Otrokov  _et al._ (2019b). In a five-septuple-layer
MnBi2Te4, the QAHE was observed at 1.4 K, and the quantization temperature can
be raised up to 6.5 K by an external magnetic field to align all layers
ferromagnetically Deng  _et al._ (2020b). High-Chern-number QHE without Landau
levels was obtained in ten-septuple-layer MnBi2Te4 under applied magnetic
field and back gate voltages Ge  _et al._ (2020). In six-septuple-layer
MnBi2Te4, the axion insulator state occurs over a wide magnetic field range
and at relatively high temperatures, while a moderate magnetic field can drive
the axion insulator phase to a Chern insulator phase with QAHE Liu  _et al._
(2020).

Tuning the energy gap is widely used in spintronics, because it can optimize
the properties of materials and make materials have better performance in
devices. There are several ways to tune the energy bands, such as by an
electric field Weisheit  _et al._ (2007); Deng  _et al._ (2018); Jiang  _et
al._ (2018); Du  _et al._ (2020), strain Ni  _et al._ (2008); Liu  _et al._
(2013); Dong  _et al._ (2019), doping Sim  _et al._ (2015); You  _et al._
(2019c); Ahmed  _et al._ (2015); You  _et al._ (2020), vacancy Chen  _et al._
(2017); Liu  _et al._ (2019); Hou  _et al._ (2020), surface modification Sim
_et al._ (2015); Nemani  _et al._ (2018) and so on. Tuning energy bands by an
external electric field has some advantages: the magnitude and direction of
the external electric field can be arbitrarily controlled; applying the
external electric field is feasible and easy to realize in experiments.
Graphene is a two-dimensional (2D) material with a zero band gap that
restricts its application in electronic devices. After applying a gate
voltage, the inversion symmetry is broken and a nonzero band gap is opened
Ohta  _et al._ (2006); Min  _et al._ (2007); Zhang  _et al._ (2009); Mak  _et
al._ (2009); Lui  _et al._ (2011). The band engineering by external electric
fields was also performed in MoS2 Lu  _et al._ (2014).

In this work, we study novel properties of MnBi2Te4 monolayer controlled by an
electric field. With the increase of electric field, the band gap decreases
and the band inversion with a topological phase transition occurs at an
electric field of about 0.1 V/Å, and the system then enters into a topological
state. With the electric field ranging from 0 to 0.15 V/Å, the magnetic
anisotropy energy (MAE) increases from about 0.1 to 6.3 meV, and the Curie
temperature Tc increases from 13 to about 61 K. The increased MAE mainly comes
from the enhanced spin-orbit coupling (SOC) due to the applied electric field.
By means of the super-exchange picture, the enhanced Tc can be understood from
the enhanced $p$-$d$ hybridization and decreased energy difference between $p$
orbitals of Te atoms and $d$ orbitals of Mn atoms. Inspired by the electric
field induced topological phase transition, we propose 2D Janus materials
MnBi2Se2Te2 and MnBi2S2Te2 with different internal electric polarizations,
which can realize QAHE. Our findings not only reveal the electric field
induced exotic properties of MnBi2Te4 monolayer, but also present a new idea
to realize QAHE in novel ferromagnetic Janus materials with electric
polarizations.

##  II Calculation method

Our first-principles calculations were based on density functional theory
(DFT) as implemented in the Vienna Ab initio Simulation Package (VASP) Kresse
and Furthmüller (1996), using the projector augmented-wave method Blöchl
(1994). The generalized gradient approximation with the Perdew-Burke-Ernzerhof
Perdew  _et al._ (1996) realization was adopted for the exchange-correlation
functional. We set the on-site effective Hubbard interaction $U$ = 4 eV in
considering electron correlation of 3$d$ electrons of Mn atoms. The monolayer
was placed under a vacuum layer of 15 Å. The plane-wave cutoff energy was set
to 550 eV. A Monkhorst-Pack k-point mesh Monkhorst and Pack (1976) with a size
of 19$\times$19$\times$1 was used for the BZ sampling. The crystal structure
was optimized until the forces on the ions were less than 0.0001 eV/Å, and the
total energy was converged to 10-8 eV with Gaussian smearing method. The
interaction of the magnetic dipoles was taken into account in calculations of
the magnetic anisotropy energies. The phonon spectra were obtained in a
4$\times$4$\times$1 supercell with the PHONOPY package Togo and Tanaka (2015).
The surface spectrum was calculated by using the Wannier functions and the
iterative Green’s function method Marzari and Vanderbilt (1997); Souza  _et
al._ (2001); Wu  _et al._ (2018); Sancho  _et al._ (1985).

Figure 1: Crystal structure of monolayer MnBi2Te4. The (a) top and (b) side
view of monolayer MnBi2Te4, where the atoms are labeled with elements and
atomic layer number in (b). (c) The evolution of the top of valence band and
the bottom of conduction band relative to their energy center at $\Gamma$
point with increasing the electric field.

##  III Monolayer MnBi2Te4

Monolayer MnBi2Te4 can be grown in a quintuple layer of Bi2Te3 and a bilayer
of MnTe with the molecular beam epitaxy method Gong  _et al._ (2019). The
crystal structure of monolayer MnBi2Te4 is shown in Fig 1. The space group is
P$\bar{3}$m1 (No. 164) with an optimized lattice constant $a$ = 4.34 Å.
Monolayer MnBi2Te4 is a ferromagnetic semiconductor with out-of-plane
magnetization, and the Curie temperature TC of its seven septuple-layers film
is about 20 K Gong  _et al._ (2019). Our estimated Curie temperature of
monolayer MnBi2Te4 is comparable with that of its film Gong  _et al._ (2019);
Sup . The atom projected band structure of monolayer MnBi2Te4 without electric
field was plotted in Fig. 2(a), from which one can observe that the bottom of
conduction band of monolayer MnBi2Te4 is mainly attributed to Bi-1 and Bi-2
atoms, while the main contribution to the top of valence bands is from Te-4
and Te-1 atoms. Because of the inversion symmetry, Bi-1 and Bi-2 atoms give
equal contributions to the density of states of the bottom of conduction bands
at $\Gamma$ point, and Te-1 and Te-4 atoms contribute equally to the density
of states of the top of valence bands at $\Gamma$ point.

##  IV Monolayer MnBi2Te4 under an electric field

By applying an electric field E normal to the atoms plane, we can tune the
properties of monolayer MnBi2Te4. The effect of electric field on the
properties of monolayer MnBi2Te4 is summarized in Table S1. There are three
main changes of the properties of monolayer MnBi2Te4 with increasing the
electric field, including the changes of band gap, magnetic anisotropy and
exchange integral.

Figure 2: Electric field induced topological phase transition. Atom projected
electronic band structures of monolayer MnBi2Te4 under the electric field of
(a) 0.00, (b) 0.05, (c) 0.10 and (d) 0.11 V/Å, respectively. The electric
field dependent (e) direct band gap at $\Gamma$ point and (f) anomalous Hall
conductivity (AHC). The results were obtained by the GGA+SOC+$U$ calculations
with $U$ = 4 eV.

###  IV.1 Evolution of band gap under an electric field

The band structure of monolayer MnBi2Te4 varies with increasing the electric
field without a big deformation of profiles but with a remarkable change of
the band gap as shown in Fig. 2. The evolution of the band gap at $\Gamma$
point with the electric field was schematically plotted in Fig. 1 (c). The
direct band gap at $\Gamma$ point [Fig. 2(e)] as well as the global band gap
increases with increasing the electric field lower than 0.1 V/Å. This is
intuitive, because on one hand, the electric field E breaks the inversion
symmetry of monolayer MnBi2Te4 resulting in the degeneracy broken of Bi-1 and
Bi-2, Te-1 and Te-4 atoms at $\Gamma$ point, respectively, and on the other
hand, the effect of electric field on the upper triple Te-Bi-Te layers
consisting of Te-1, Bi-1, and Te-2 atoms is equivalent to electron doping,
while for the lower triple Te-Bi-Te layers consisting of Te-3, Bi-2, and Te-4
atoms it corresponds to hole doping. Thus, for the cation Bi-1, its energy
level moves downward close to Fermi level, while for anion Te-4, its energy
level moves upward close to Fermi level. This analysis is also verified by our
DFT results as shown in Fig. 2. Therefore, the energy levels of Bi-1 and Te-4
atoms should be touched at a proper electric field, which is about 0.1 V/Å in
our calculations. When the electric field continues to increase to 0.11 V/Å,
an inversion of the energy bands occurs at $\Gamma$ point [Fig. 2(d)] with a
topological phase transition from a topological trivial state to a nontrivial
state with nonzero Chern number $C$=1. However, because there is no global
energy gap, we cannot observe a quantized AHC, but it can adiabatically evolve
to the quantum anomalous Hall insulating state. When the electric field
continues to increase from 0.13 to 0.15 V/Å, the direct band gap at $\Gamma$
point decreases, and the system turns into the topological state with $C$=2.
Although there is also no global gap, it is interesting to note that a
relatively flat plateau of AHC occurs with E=0.15 V/Å near Fermi level as
shown in Fig. 2(f).

Figure 3: Electric field enhanced spin-orbit coupling. The (a) electric field
and (b) SOC strength dependent MAE, where MAE means the energy difference per
MnBi2Te4 formula unit between the in-plane and out-of-plane magnetic
configurations and the SOC strength under the electric field of 0.15 V/Å is
set to 1. The (c) electric field and (d) SOC strength dependent gap difference
between the gaps without and with SOC.

###  IV.2 Magnetic anisotropy of MnBi2Te4 monolayer under an electric field

Besides the topological phase transition, the electric field also dramatically
influences magnetic anisotropy energy (MAE), where MAE means the energy
difference per MnBi2Te4 formula unit between the out-of plane and in-plane
ferromagnetic configurations. The electric field E dependent MAE was plotted
in Fig. 3(a). From Fig. 3(a), one may observe that MAE increase with
increasing E. MAE are usually related to the SOC, thus the increase of MAE may
come from the enhanced SOC because of the electric field. To verify this
observation, we extracted the dependence of MAE on the SOC strength with the
electric field of 0.15 V/Å from DFT calculations, and obtained the electric
field dependent SOC strength by comparing the MAE under different electric
fields and SOC strength as plotted in Fig. 3(b). It is obvious that the SOC is
enhanced with increasing the electric field. A larger anomalous Hall
conductivity (AHC) $\sigma_{xy}$ is expected in monolayer MnBi2Te4 with
enhanced SOC. We calculated the AHC with electric fields of 0.05, 0.10 and
0.15 V/Å, respectively, as shown in Fig. 2(f). Enhanced SOC can also be seen
from the enhanced AHC as shown in Fig. 2(f) and the gap difference between the
band gaps without SOC and with SOC in Figs. 3(c) and (d) with increasing the
electric field. The Mn local magnetic moment is not sensitive to the electric
field, and in the range of electric field we studied, it keeps at about 4.5
$\mu_{B}$.

Figure 4: Electric field enhanced Curie temperature. The evolution of the (a)
exchange integrals and (b) Curie temperature with electric field. (c) The
schematic diagram of the micromechanism of enhanced Curie temperature under
electric field. Figure 5: QAHE in monolayers MnBi2Se2Te2 and MnBi2S2Te2. (a)
Band structure, (b) AHC and (c) electric field dependent band gap and Curie
temperature of monolayer MnBi2Se2Te2. (d) Band structure, (e) AHC and (f) edge
states of monolayer MnBi2S2Te2.

###  IV.3 Curie temperature under an electric field

The exchange integral $J$ shares the similar dependence on the electric field,
i.e. the exchange integral increases with the increase of E as shown in Fig.
4(a). The increase of exchange integral $J$ can be interpreted by the
superexchange interaction Goodenough (1955); Anderson (1959); Kanamori (1960),
where the FM coupling is expected since the Mn-Te-Mn bond angle is close to
90∘. The indirect FM coupling between Mn atoms is proportional to the direct
AFM coupling between neighboring Mn and Te atoms. The magnitude of this direct
AFM coupling can be roughly estimated as $J_{pd}=|V_{pd}|^{2}/|E_{p}-E_{d}|$,
where $|V_{pd}|$ is the hopping matrix element between $p$ orbitals of Te and
$d$ orbitals of Mn, and $|E_{p}-E_{d}|$ is the energy difference between them.
By using maximally localized Wannier orbital projections, the dominant hopping
matrix elements $|V_{pd}|$ and their corresponding energy differences
$|E_{p}-E_{d}|$ can be obtained for monolayer MnBi2Te4 without E and with
E=0.15V/Å, respectively, as listed in Table S2. The enhanced direct AFM
coupling with increasing the electric field comes from the enhanced $p$-$d$
hybridization owing to the increase of hopping and the decrease of energy
difference between $p$ orbitals of Te and $d$ orbitals of Mn. It can be
understood from that the energy levels of Mn atoms are relatively deep in
MnBi2Te4, and the electric field drives the energy levels of the upper and
lower Te layers near Mn layer to move downward, resulting in the decrease of
the energy level difference and the enhancement of the overlaps between $p$
orbitals of Te and $d$ orbitals of Mn atoms as schematically depicted in Fig.
4(c).

The calculated Curie temperature based on the isotropic Heisenberg model with
the single ion anisotropy (SIA) using Monte Carlo (MC) simulation was listed
in Table S1. It can be seen that for MnBi2Te4 with E=0.15 V/Å the Curie
temperature is even about 4.5 times larger than that without E as shown in
Fig. 4(b).

##  V Novel monolayers MnBi2Se2Te2 and MnBi2S2Te2 for QAHE

Inspired by the above study, where an electric field can tune the energy band
and induce a topological phase transition in MnBi2Te4 monolayer, we propose a
2D Janus structure MnBi2Se2Te2 monolayer based on MnBi2Te4 monolayer. Janus
crystals represent a class of 2D materials with different atomic species on
their upper and lower facets. Janus MnBi2Se2Te2 monolayer can be obtained by
substituting the upper triple Te-Bi-Te layers of MnBi2Te4 monolayer with a
triple Se-Bi-Se layers. The stability of MnBi2S2Te2 monolayer was checked by
its phonon spectra, molecular dynamic simulation and formation energy Sup .
Because of different electronegativity of Se and Te, MnBi2Se2Te2 monolayer
possesses the spontaneous electric polarization of about 0.44 eÅ. MnBi2Se2Te2
monolayer exhibits a ferromagnetic ground state with the in-plane
magnetization, and its Curie temperature is estimated to be 14.3 K. Due to the
small magnetic anisotropy, the magnetization direction can be tuned form in-
plane to out-of-plane by a small magnetic field or strain. The band structure
of MnBi2Se2Te2 monolayer shows a full band gap of about 44 meV as shown in
Fig. 5(a). The calculation on anomalous Hall conductivity shows a plateau at
the Fermi level, which corresponds to a Chern number $C=1$, indicating QAHE
state as shown in Fig. 5(b). As discussed above for MnBi2Te4 monolayer, when
the system turns into the topological phase, the energy gap increases first
and then decreases, and the Curie temperature keeps increasing with the
increase of electric field. This is verified again in MnBi2Se2Te2 monolayer,
where the electric field enhances Curie temperature and changes the band gap
as shown in Fig. 5(c).

For Janus material MnBi2S2Te2 monolayer, its spontaneous electric polarization
is about 0.73 eÅ, which is larger than that for MnBi2Se2Te2 monolayer, thus a
larger band gap and higher Curie temperature are expected in MnBi2S2Te2
monolayer according to the above discussion. MnBi2S2Te2 monolayer holds
ferromagnetic ground state with out-of-plane magnetization, and its Curie
temperature is estimated to be 30 K. MnBi2S2Te2 monolayer has a global band
gap of about 80 meV as shown in Fig. 5(d). The topologically nontrivial band
structure of MnBi2S2Te2 monolayer is characterized by a nonzero Chern number
$C=2$ with a quantized charge Hall plateau of 2$e^{2}/h$ and two gapless
chiral edge states connecting the valence and conduction bands as shown in
Figs. 5(e) and (f), respectively.

To check the influence of the Hubbard $U$ on the QAHE, we calculate the
anomalous Hall conductivity with $U$ = 3, 4 and 5 for monolayers MnBi2Se2Te2
and MnBi2S2Te2, respectively, as shown in Fig. S4. The results show that by
varying the Hubbard $U$ from 3 to 5 eV, the QAHE states in both MnBi2Se2Te2
and MnBi2S2Te2 remain, but the band gap is slightly changed.

In monolayers one would expect a gap to open at an energy-scale set by the
overlap of the edge mode wavefunctions on the top and bottom surfaces. The
gaps opened by the mixture of the top and bottom surfaces for Janus
MnBi2Se2Te2 and MnBi2S2Te2 are 118 and 121 meV, respectively, and the
corresponding magnetic exchange energies of the above Janus materials are 140
and 161 meV. In both cases, the gaps are smaller than the magnetic exchange
energy, supporting the QAHE states.

According to the calculated results of the phonon spectra, molecular dynamics
simulation and the formation energy for Janus MnBi2Se2Te2 and MnBi2S2Te2, we
found that they are both energetically and dynamically stable, and are
feasible in experiments because of their exothermic reactions and much lower
formation energy than that of MnBi2Te4 Sup . Thus, one may expect to grow the
bulk materials first and then exfoliate them. Alternatively, Janus MnBi2Se2Te2
can be grown in the quintuple layers of Bi2Te3 and Bi2Se3 and a bilayer of
MnTe with the molecular beam epitaxy method.

##  VI Summary

In this work, we systematically investigate the properties of monolayer
MnBi2Te4 under electric field. It is found that the electric field can induce
a topological phase transition from a topologically trivial state to a
nontrivial state. It is also observed that the MAE and Tc of MnBi2Te4
monolayer are dramatically enhanced with the increase of electric field. The
increased MAE mainly comes from the enhanced SOC due to the electric field. In
terms of the super-exchange picture, the enhanced Tc can be understood from
the enhanced $p$-$d$ hybridization and decreased energy difference between $p$
orbitals of Te atoms and $d$ orbitals of Mn atoms. In addition, we propose
novel Janus monolayers MnBi2Se2Te2 and MnBi2S2Te2 with different spontaneous
electric polarizations, which can realize the QAHE with Chern numbers $C$=1
and $C$=2, respectively. Our results will spur more studies on novel
properties of MnBi2Te4 monolayer under an electric field, and also provide new
candidates to realize QAHE in ferromagnetic semiconductors with electric
polarization that would be particularly interesting in electrically controlled
spintronic devices.

## Acknowledgement

Jing-Yang You and Xue-Juan Dong contributed equally to this work.

This work is supported in part by the National Key R&D Program of China (Grant
No. 2018YFA0305800), the Strategic Priority Research Program of the Chinese
Academy of Sciences (Grant No. XDB28000000), the National Natural Science
Foundation of China (Grant No.11834014), and Beijing Municipal Science and
Technology Commission (Grant No. Z191100007219013). B.G. is also supported by
the National Natural Science Foundation of China (Grants No. Y81Z01A1A9 and
No. 12074378), the Chinese Academy of Sciences (Grants No. Y929013EA2 and No.
E0EG4301X2), the University of Chinese Academy of Sciences (Grant No.
110200M208), the Strategic Priority Research Program of Chinese Academy of
Sciences (Grant No. XDB33000000), and the Beijing Natural Science Foundation
(Grant No. Z190011).

## References

  * Haldane (1988) F. D. M. Haldane, Phys. Rev. Lett. 61, 2015 (1988).
  * Onoda and Nagaosa (2003) M. Onoda and N. Nagaosa, Phys. Rev. Lett. 90, 206601 (2003).
  * Liu  _et al._ (2008) C.-X. Liu, X.-L. Qi, X. Dai, Z. Fang, and S.-C. Zhang, Phys. Rev. Lett. 101, 146802 (2008).
  * Wu (2008) C. Wu, Phys. Rev. Lett. 101, 186807 (2008).
  * Yu  _et al._ (2010) R. Yu, W. Zhang, H.-J. Zhang, S.-C. Zhang, X. Dai, and Z. Fang, Science 329, 61 (2010).
  * Chang  _et al._ (2013) C.-Z. Chang, J. Zhang, X. Feng, J. Shen, Z. Zhang, M. Guo, K. Li, Y. Ou, P. Wei, L.-L. Wang, Z.-Q. Ji, Y. Feng, S. Ji, X. Chen, J. Jia, X. Dai, Z. Fang, S.-C. Zhang, K. He, Y. Wang, L. Lu, X.-C. Ma, and Q.-K. Xue, Science 340, 167 (2013).
  * Wu  _et al._ (2014) J. Wu, J. Liu, and X.-J. Liu, Phys. Rev. Lett. 113, 136403 (2014).
  * Chang  _et al._ (2015) C.-Z. Chang, W. Zhao, D. Y. Kim, H. Zhang, B. A. Assaf, D. Heiman, S.-C. Zhang, C. Liu, M. H. W. Chan, and J. S. Moodera, Nat. Mater. 14, 473 (2015).
  * Mogi  _et al._ (2015) M. Mogi, R. Yoshimi, A. Tsukazaki, K. Yasuda, Y. Kozuka, K. S. Takahashi, M. Kawasaki, and Y. Tokura, Appl. Phys. Lett. 107, 182401 (2015).
  * Liu  _et al._ (2016) C.-X. Liu, S.-C. Zhang, and X.-L. Qi, Annu. Rev. Condens. Matter Phys. 7, 301 (2016).
  * Si  _et al._ (2017) L. Si, O. Janson, G. Li, Z. Zhong, Z. Liao, G. Koster, and K. Held, Phys. Rev. Lett. 119, 026402 (2017).
  * You  _et al._ (2019a) J.-Y. You, C. Chen, Z. Zhang, X.-L. Sheng, S. A. Yang, and G. Su, Phys. Rev. B 100, 064408 (2019a).
  * Ou  _et al._ (2017) Y. Ou, C. Liu, G. Jiang, Y. Feng, D. Zhao, W. Wu, X.-X. Wang, W. Li, C. Song, L.-L. Wang, W. Wang, W. Wu, Y. Wang, K. He, X.-C. Ma, and Q.-K. Xue, Adv. Mater. 30, 1703062 (2017).
  * He  _et al._ (2018) K. He, Y. Wang, and Q.-K. Xue, Annu. Rev. Condens. Matter Phys. 9, 329 (2018).
  * You  _et al._ (2019b) J.-Y. You, Z. Zhang, B. Gu, and G. Su, Phys. Rev. Appl 12, 024063 (2019b).
  * Li  _et al._ (2020a) Y. Li, J. Li, Y. Li, M. Ye, F. Zheng, Z. Zhang, J. Fu, W. Duan, and Y. Xu, Phys. Rev. Lett. 125, 086401 (2020a).
  * Otrokov  _et al._ (2017) M. M. Otrokov, T. V. Menshchikova, M. G. Vergniory, I. P. Rusinov, A. Y. Vyazovskaya, Y. M. Koroteev, G. Bihlmayer, A. Ernst, P. M. Echenique, A. Arnau, and E. V. Chulkov, 2D Mater. 4, 025082 (2017).
  * Otrokov  _et al._ (2019a) M. M. Otrokov, I. I. Klimovskikh, H. Bentmann, D. Estyunin, A. Zeugner, Z. S. Aliev, S. Gaß, A. U. B. Wolter, A. V. Koroleva, A. M. Shikin, M. Blanco-Rey, M. Hoffmann, I. P. Rusinov, A. Y. Vyazovskaya, S. V. Eremeev, Y. M. Koroteev, V. M. Kuznetsov, F. Freyse, J. Sánchez-Barriga, I. R. Amiraslanov, M. B. Babanly, N. T. Mamedov, N. A. Abdullayev, V. N. Zverev, A. Alfonsov, V. Kataev, B. Büchner, E. F. Schwier, S. Kumar, A. Kimura, L. Petaccia, G. D. Santo, R. C. Vidal, S. Schatz, K. Kißner, M. Ünzelmann, C. H. Min, S. Moser, T. R. F. Peixoto, F. Reinert, A. Ernst, P. M. Echenique, A. Isaeva, and E. V. Chulkov, Nature 576, 416 (2019a).
  * Lee  _et al._ (2013) D. S. Lee, T.-H. Kim, C.-H. Park, C.-Y. Chung, Y. S. Lim, W.-S. Seo, and H.-H. Park, CrystEngComm 15, 5532 (2013).
  * Cui  _et al._ (2019) J. Cui, M. Shi, H. Wang, F. Yu, T. Wu, X. Luo, J. Ying, and X. Chen, Phys. Rev. B 99, 155125 (2019).
  * Li  _et al._ (2020b) H. Li, S. Liu, C. Liu, J. Zhang, Y. Xu, R. Yu, Y. Wu, Y. Zhang, and S. Fan, Phys. Chem. Chem. Phys. 22, 556 (2020b).
  * Zhang  _et al._ (2019) D. Zhang, M. Shi, T. Zhu, D. Xing, H. Zhang, and J. Wang, Phys. Rev. Lett. 122, 206401 (2019).
  * Chen  _et al._ (2019) Y.J. Chen, L.X. Xu, J.H. Li, Y.W. Li, H.Y. Wang, C.F. Zhang, H. Li, Y. Wu, A.J. Liang, C. Chen, S.W. Jung, C. Cacho, Y.H. Mao, S. Liu, M.X. Wang, Y.F. Guo, Y. Xu, Z.K. Liu, L.X. Yang, and Y.L. Chen, Phys. Rev. X 9, 041040 (2019).
  * Vidal  _et al._ (2019) R. C. Vidal, A. Zeugner, J. I. Facio, R. Ray, M. H. Haghighi, A. U.B Wolter, L. T. CorredorBohorquez, F. Caglieris, S. Moser, T. Figgemeier, T. R.F. Peixoto, H. B. Vasili, M. Valvidares, S. Jung, C. Cacho, A. Alfonsov, K. Mehlawat, V. Kataev, C. Hess, M. Richter, B. Büchner, J. van den Brink, M. Ruck, F. Reinert, H. Bentmann, and A. Isaeva, Phys. Rev. X 9, 041065 (2019).
  * Aliev  _et al._ (2019) Z. S. Aliev, I. R. Amiraslanov, D. I. Nasonova, A. V. Shevelkov, N. A. Abdullayev, Z. A. Jahangirli, E. N. Orujlu, M. M. Otrokov, N. T. Mamedov, M. B. Babanly, and E. V. Chulkov, J. Alloys Compd. 789, 443 (2019).
  * Deng  _et al._ (2020a) H. Deng, Z. Chen, A. Wołoś, M. Konczykowski, K. Sobczak, J. Sitnicka, I. V. Fedorchenko, J. Borysiuk, T. Heider, Ł. Pluciński, K. Park, A. B. Georgescu, J. Cano, and L. Krusin-Elbaum, Nat. Phys. 17, 36-42 (2021a).
  * Lei  _et al._ (2020) C. Lei, S. Chen, and A. H. MacDonald, Proceedings of the National Academy of Sciences 117, 27224 (2020).
  * Rienks  _et al._ (2019) E. D. L. Rienks, S. Wimmer, J. Sánchez-Barriga, O. Caha, P. S. Mandal, J. Růžička, A. Ney, H. Steiner, V. V. Volobuev, H. Groiss, M. Albu, G. Kothleitner, J. Michalička, S. A. Khan, J. Minár, H. Ebert, G. Bauer, F. Freyse, A. Varykhalov, O. Rader, and G. Springholz, Nature 576, 423 (2019).
  * Hu  _et al._ (2020) C. Hu, L. Ding, K. N. Gordon, B. Ghosh, H.-J. Tien, H. Li, A. G. Linn, S.-W. Lien, C.-Y. Huang, S. Mackey, J. Liu, P. V. S. Reddy, B. Singh, A. Agarwal, A. Bansil, M. Song, D. Li, S.-Y. Xu, H. Lin, H. Cao, T.-R. Chang, D. Dessau, and N. Ni, Sci. Adv. 6, eaba4275 (2020).
  * Klimovskikh  _et al._ (2020) I. I. Klimovskikh, M. M. Otrokov, D. Estyunin, S. V. Eremeev, S. O. Filnov, A. Koroleva, E. Shevchenko, V. Voroshnin, A. G. Rybkin, I. P. Rusinov, M. Blanco-Rey, M. Hoffmann, Z. S. Aliev, M. B. Babanly, I. R. Amiraslanov, N. A. Abdullayev, V. N. Zverev, A. Kimura, O. E. Tereshchenko, K. A. Kokh, L. Petaccia, G. D. Santo, A. Ernst, P. M. Echenique, N. T. Mamedov, A. M. Shikin, and E. V. Chulkov, npj Quantum Materials 5, 54 (2020).
  * Li  _et al._ (2019a) J. Li, Y. Li, S. Du, Z. Wang, B.-L. Gu, S.-C. Zhang, K. He, W. Duan, and Y. Xu, Sci. Adv. 5, eaaw5685 (2019a).
  * Li  _et al._ (2019b) Y. Li, Z. Jiang, J. Li, S. Xu, and W. Duan, Phys. Rev. B 100, 134438 (2019b).
  * Otrokov  _et al._ (2019b) M.M. Otrokov, I.P. Rusinov, M. Blanco-Rey, M. Hoffmann, A.Y. Vyazovskaya, S.V. Eremeev, A. Ernst, P.M. Echenique, A. Arnau, and E.V. Chulkov, Phys. Rev. Lett. 122, 107202 (2019b).
  * Deng  _et al._ (2020b) Y. Deng, Y. Yu, M. Z. Shi, Z. Guo, Z. Xu, J. Wang, X. H. Chen, and Y. Zhang, Science 367, 895 (2020b).
  * Ge  _et al._ (2020) J. Ge, Y. Liu, J. Li, H. Li, T. Luo, Y. Wu, Y. Xu, and J. Wang, Natl. Sci. Rev. 7, 1280 (2020).
  * Liu  _et al._ (2020) C. Liu, Y. Wang, H. Li, Y. Wu, Y. Li, J. Li, K. He, Y. Xu, J. Zhang, and Y. Wang, Nat. Mater. 19, 522 (2020).
  * Weisheit  _et al._ (2007) M. Weisheit, S. Fahler, A. Marty, Y. Souche, C. Poinsignon, and D. Givord, Science 315, 349 (2007).
  * Deng  _et al._ (2018) Y. Deng, Y. Yu, Y. Song, J. Zhang, N. Z. Wang, Z. Sun, Y. Yi, Y. Z. Wu, S. Wu, J. Zhu, J. Wang, X. H. Chen, and Y. Zhang, Nature 563, 94 (2018).
  * Jiang  _et al._ (2018) S. Jiang, L. Li, Z. Wang, K. F. Mak, and J. Shan, Nat. Nanotechnol. 13, 549 (2018).
  * Du  _et al._ (2020) S. Du, P. Tang, J. Li, Z. Lin, Y. Xu, W. Duan, and A. Rubio, Phys. Rev. Research 2, 022025(R) (2020).
  * Ni  _et al._ (2008) Z. H. Ni, T. Yu, Y. H. Lu, Y. Y. Wang, Y. P. Feng, and Z. X. Shen, ACS Nano 2, 2301 (2008).
  * Liu  _et al._ (2013) X. C. Liu, H. W. Zhang, and K. Lu, Science 342, 337 (2013).
  * Dong  _et al._ (2019) X.-J. Dong, J.-Y. You, B. Gu, and G. Su, Phys. Rev. Appl 12, 014020 (2019).
  * Sim  _et al._ (2015) D. M. Sim, M. Kim, S. Yim, M.-J. Choi, J. Choi, S. Yoo, and Y. S. Jung, ACS Nano 9, 12115 (2015).
  * You  _et al._ (2019c) J.-Y. You, B. Gu, and G. Su, Sci. Rep. 9, 20116 (2019c).
  * Ahmed  _et al._ (2015) T. Ahmed, N. A. Modine, and J.-X. Zhu, Appl. Phys. Lett. 107, 043903 (2015).
  * You  _et al._ (2020) J.-Y. You, B. Gu, and G. Su, Phys. Rev. B 101, 184521 (2020).
  * Chen  _et al._ (2017) Z. Chen, B. Ge, W. Li, S. Lin, J. Shen, Y. Chang, R. Hanus, G. J. Snyder, and Y. Pei, Nat. Commun. 8, 13828 (2017).
  * Liu  _et al._ (2019) Y. Liu, C. Ma, Q. Zhang, W. Wang, P. Pan, L. Gu, D. Xu, J. Bao, and Z. Dai, Adv. Mater. 31, 1900062 (2019).
  * Hou  _et al._ (2020) F. Hou, Q. Yao, C.-S. Zhou, X.-M. Ma, M. Han, Y.-J. Hao, X. Wu, Y. Zhang, H. Sun, C. Liu, Y. Zhao, Q. Liu, and J. Lin, ACS Nano 14, 11262–11272 (2020).
  * Nemani  _et al._ (2018) S. K. Nemani, R. K. Annavarapu, B. Mohammadian, A. Raiyan, J. Heil, M. A. Haque, A. Abdelaal, and H. Sojoudi, Adv. Mater. Interfaces 5, 1801247 (2018).
  * Ohta  _et al._ (2006) T. Ohta, A. Bostwick, T. Seyller, K. Horn, and E. Rotenberg, Science 313, 951 (2006).
  * Min  _et al._ (2007) H. Min, B. Sahu, S. K. Banerjee, and A. H. MacDonald, Phys. Rev. B 75, 155115 (2007).
  * Zhang  _et al._ (2009) Y. Zhang, T.-T. Tang, C. Girit, Z. Hao, M. C. Martin, A. Zettl, M. F. Crommie, Y. R. Shen, and F. Wang, Nature 459, 820 (2009).
  * Mak  _et al._ (2009) K. F. Mak, C. H. Lui, J. Shan, and T. F. Heinz, Phys. Rev. Lett. 102, 256405 (2009).
  * Lui  _et al._ (2011) C. H. Lui, Z. Li, K. F. Mak, E. Cappelluti, and T. F. Heinz, Nat. Phys. 7, 944 (2011).
  * Lu  _et al._ (2014) C.-P. Lu, G. Li, J. Mao, L.-M. Wang, and E. Y. Andrei, Nano Lett. 14, 4628 (2014).
  * Kresse and Furthmüller (1996) G. Kresse and J. Furthmüller, Phys. Rev. B 54, 11169 (1996).
  * Blöchl (1994) P. E. Blöchl, Phys. Rev. B 50, 17953 (1994).
  * Perdew  _et al._ (1996) J. P. Perdew, K. Burke, and M. Ernzerhof, Phys. Rev. Lett. 77, 3865 (1996).
  * Monkhorst and Pack (1976) H. J. Monkhorst and J. D. Pack, Phys. Rev. B 13, 5188 (1976).
  * Togo and Tanaka (2015) A. Togo and I. Tanaka, Scr. Mater. 108, 1 (2015).
  * Marzari and Vanderbilt (1997) N. Marzari and D. Vanderbilt, Phys. Rev. B 56, 12847 (1997).
  * Souza  _et al._ (2001) I. Souza, N. Marzari, and D. Vanderbilt, Phys. Rev. B 65, 035109 (2001).
  * Wu  _et al._ (2018) Q. Wu, S. Zhang, H.-F. Song, M. Troyer, and A. A. Soluyanov, Comput. Phys. Commun. 224, 405 (2018).
  * Sancho  _et al._ (1985) M. P. L. Sancho, J. M. L. Sancho, J. M. L. Sancho, and J. Rubio, J. Phys. F: Met. Phys. 15, 851 (1985).
  * Gong  _et al._ (2019) Y. Gong, J. Guo, J. Li, K. Zhu, M. Liao, X. Liu, Q. Zhang, L. Gu, L. Tang, X. Feng, D. Zhang, W. Li, C. Song, L. Wang, P. Yu, X. Chen, Y. Wang, H. Yao, W. Duan, Y. Xu, S.-C. Zhang, X. Ma, Q.-K. Xue, and K. He, Chin. Phys. Lett. 36, 076801 (2019).
  * (68) See Supplemental Material at [url] for DFT results on estimated Curie temperature and stability of MnBi2Te4, MnBi2Se2Te2 and MnBi2S2Te2.
  * Goodenough (1955) J. B. Goodenough, Phys. Rev. 100, 564 (1955).
  * Anderson (1959) P. W. Anderson, Phys. Rev. 115, 2 (1959).
  * Kanamori (1960) J. Kanamori, J. Appl. Phys. 31, S14 (1960).