\section{Methods}
The calculations were based on density functional theory (DFT)
implemented in the {\sc Quantum ESPRESSO} package~\cite{QE-2009}.  The
generalized gradient approximation (GGA) of Perdew-Burke-Ernzerhof
(PBE) was used for the exchange and correlation functional, and
Troullier-Martins type pseudopotentials~\cite{troullierPRB1991}.  The
Kohn-Sham orbitals were expanded in a plane-wave basis with a cutoff
energy of 70 Ry, and for the charge density a cutoff of 280 Ry was
used.  A $k$-point grid sampling grid was generated using the
Monkhorst-Pack scheme with 10$\times$10$\times$1
points~\cite{monkhorstPRB1976}, and a finer regular grid of
80$\times$80$\times$1 was used for transition probability
calculations.  The equilibrium structures were found by using a
conjugate-gradient optimization algorithm, and the energy landscape is
mapped by relaxing the structure under constraints for each of the
in-plane lattice parameters, while all the other structural parameters
are allowed to relax.

We used the modern theory of
polarization~\cite{vanderbilt-PRB-47-1651-1993} to calculate the
spontaneous polarization given by
\begin{equation}
\vec{\mathcal{P}}=\frac{1}{\Omega}\sum_{\tau}q^{\rm{ion}}_{\tau}{\bf R}_{\tau}-\frac{2i\rm{e}}{(2\pi)^3}\sum_{n}^{\rm{occ}}\int_{BZ}d^3{\bf k}e^{-i\vec{k}\cdot{\bf R}}\Big\langle u_{n{\bf k}}\Big|\frac{\partial u_{n{\bf k}}}{\partial {\bf k}}\Big\rangle,
\label{eq:pol}
\end{equation}
where $q_\tau$ is the ionic charge plus the core electrons,
${\bf R}_{\tau}$ is the position of ions, $\Omega$ is the unit cell
volume, $\rm{e}$ is the elementary charge, $n$ is the valence band
index, ${\bf k}$ is the wave vector, and $u_{n{\bf k}}$ is the
electronic wave function. The first term is the contribution from ions
and core electrons, and the second term is the electronic contribution
defined as adiabatic flow of current which can be calculated from the
Berry connection~\cite{vanderbilt-PRB-47-1651-1993}.The response of
the material to a homogenous static external electric field is
calculated based on methods developed by
Refs.~\cite{souza-PRL-89-117602, umari-PRL-89-157602} implemented in
the {\sc Quantum ESPRESSO} package~\cite{QE-2009}.

\begin{figure}
\includegraphics[width=8cm]{cocoord.pdf}
\caption{Schematic configuration-coordinate diagram for
$Cmcm$-ML and $Pnma$-ML phases, in SnS and GeSe.}
\label{fig:cc}
\end{figure}
\section{Results}
\subsection{Multistability of SnS and GeSe in the monolayer phase}
We start by exploring the energy landscape of monolayer SnS and
GeSe. We consider the monolayer form of the two structures that are
known for bulk SnS ie., a centrosymmetric structure ($Cmcm$), and the
$Pnma$ structure resembling black phosphorus, and which is the only
known layered structure of bulk GeSe.  We will designate the respective
monolayer phases by appending `ML' to the respective bulk space group.

The atomic positions in the $Pnma$-ML phase are
$\pm$(M:0.25$\pm\delta$, 0.25, 0.05; X:0.25, 0.25, -0.05) in fractional
coordinates, where M=(Sn, Ge) and X=(S, Se), $\delta=0.06$ and 0.08
for SnS and GeSe, respectively. The $Cmcm$-ML phase is obtained by
taking $\delta=0$.  As a result, the $Cmcm$-ML has two perpendicular
mirror symmetry planes, as well as inversion symmetry, while $Pnma$-ML
has no inversion symmetry. In our DFT simulations we used
$\delta=0.01$ as a tolerance to distinguish the $Pnma$-ML phase from
the $Cmcm$-ML phase ~\footnote{We define puckering orientation as a
  unit vector of the in plane bond formed by the nearest neighbor of
  MX atoms in the direction of the broken mirror symmetry. For the SnS
  structure shown in Fig.~\ref{fig:stress-strain}(d), the puckering
  direction $\hat{d}_{\rm puck}=\hat{x}$ as we define
  $\hat{d}_{\rm puck}=\frac{\vec{x_{\rm S}}-\vec{x_{\rm
        Sn}}}{|\vec{x_{\rm S}}-\vec{x_{\rm Sn}}|}$.}.

The $Pnma$-ML and the $Cmcm$-ML phases can both be seen as distortions
of a rocksalt bilayer that can be transformed into each other by a
displacement of some of the atoms along $\hat{x}$ (see
Fig.\ref{fig:stress-strain} for $\hat{x}$ and $\hat{y}$ directions).
The $Cmcm$-ML and $Pnma$-ML phases of SnS and GeSe monolayer have also
been reported in Ref.~\cite{mehboudi-NL-5b04613-2016}.  By symmetry,
there are four distinct $Pnma$-ML configurations (equivalent by
$\pi/2$ rotations of the puckering direction).  For SnS, $Cmcm$-ML is
a local minima of the energy surface.  For GeSe, the $Cmcm$-ML
structure is not an energy minimum but a saddle point.  The activation
energy for reorientation of the $Pnma$-ML puckering direction is very
small (88 meV for SnS and 43 meV for GeSe).  We note that GGA has been
successful in predicting the small enthalpy differences (tens of meV)
between different phases of ferroelectric materials, because
systematic errors cancel out when comparing systems with very similar
structures~\cite{sanna-PRB-83-054112-2011}. The broken inversion
symmetry and total energy with a typical double-well potential of SnS
and GeSe are the first two indications that these materials may
possess ferroelectricity.

\begin{figure}
  \centering
  \includegraphics[width=8.6cm]{stress-strain.pdf}
  \caption{Stress-strain curves of monolayer (a) SnS and (b) GeSe
    for tensile strain along the $\hat{x}$ (black circle) and $\hat{y}$ (red square) directions.
    (I) indicates the $Pnma$-ML structure reconfiguration such that
    the puckering (armchair) direction $\hat{d}_{\rm puck}$ becomes
    $\hat{y}$ instead of $\hat{x}$.  (II) indicates the transformation
    into an hexagonal phase. In the insets of (a) and (b), the strain
    in the $\hat{y}$ direction was shifted to highlight the rotation
    of the $Pnma$-ML structure by $\pi/2$, swapping the armchair and
    zigzag directions. (c) and (d) top and side view of SnS structure
    with $\hat{d}_{\rm puck}=\hat{x}$. The larger grey atom is Sn and
    the smaller yellow atom is S. (e) The respective Brillouin zone
    and the high symmetry points. }
  \label{fig:stress-strain}
\end{figure}

\subsection{Application of uniaxial stress}
The phase transition of SnS to $Cmcm$-ML, or equivalently the
reorientation of the $Pnma$-ML structure, can be induced by in-plane
uniaxial tensile stress (Fig.~\ref{fig:stress-strain}).  We use an effective
thickness to estimate the values of stress, as outlined in
Ref.~\cite{gomes-PRB-92-214103-2015}.

For uniaxial stress along $\hat{y}$, the SnS structure begins to
resemble $Cmcm$-ML as the shorter lattice parameter $b$ is stretched.
For $\epsilon_{y}>0.08$, uniaxial stress results in the rotation of
the $Pnma$-ML structure by $\pi/2$. The puckering
$\hat{d}_{\rm puck}$thus rotates from $\hat{x}$ to $\hat{y}$
[Fig.~\ref{fig:stress-strain}(a), transition I]. Similar qualitative
behavior is observed in GeSe (see
Fig.~\ref{fig:stress-strain}(b)). Both SnS and GeSe transit to $Cmcm$
phase, but they spontaneously revert back to $Pnma$ once the tensile
stress is removed~\footnote{ We found that once the stretch is
  removed the $Cmcm$ structure spontaneously reverts back to $Pnma$
  for both SnS and GeSe. However, we found that during {\it
    compression}, the $Cmcm$ phase of SnS is stable.}.

The application of uniaxial stress along $\hat{x}$ reveals another
phase transition at $\epsilon_{x}=0.72$ and 0.78 for SnS and GeSe,
respectively.  The structure is a hexagonal phase resembling blue
phosphorene (see Ref.~\cite{mehboudiPNAS2015}).  The hexagonal
structure and its band structure are plotted in Fig.~\ref{fig:band1}.

\begin{figure}
  \centering
  \includegraphics[width=8cm]{EField.pdf}
  \caption{Structural visualization of clamped SnS monolayer under
    uniform electric field at points of transition. Puckering and
    electric dipole orientation (red arrow) can switch from positive
    $\hat{x}$ (b) to either negative $\hat{x}$ (a) or positive
    $\hat{y}$ (c) depending on the directions of applied electric
    field.  }
  \label{fig:efield}
\end{figure}

\subsection{Application of electric field}

\begin{figure*}
  \centering
  \includegraphics[width=17.2cm]{bands-12.pdf}
  \caption{
    Representative band structures of SnS monolayers (a)
    unstrained, (b) to (d) under tensile uniaxial stress along the $\hat{x}$
    for axial strains of $\epsilon_{x}=0.22$ to $\epsilon_{x}=0.75$,
    and (e) to (g) under tensile uniaxial stress along $\hat{y}$ for axial
    strains of $\epsilon_{y}=0.02$ to $\epsilon_{y}=0.27$. The dotted
    lines locate the valence band maxima. The corresponding side and
    top view of structural visualizations are below the band structure
    plots.  It is apparent that the band structure (b)
    $\epsilon_x=0.22$ (or an uniaxial stress of
    $\sigma_{xx}\sim1.4$GPa) is equivalent to the band structure (g)
    $\epsilon_y=0.27$ (or an uniaxial stress of
    $\sigma_{yy}\sim1.4$GPa) if the $\hat{x}$ and $\hat{y}$ are
    inverted (rotation around $\Gamma$ axis on figures).}
  \label{fig:band1}
\end{figure*}

Application of an electric field is an alternative way to trigger the
transition between different minima on the energy surface of SnS or
GeSe.  Since the $Pnma$-ML structure is piezoelectric, the application
of an electric field along the polar ($\hat{x}$) direction in a
mechanically free sample induces strain as
well~\cite{gomes-PRB-92-214103-2015}.  However, here we will consider,
for simplicity, the application of an electric field to a mechanically
clamped sample.

The spontaneous polarization in the $Pnma$-ML phase, which was
measured with respect to the centrosymmetric structure by taking as
the effective volume the equivalent volume occupied by a layer of the
bulk unit cell, is 0.6 and 1.7 C/m$^2$ for SnS and GeSe, respectively,
which is comparable to that of 3D
ferroelectrics~\cite{zhong-PRL-72-3618-1994}.

In this case, application of an electric field with polarity opposed
to the bond dipole results in bonds breaking and creates new bonds
with inversion of the polarization along $\hat{x}$, rather than in a
rotation of the structure. As shown in Fig.~\ref{fig:efield} (a) the
ionic configuration changes (i.e., $\hat{d}_{\rm puck}$ switches from
$\hat{x}$ to $-\hat{x}$), and it is apparent from Eq.~\ref{eq:pol}
that the electric dipole orientation can be switched, which we have
found to be the case based on our DFT calculations.

The coercive field for this puckering transformation is
0.18$\times10^{7}$~V/cm for SnS and 0.51$\times10^{7}$~V/cm for
GeSe. Moreover, we found that applying an electric field in $\hat{y}$
at 0.29$\times10^{7}$~V/cm (0.80$\times10^{7}$~V/cm) could also
convert the $\hat{d}_{\rm puck}$ from $\hat{x}$ to $\hat{y}$ for SnS
(GeSe).  The coercive field calculated by this method corresponds to
the electric field at which the unfavorable phase becomes unstable and
can be seen as an upper bound for the coercive field of a real
multi-domain material.  This is usually smaller provided that the
domain walls are mobile at that temperature and, according to a recent
work~\cite{qian2016}, the domain wall energy is small for this class
of materials.  Thus, the electrical fields necessary for ferroelectric
switching are clearly achievable in current 2D
experiments~\cite{radisavljevic-NatNanotechnology-6-147-2011}.  The
structures of SnS monolayer under electric fields at which the
puckering orientation switches are plotted in Fig.~\ref{fig:efield}.

Since the two materials possess a spontaneous, reversible polarization
and bistability, they classify as ferroelectrics.  The
configuration-coordinate diagram of GeSe is typical of a ferroelectric
with second-order phase transition at $T=0$ (consistent with the
change in symmetry). The energy curve for SnS has a minimum rather
than a saddle point at $Cmcm$-ML, and therefore resembles a
ferroelectric with first order phase transition, with the peculiarity
that the $Cmcm$-ML structure is stable for all $T>0$.  Recently, based
on Car-Parrinello molecular dynamics simulations, Mehboudi et al.
showed that monolayer monochalcogenides undergo an order-disorder
phase transition~\cite{mehboudi-NL-5b04613-2016}. Hence, since SnS and
GeSe have four degenerate $Pnma$-ML phases, we expect that the average
total polarization goes to zero as temperature approaches $T_{\rm m}$.

\subsection{Band structure}
\begin{figure}
  \centering
  \includegraphics[width=8.6cm]{bands-34.pdf}
  \caption{Evolution of GeSe band structure with strains in armchair
    (a) to (d) and zigzag direction (e) to (h). The dotted lines
    locate the valence band maxima. The structure inversion is found
    at $\epsilon_{y}=0.15$. It is apparent that the band structure (b)
    $\epsilon_x=0.22$ (or an uniaxial stress of
    $\sigma_{xx}\sim1.4$GPa) is equivalent to the band structure (h)
    $\epsilon_y=0.30$ (or an uniaxial stress of
    $\sigma_{yy}\sim1.4$GPa) if the $\hat{x}$ and $\hat{y}$ are
    inverted (rotation around $\Gamma$ axis on figures).}
  \label{fig:band2}
\end{figure}
The phase transitions are accompanied by changes of the band structure
and can, therefore, be detected optically.  Representative SnS and
GeSe band structures under uniaxial stress are shown in
Fig.~\ref{fig:band1} and Fig.~\ref{fig:band2}, respectively.  We note
that even though the band gap is underestimated due to our usage of
DFT as the calculation method~\cite{gomesPRB2015}, the dispersion of
the bands is accurately reproduced. Unstrained SnS is an indirect-gap
semiconductor with its valence band maximum located near the X-point
(along the $\Gamma$-X line) and the conduction band minimum near the
Y-point (along the $\Gamma$-Y line).  There are, therefore, two
two-fold degenerate valleys, designated $V_x$ and $V_y$, respectively.
At large strains along $\hat{x}$, SnS transforms to a hexagonal phase
at $\epsilon_x=0.72$ resembling blue phosphorene (Fig.~\ref{fig:band1}
(c))~\cite{mehboudiPNAS2015} and becomes a direct gap at
$\epsilon_x=0.75$. For uniaxial stress along $\hat{y}$ there is a
transition from indirect gap to direct gap at $\epsilon_y=0.02$ (see
Fig.~\ref{fig:band1}(e)), after which the system again becomes
indirect gap.

The band structure of GeSe under uniaxial stress is shown in
Fig.~\ref{fig:band2} (a) to (d) for the $\hat{x}$ and (e) to (h) for
the $\hat{y}$.  Even though unstrained GeSe is a direct-gap
semiconductor, there are also two nearly degenerate conduction band
minima at the $V_x$ and $V_y$ points.  The swapping between the
$\hat{x}$ and $\hat{y}$ of the $Pnma$-ML structure under tensile
stress along the $\hat{y}$ direction occurs at $\epsilon_y=0.15$ and
is in this case accompanied by a loss of the direct bandgap, which
becomes indirect as the structure reverts back into $Pnma$-ML. As
shown in Fig.~\ref{fig:band2}, the band structure (b)
$\epsilon_x=0.22$ is equivalent to the band structure (h)
$\epsilon_y=0.30$ if the $\hat{x}$ and $\hat{y}$ are inverted
(rotation around $\Gamma$ axis on figures). The transition to a
hexagonal phase under tensile stress along $\hat{x}$
($\epsilon_x=0.78$) is also accompanied by an indirect- to direct-gap
semiconductor transition.

In addition, we calculated the projected density of states for SnS and
GeSe for various strains (Fig.~\ref{fig:PDOS-all}).  The trends of the
evolution of PDOS of GeSe and SnS with increasing strain are similar.
Specifically, the relative contributions of the $p$-orbitals for Sn
and Ge atoms at energies close to the maximum valence band increases
with increasing strain.

\begin{figure*}
  \centering
  \includegraphics[width=17cm]{PDOS-all.pdf}
  \caption{Projected density of states (PDOS) of SnS (a) to (e) and GeSe (f) to (j) for different
    strains. The top panels are PDOS of Sn (Ge) atom and the bottom panels
    are PDOS of S (Se) atom.}
  \label{fig:PDOS-all}
\end{figure*}

The selection of valleys $V_x$ or $V_y$ can be achieved by at least
two different optical methods: (i) using the fact that the direct gap
is different at the two valley pairs; or (ii) using the optical
selection rules. The direct transitions at the $V_x$ and $V_y$ valleys
have different energies, provided there is a means to identify the
orientation of the crystal (Fig.~\ref{fig:bandgap}).  We plot the
energy difference between valence and conduction band of SnS as
functions of in plane wave vectors shown in Fig.~\ref{fig:bandgap} (a)
and (b). It can be seen that the gap surface of $\epsilon_x=0.22$
(Fig.~\ref{fig:bandgap} (a)) is equivalent to $\epsilon_y=0.27$
(Fig.~\ref{fig:bandgap} (b)) but rotated 90$^\circ$. It is evident
that under uniaxial stress in $\hat{y}$ the bands have rotated in the
Brillouin Zone, i.e. the $V_y$ valley effectively becomes the $V_x$
valley after passing the transition point of $\epsilon_{y}$=0.08.

\begin{figure}
  \centering
  \includegraphics[width=8.6cm]{valley.pdf}
  \caption{Band gap surfaces (a) $\epsilon_x=0.22$ and (b)
    $\epsilon_y=0.27$ demonstrate the valley swapping. (c) Schematic
    selective valley polarization.  (d) Evolution of the bandgap and
    (e, f) relative polarization under uniaxial stress along
    $\hat{y}$, highlighting the phase transition.  Under small strain,
    the direct transition at $V_x$ is only visible under incident
    $x$-polarized light, while the $V_y$ transition is visible under
    both incident $y$ and $x$ (with a small coupling) polarized
    light.}
  \label{fig:bandgap}
\end{figure}

\subsection{Transition probabilities}
Using linearly polarized light to select the valleys $V_x$ or $V_y$
provides an additional method to detect the phase transition
optically. The interband transition probability at a given wave vector
$\bf k$ is given by~\cite{rodin-PRB-93-045431, xiao-PRL-108-196802-2012}
\begin{equation}
P_i({\bf k})\propto\left|\frac{m}{\hbar}\left\langle c({\bf k}) \left|\frac{\partial H}{\partial k_i}\right|v({\bf k})\right\rangle\right|^2,
\end {equation}
where $i$ is the direction of the light polarization, $c(\bf k)$ is
the conduction band wave function, $v(\bf k)$ is the valence band wave
function, and $H$ is the Hamiltonian.  Alternatively, one can relate
the transition probability to the dipole moment between the initial
and the final bands:
$\langle \mathbf{c}|\hat p_{x/y}|\mathbf{v}\rangle$, where the
momentum direction corresponds to the light polarization. For the
transition to be allowed, the dipole moment must not vanish. It is
possible to determine whether it is finite or not using the symmetry
of the bands and the momentum. Since the dipole moment is computed by
integrating the product of the initial and final wave functions, and
the momentum, it is nonzero only if this product
($\propto \mathbf{c}^\dagger (\mathbf
{r})\partial_{x/y}\mathbf{v}(\mathbf{r})$)
is not odd with respect to any of the axes. In other words, the
integrand must remain unchanged under every symmetry transformation of
the space group characterizing the crystal.

We used our \emph{ab initio} results to calculate the transition
probabilities.  For unstrained SnS, $\hat{y}$-polarized light
populates only the $V_y$ valleys, as there is no coupling between the
valence and conduction band at $V_x$ in the $\hat{y}$ direction (see
Fig.~\ref{fig:bandgap} (e)). As shown by
Ref. ~\cite{rodin-PRB-93-045431}, the conduction band, valence band,
and the $p_x$ have a same irreducible representation. Consequently,
the direct product of these quantities results in a non-vanishing
transition probability coupling. On the other hand,
$\hat{y}$-polarized light cannot excite $V_x$, as it possesses
different representation.  $\hat{x}$-polarized light can populate both
$V_x$ and $V_y$ but it populates predominantly the $V_x$ valleys, with
$P_x(V_x)/P_x(V_y)\sim40$.  Similar behavior is observed in GeSe with
a smaller selective valley polarization ratio. For instance, with
linearly $\hat{x}$-polarized light the selective valley polarization
ratio was found to be $P_x(V_x)/P_x(V_y)\sim15$.  The schematic valley
polarization is shown in Fig.~\ref{fig:bandgap}~(c).

The evolution of local gap $V_x$ and $V_y$ of SnS under stress in the
$\hat{y}$ direction is shown in Fig.~\ref{fig:bandgap}(d). We see that
there is an abrupt change in $V_y$ gap near the transition point
$\epsilon_y=0.08$. We also plot the relative polarization
$P_y(V_x)/P_x(V_x)$ and $P_x(V_y)/P_y(V_y)$ as a function of axial
strain $\epsilon_y$, shown in Fig.~\ref{fig:bandgap}(e) and (f) for
SnS and GeSe, respectively. As we discussed earlier,
$\hat{x}$-polarized light populates predominantly the $V_x$ valleys
but there is still a small transition probability at $V_y$ when
$\hat{x}$-polarized light is used. The absorption threshold for
$\hat{x}$-polarized light has an abrupt change near $\epsilon_y=0.08$
($\epsilon_y=0.15$ for GeSe), when the phase transition takes
place. However, the absorption edge for $\hat{y}$-polarized light
changes smoothly.

Before the transition point, the structure has a mirror symmetry
inverting $\hat{y}$, and the $V_y$ valleys can be populated using
polarized light along $\hat{y}$ and $\hat{x}$ (the latter with a very
small coupling).  However, after the transition point, the puckering
direction is rotated to be in the $\hat{y}$, and the reflection
symmetry in $\hat{y}$ is broken, whereas a reflection symmetry emerges
in $\hat{x}$. As a result, $V_x$ can be excited by both $\hat{x}$ and
$\hat{y}$ polarized light after the transition takes place.  We have
therefore demonstrated how optical transitions can be used to detect
the orientation of the structure which determines valley
configurations.

In summary, we have used first-principles calculations to demonstrate the
potential of group-IV monochalcogenide monolayers as functional
materials for information storage.  This strategy, demonstrated using
SnS and GeSe as prototypes, relies on the metastability and the
possibility of switching the polarization direction using stress or
electric field, creating a binary memory device.  Comparing these
prototype materials, SnS differs from GeSe because it has a stable
centrosymmetric phase which, at $T=0$, is close in energy to the
$Pnma$-ML phase.

Due to their peculiar band structures, both SnS and GeSe could in
principle be used as functional materials for memory devices that can
easily be interfaced with valleytronics logic.  Valleytronics is based
on the concept that the valley index can potentially be used to store
information for subsequent logic operations, equivalent to spin in
spintronics.  However, in most valleytronics materials the information
can be considered non-volatile only up to the timescale defined by
inter-valley scattering processes, which are ubiquitous in real
materials.  Structural changes, used to store information in phase
change memory devices, take place on a timescale orders of magnitude
longer.  Materials such as SnS and GeSe can be used to convert
information stored as structural phase into information stored as
valley index.  One possibility is for example by using near-bandgap
light that excites only the pair of valleys corresponding to the
lowest energy exciton.  The subsequent electronic state will have
electron-hole pairs with momentum $(\pm k_x,0)$ or $(0,\pm k_y)$,
depending on the structure orientation.  This valley state can be
transmitted onto a valley-filter~\cite{gunlycke-PRL-106-136806}.
Alternatively, if coupled to a polarized light detector, the
polarization switching can be detected optically taking advantage of
valley-dependent direction of the linear polarization of the
luminescence~\cite{rodin-PRB-93-045431}.

\begin{acknowledgments}
  P.Z.H. is grateful for the support of the Physics and Mechanical
  Engineering Departments at Boston University, the hospitality of the
  NUS Centre for Advanced 2D Materials and Graphene Research Centre
  where this work was initiated, the support of the Materials Science
  and Engineering Innovation Grant and the Boston University High
  Performance Shared Computing Cluster. A.C. acknowledges support by
  the National Research Foundation, Prime Minister Office, Singapore,
  under its Medium Sized Centre Programme and CRP award ``Novel 2D
  materials with tailored properties: beyond graphene'' (Grant No.
  R-144-000-295-281). D.K.C. is grateful for the hospitality of the
  Aspen Center for Physics which is supported by NSF Grant
  $\#$PHY-1066293, and of the International Institute for Physics of
  the Federal University of Rio Grande do Norte, in Natal, Brazil,
  where some of this work was completed.  HSP acknowledges the support
  of the Mechanical Engineering Department at Boston University. We
  thank Alex Rodin for helpful comments and discussions.
\end{acknowledgments}


\section{Introduction} \label{section:intro}

Seidel's switching is a graph operation which makes a
given vertex adjacent to precisely those vertices to which it was non-adjacent
before, while keeping the rest of the graph unchanged. Two graphs are called
switching-equivalent if one can be made isomorphic to the other one by a sequence
of switches. The class of graphs that are pairwise switching-equivalent is
called a switching class.

Hage in his PhD thesis~\cite[p.~115, Problem~8.5]{Hage01} posed the problem to characterize
the graphs that have the maximum (or minimum) number of edges in their switching class.
We call such graphs \emph{switching-maximal} and \emph{switching-minimal}, respectively.

Some properties of switching-maximal graphs were studied
by Kozerenko~\cite{Kozerenko15}. He proved that any graph with sufficiently
large minimum degree is switching-maximal, and that the join of certain graphs
is switching-maximal.
Further, he gave a characterization of triangle-free switching-maximal graphs
and of non-hamiltonian switching-maximal graphs.

It is easy to observe that a graph is switching-maximal if and only if its
complement is switching-minimal. We call the problem to decide if a graph is switching-minimal
\textsc{Switch-Minimal}.

Jel{\'\i}nkov{\' a} et al.~\cite{JSHK11-param} studied the more general problem
\textsc{Switch-Few-Edges} -- the problem of deciding
if a graph can be switched to contain at most a certain number of edges.
They presented a proof that the problem is NP-complete. Unfortunately, their proof is not correct.
Specifically, Lemma 4.3 of~\cite{JSHK11-param}, which claims to establish a
reduction from the classical \textsc{Max-Cut} problem to
\textsc{Switch-Few-Edges}, is false. The claim of the lemma fails, e.~g., on a
graph $G$ formed by two disjoint cliques of the same size.

In this paper, we provide a different proof of the NP-hardness of
\textsc{Switch-Few-Edges}, based on a reduction from a restricted
version of \textsc{Max-Cut}.
Furthermore, we strengthen this result by proving that for any $c > 0$,
\textsc{Switch-Few-Edges} is NP-complete even
if we require that the input graph has density at most~$c$.
We also prove that if the problem \textsc{Switch-Minimal} is co-NP-complete, then for
any $c > 0$, the problem is co-NP-complete even on graphs with density at most~$c$.

We thus partially answer a question of Matou\v sek and
Wagner~\cite{MW14} posed in connection with properties of simplicial complexes
-- they asked if deciding switching-minimality was easy for graphs of bounded density.
Our results also indicate that it might be unlikely to get an easy
characterization of switching-minimal (or switching-maximal) graphs, which
contributes to understanding Hage's question~\cite{Hage01}.

\subsection{Formal definitions and previous results}
\label{subs:form}

Let $G$ be a graph. Then the \emph{Seidel's switch of a vertex subset} $A
\subseteq V(G)$ is denoted by $S(G,A)$ and is defined by
\[S(G,A) = (V(G), E(G) \bigtriangleup \{ xy : x \in A,\ y \in V(G) \setminus A
\} ).
\]

\noindent
It is the graph obtained from $G$ by consecutive switching of the vertices of $A$.

We say that two graphs $G$ and $H$ are \emph{switching-equivalent} (denoted by
$G \sim H$) if there is a
set $A \subseteq V(G)$ such that $S(G,A)$ is isomorphic to $H$.
The set
$[G] = \{ S(G,A) : A \subseteq V(G) \}$ is called the \emph{switching class}
of $G$.

We say that a graph $G$ is \emph{$(\leq k)$-switchable} if there is a set $A
\subseteq V(G)$ such that $S(G,A)$ contains at most $k$ edges. Analogously, a
graph $G$ is \emph{$(\geq k)$-switchable} if there is a set $A
\subseteq V(G)$ such that $S(G,A)$ contains at least $k$ edges.

It is easy to observe that a graph $G$ is $(\leq k)$-switchable if and only if
the complement $\overline{G}$ is $\left(\geq \binom{n}{2} -
k\right)$-switchable.
We may, therefore, focus on $(\leq k)$-switchability only.

We examine the following problems.

\newdimen\sirka
\sirka=-\fboxsep \advance\sirka by -\fboxrule \multiply\sirka by 2
\advance\sirka by \hsize
\vskip\fboxsep
\vskip\fboxsep
\noindent
\framebox[\hsize][l]{\begin{minipage}{\sirka}
\textsc{Switch-Few-Edges}\\
 \textbf{Input:} A graph $G=(V,E)$, an integer $k$\\
 \textbf{Question:} Is $G$ $(\leq k)$-switchable?
 \end{minipage}}
\vskip\fboxsep

\vskip\fboxsep
\noindent
\framebox[\hsize][l]{\begin{minipage}{\sirka}
\textsc{Switch-Minimal}\\
 \textbf{Input:} A graph $G=(V,E)$\\
 \textbf{Question:} Is $G$ switching-minimal?
 \end{minipage}}
\vskip\fboxsep
\vskip\fboxsep

We say that a graph is \emph{switching-reducible} if $G$ is \emph{not}
switching-minimal, in other words, if there is a set $A
\subseteq V(G)$ such that $S(G,A)$ contains fewer edges than~$G$.
For further convenience, we also define the problem \textsc{Switch-Reducible}.

\vskip\fboxsep
\vskip\fboxsep
\noindent
\framebox[\hsize][l]{\begin{minipage}{\sirka}
\textsc{Switch-Reducible}\\
 \textbf{Input:} A graph $G=(V,E)$\\
 \textbf{Question:} Is $G$ switching-reducible?
 \end{minipage}}
\vskip\fboxsep
\vskip\fboxsep

Let $G = (V,E)$ be a graph. We say that a partition $V_1$, $V_2$ of $V$ is a
\emph{cut} of $G$. For a cut $V_1$, $V_2$, the set of edges that have exactly one end-vertex
in $V_1$ is denoted by ${\mathop{\rm cutset}}(V_1)$, and the edges of ${\mathop{\rm cutset}}(V_1)$ are called
\emph{cut-edges}.
When there is no danger of confusion, we also say that a single subset $V_1 \subseteq V$ is a cut
(meaning the partition $V_1$, $V\setminus V_1$).

\subsection{Easy cases}
\label{subs:easy}

In this subsection we present several results about easy special cases of the
problems that we focus on. This complements our hardness results.

The following theorem was proved by Ehrenfeucht et~al.~\cite{EHHR00-issues} and
also independently (in a slightly weaker form) by Kratochv\'\i l~\cite{Kratochvil03}.

\begin{theorem}\label{thm:ehhr-reg}
Let $\mathcal P$ be a graph property that can be decided in time $\mathcal O(n^a)$ for an
integer $a$. Let every graph with $\mathcal P$ contain a vertex of degree at most
$d(n)$. Then the problem if an input graph is switching-equivalent to a graph with
$\mathcal P$ can be decided in time $\mathcal O(n^{d(n) + 1 + \max(a,2)})$.
\end{theorem}

The proof of Theorem~\ref{thm:ehhr-reg} also gives an algorithm that works in
the given time. Hence, it also provides an algorithm for
\textsc{Switch-Few-Edges}: in a graph with at most $k$ edges all vertex degrees
are bounded by $k$. Hence, we can use $d(n) = k$ and $a=2$ and get an $\mathcal
O(n^{k+3})$-time algorithm. It was further proved by Jel\'\i nkov\' a et al.~\cite{JSHK11-param} that
\textsc{Switch-Few-Edges} is fixed-parameter tract\-able; it has a kernel with
$2k$ vertices, and there is an algorithm running in time $\mathcal O(2.148^k \cdot n +m)$, where $m$ is the number
of edges of the input graph. In Section~\ref{sec:swfew-npc}, we provide a corrected
NP-completeness proof.

The following proposition states a basic relation of
switching-minimality and graph degrees.

\begin{proposition}[folklore]\label{pro:pul}
 Every switching-minimal graph $G=(V,E)$ on $n$ vertices has maximum degree at
most~$\lfloor (n-1)/2 \rfloor$.
\end{proposition}
\begin{proof}
 Clearly, if $G$ contains a vertex $v$ of degree greater than $\lfloor (n-1)/2
\rfloor$, then $S(G,\{v\})$ has fewer edges than $G$, showing that $G$ is not
switching-minimal
\qed\end{proof}

We remark that for a given graph $G$ we can efficiently construct a switch
whose maximum degree is at most $\lfloor (n-1)/2 \rfloor$; one by one, we switch
vertices whose degree exceeds this bound (in this way, the number of edges is
decreased in each step). However, the graph
constructed by this procedure is not necessarily switching-minimal.

Let $e(A)$ denote the number of edges whose one vertex is in $A$ and the
other one in $V(G) \setminus A$. The next proposition is an equivalent
formulation of Lemma 2.5 of Kozerenko~\cite{Kozerenko15}, strengthening
Proposition~\ref{pro:pul}.

\begin{proposition}\label{prop:kozerenko}
A graph $G$ is switching-minimal if and only if for every $A \subseteq V(G)$,
 we have
\begin{displaymath}
2e(A) \leq |A|(|V(G)| -  |A|).
\end{displaymath}
\end{proposition}

We derive the following consequence.

\begin{proposition}\label{prop:maxdeg}
Let $G$ be a graph with $n$ vertices. If the maximum vertex degree in $G$ is at most
$\frac n 4$, then $G$ is switching-minimal.
\end{proposition}
\begin{proof}
Let $A$ be any subset of $V(G)$. We observe that $e(A) = e(V(G) \setminus A)$;
hence we can assume without loss of generality that $|A| \leq n/2$, and thus
$|V(G)| -  |A| \geq n/2$.

Further, as $e(A) \leq \sum_{v\in A}\mathop{{\rm deg}}(v)$, we have that $e(A) \leq |A|{\frac
n 4}$. Hence, $2e(A) \leq |A|(|V(G)| -  |A|)$, and the condition of
Proposition~\ref{prop:kozerenko} is fulfilled
\qed\end{proof}

Proposition~\ref{prop:maxdeg} implies that \textsc{Switch-Few-Edges} and
\textsc{Switch-Minimal} are trivially solvable in polynomial time for graphs on
$n$ vertices with maximum degree at most~$\frac n 4$.

We note that in Proposition~\ref{prop:maxdeg}, the bound $\frac n 4$ in general
cannot be improved, as shown by the example of a $k$-regular bipartite graph on
$n$ vertices with $k>\frac n 4$. Such a graph is switching-equivalent to a
$(\frac n 2 -k)$-regular bipartite graph, and therefore is not
switching-minimal.

\section{NP-Completeness of {\sc Switch-Few-Edges}}
\label{sec:swfew-npc}

Jel{\'\i}nkov{\' a} et al.~\cite{JSHK11-param} presented a proof that the problem
\textsc{Switch-Few-Edges} is NP-complete. Unfortunately, there is an error in their proof.
We present another proof here. The core of the original proof is a reduction from the \textsc{Max-Cut} problem.
Our reduction works in a similar way. However, we need the following more special version of
\textsc{Max-Cut} (we prove the NP-completeness of {\sc Large-Deg-Max-Cut} in
Section~\ref{sec:npc-large-max-cut}).

\vskip\fboxsep
\vskip\fboxsep
\noindent
\framebox[\hsize][l]{\begin{minipage}{\sirka}
\textsc{Large-Deg-Max-Cut}\\
 \textbf{Input:} A graph $G$ with $2n$ vertices such that the minimum vertex
degree of $G$ is $2n-4$ and the complement of $G$ does not contain triangles; an integer $j$\\
 \textbf{Question:} Does there exist a cut $V_1$ of $V(G)$ with at least $j$ cut-edges?
 \end{minipage}}
\vskip\fboxsep
\vskip\fboxsep

\begin{proposition}
\label{prop:eq}
Let $G$ be a graph. In polynomial time, we
can find a graph $G'$ such that $|V(G')| = 4|V(G)|$ and the following
statements are equivalent for every integer $j$:
\begin{enumerate}
\item[(a)] There is a cut in $G$ with at least $j$ cut-edges,
\item[(b)] there exists a set $A\subseteq V(G')$ such that $S(G',A)$
contains at most $|E(G')| - 16j$ edges.
\end{enumerate}
\end{proposition}

\begin{proof}
We first describe the construction of the graph~$G'$. For each vertex
$u$ of $G$ we create a corresponding four-tuple $\{u', u'', u''', u''''\}$ of
pairwise non-adjacent vertices in~$G'$. An edge of $G$ is then represented by a
complete bipartite graph interconnecting the two four-tuples, and a non-edge in
$G$ is represented by $8$ edges that form a cycle that alternates between the
two four-tuples (see Fig.~\ref{figure:udelatka}).

We remark that our construction of $G'$ follows a similar idea as the
construction in the attempted proof of Jel{\'\i}nkov{\' a} et al.~\cite{JSHK11-param},
a notable difference being that in the original construction, a vertex of $G$
was replaced by a pair of vertices of $G'$ rather than a four-tuple.

\begin{figure}
\centering
\includegraphics{udelatka}
\caption{The representation of non-edges and edges of $G$.\label{figure:udelatka}}
\end{figure}

A vertex four-tuple in $G'$ corresponding to a vertex of $G$ is called an
\emph{o-vertex}. A pair of o-vertices
corresponding to an edge of $G$ is called an \emph{o-edge} and a pair of o-vertices
corresponding to an non-edge of $G$ is called an \emph{o-non-edge}. Where there is no danger of confusion, we
identify o-vertices with vertices of $G$, o-edges with edges of $G$ and o-non-edges with non-edges of $G$.

We now prove that the statements (a) and (b) are equivalent.
First assume that there is a cut $V_1$ of $V(G)$ with $j'$ cut-edges. Let $V_1'$
be the set of vertices $u', u'', u''', u''''$ for all $u \in V_1$.
We prove that $S(G',V_1')$ contains at most $|E(G')| - 16j'$ edges.

We say that a non-edge \emph{crosses the cut $V_1$} if the non-edge has exactly one
vertex in $V_1$.
It is clear that $G'$ contains 16 edges per every o-edge and 8 edges per every o-non-edge.
In $S(G',V_1')$, every o-edge corresponding to an edge that is not a cut-edge is unchanged
by the switch and yields 16 edges. Similarly, every o-non-edge corresponding to a non-edge that
does not cross the cut yields 8 edges.

Fig.~\ref{figure:ctv-legalni} illustrates the switches of o-non-edges and
o-edges that have exactly one end-o-vertex in $V_1$.
We can see that every o-non-edge corresponding
to a non-edge that crosses the cut yields 8 edges in $S(G',V_1')$, and that every o-edge corresponding
to a cut-edge yields 0 edges. Altogether, $S(G',V_1')$ has $|E(G')| - 16j'$ edges,
which we wanted to prove.

\begin{figure}
\centering
\includegraphics{ctv-legalni}
\caption{Switches of an o-non-edge and of an o-edge.\label{figure:ctv-legalni}}
\end{figure}

Now assume that there exists a set $A\subseteq V(G')$ such that $S(G',A)$
contains at most $|E(G')| - 16j$ edges. We want to find a cut in $G$ with at
least $j$ cut-edges.

We say that an o-vertex $u$ of $G'$ is \emph{broken in $A$} if $A$ contains
exactly one, two or three vertices out of $u', u'', u''', u''''$; otherwise, we say that $u$ is \emph{legal in $A$}.
We say that an o-edge or o-non-edge $\{u,v\}$ is \emph{broken in $A$} if at
least one of the o-vertices $u$, $v$ is broken. Otherwise, we say that $\{u,v\}$ is \emph{legal in $A$}.

If all vertices of $G$ are legal in $A$, we say that $A$ is \emph{legal}.
Legality is a desired property, because for a legal set $A$ we can define a subset
$V_A$ of $V(G)$ such that
\[
V_A =\left\{u \in V(G): \{u',u'',u''',u''''\}\subseteq A\right\}.
\]
The set $V_A$
then defines a cut in $G$.
If a set is not legal, we proceed more carefully to get a cut from it.
For any vertex subset $A$, we say that a set $A'$ is a \emph{legalization} of $A$ if $A'$
is legal and if $A'$ and $A$ differ only on o-vertices that are broken in $A$.

We want to show that for every illegal set $A$, there exists its legalization
$A'$ such that the number of edges in $S(G',A')$ is not much higher than in
$S(G',A)$. To this end, we give the Algorithm Legalize
which for a set $A$ finds such a legalization $A'$.
During the run of the Algorithm, we keep a set $A''$. In the beginning we set
$A'' := A$ and in each step we change $A''$ so that more o-vertices are legal.

We define some notions needed in the Algorithm. Let $v$ be an o-vertex and consider the o-vertices that are adjacent to $v$
(through an o-edge); we call them \emph{o-neighbors} of $v$. The o-neighbors of
$v$ are four-tuples of vertices and some of those vertices are in $A''$, some of them are not.
We define ${\mathop{\rm dif}}(v)$ as the number of such vertices that are in $A''$ minus the number
of such vertices that are not
in $A''$. (Note that ${\mathop{\rm dif}}(v)$ is always an even number, because the total number of vertices
in o-neighbors is even. If all o-neighbors were legal, then ${\mathop{\rm dif}}(v)$ would be divisible by four.)

\begin{figure}
\centering
\framebox[\hsize][l]{\begin{minipage}{\sirka}
\textbf{Algorithm Legalize(A)}\\
Set $A'' := A$; do the following while any of the cases applies.
\begin{enumerate}[label=Case \arabic*.,leftmargin=*]
\item\label{case:a}
There exists a broken o-vertex $v$ such that $|{\mathop{\rm dif}}(v)| \geq 4$. If ${\mathop{\rm dif}}(v) \geq 4$,
set $A'' := A'' \setminus \{v', v'', v''', v''''\}$. Otherwise,
set $A'' := A'' \cup \{v', v'', v''', v''''\}$.
\item\label{case:b}
Case 1 does not apply and there exists an asymmetric broken vertex $v$ such that
$v$ contains exactly one vertex from $A''$ and ${\mathop{\rm dif}}(v) = 2$. Set $A'' := A''
\setminus \{v', v'', v''', v''''\}$.
\item\label{case:c}
Case 1 does not apply and there exists an asymmetric broken vertex $v$ such that
$v$ contains exactly three vertices from $A''$ and ${\mathop{\rm dif}}(v) = -2$. Set $A'' := A''
\cup \{v', v'', v''', v''''\}$.
\item\label{case:d}
None of Cases 1, 2, 3 applies and there exist two adjacent broken
o-vertices $u$ and $v$. Set
$$A_1 := (A'' \cup \{u', u'', u''', u''''\}) \setminus \{v', v'', v''', v''''\},$$
$$A_2 := (A'' \cup \{v', v'', v''', v''''\}) \setminus \{u', u'', u''', u''''\}.$$
If $|E(S(G',A_1))| < |E(S(G',A_2))|$ then set $A'' := A_1$, otherwise $A'' := A_2$.
\item\label{case:e}
None of the above cases applies. Then legalize the remaining broken
o-vertices arbitrarily, output $A''$ and STOP.
\end{enumerate}
 \end{minipage}}
\caption{The Algorithm Legalize.\label{figure:alg}}
\end{figure}

The Algorithm is given in Fig.~\ref{figure:alg}.
As in the last step the Algorithm legalizes all remaining broken o-vertices, it
is clear that the set $A''$ output by the Algorithm is a
legalization of $A$.
We prove that $|E(S(G',A''))| - |E(S(G',A))| \leq 7$.

We need to introduce more terminology. A pair of vertices of $G'$ which belong to the same o-vertex is called a
\emph{v-pair}. A pair of vertices of $G'$ which belong to different
o-vertices that are adjacent (in $G$) is called an \emph{e-pair}.
A pair of vertices of $G'$ which belong to different o-vertices that are
non-adjacent (in $G$) is called an \emph{n-pair}. It is easy to see that any
edge of $G'$ or $S(G',A'')$ is either a v-pair, an e-pair or an n-pair. We call such edges \emph{v-edges},
\emph{e-edges} and \emph{n-edges}, respectively.

We say that a broken o-vertex $v$ is \emph{asymmetric} if it contains an odd number of
vertices of $A''$; we say that a broken o-vertex
is \emph{symmetric} if it contains two vertices out of $A''$.

To measure how the number of edges of $S(G',A'')$ changes during the run of the
Algorithm, we define a variable ${\mathop{c}}(A'')$ which we call the \emph{charge} of
the graph $S(G',A'')$.
Before the first step we set ${\mathop{c}}(A'') := |E(S(G',A))|$. After a step of the
Algorithm, we update ${\mathop{c}}(A'')$ in the following way.

\begin{itemize}
\item For every v-pair or e-pair that was an edge of $S(G',A'')$ before the step
and is no longer an edge of $S(G',A'')$ after the step, we decrease ${\mathop{c}}(A'')$
by one.
\item For every v-pair or e-pair that was not an edge of $S(G',A'')$ before the step
and that has become an edge of $S(G',A'')$ after the step, we increase ${\mathop{c}}(A'')$
by one.
\item For every o-vertex $v$ that was legalized in the step and is incident to an o-non-edge,
we change ${\mathop{c}}(A'')$ in the following way:
\begin{itemize}
\item if $v$ is symmetric, we increase ${\mathop{c}}(A'')$ by $2.5$ for every o-non-edge
incident to $v$;
\item if $v$ is asymmetric, we increase ${\mathop{c}}(A'')$ by $1.5$ for every o-non-edge
incident to $v$.
\end{itemize}
\end{itemize}

\begin{figure}
\centering
\includegraphics{ctverice}
\caption{All possible illegal switches of o-non-edges (up to symmetry). Vertices
of $A$ are marked in white and edges are as in $G$ (left to the arrow) and as in
$S(G',A)$ (right to the arrow). In the highlighted cases, the number of n-edges in $S(G',A)$ is lower
than~$8$.\label{figure:ctv-non-edges}}
\end{figure}

To explain the last two points, we observe how the number of n-edges increases
after legalizing an o-vertex. By analyzing all cases of o-non-edges with one or
two broken end-o-vertices (see Fig.~\ref{figure:ctv-non-edges}),
we get that there are four cases where the o-non-edges have less than 8
n-edges before legalization: either 6 or 4 n-edges. In these cases, both end-o-vertices are broken.
If there are only 4 n-edges, at least one of the end-o-vertices is symmetric.
After one end-o-vertex is legalized,
the number of n-edges increases by 2 or 4. When the second end-o-vertex is legalized, the
number of n-edges does not increase for this particular o-non-edge.

After both end-o-vertices are legalized, the charge has been changed in the
following way: if both end-o-vertices were symmetric, we have
increased the charge by $5$. If one of them was symmetric and the other one was
asymmetric, we have increased the charge by $4$. Finally, if both were
asymmetric, we have increased the charge by $3$. In all these cases,
the increase is an upper bound on the number of contributed n-edges.

Further, every v-edge or e-edge that has appeared or disappeared during the run of the Algorithm
is counted immediately after the corresponding step. Hence, we have proved the following Claim.

\begin{claimm}\label{cl:upper-bound}
At the end of the Algorithm we have that ${\mathop{c}}(A'') \geq |E(S(G',A''))|$.
\end{claimm}

Next, we give an upper bound on the charge ${\mathop{c}}(A'')$.

\begin{claimm}\label{cl:decrease}
After every step of the Algorithm except for the last one, the charge ${\mathop{c}}(A'')$ is decreased.
After the last step, the charge is increased by at most 7. Hence, ${\mathop{c}}(A'') \leq |E(S(G',A))| + 7$.
\end{claimm}

To prove Claim~\ref{cl:decrease}, we count how the charge changes after each
step of the Algorithm Legalize. We distinguish cases according to which the step was done.

\begin{enumerate}[label=Case \arabic*.,leftmargin=*]
\item
	We may assume without loss of generality that ${\mathop{\rm dif}}(v)\geq 4$ (otherwise we swap the roles of $A''$ and $V(G') \setminus A''$.
	Further, $v$ can be either symmetric or asymmetric; we first assume that $v$ is symmetric (see Fig.~\ref{figure:case1}). Then by its legalization the number
	of v-edges is decreased by $4$.

	As ${\mathop{\rm dif}}(v)\geq 4$, then among vertices in o-neighbors of $v$, there must be at least four more vertices
	belonging to $A''$ than those not belonging to $A''$. Thus, by removing any vertex of $\{v', v'', v''', v''''\}$ from $A''$
	we reduce the number of e-edges by at least $4$. As $v$ contains two vertices out of $\{v', v'', v''', v''''\}$, we reduce the number
	of e-edges by at least $8$.

	For n-pairs that have one vertex inside $v$ the charge is increased by at most $3 \cdot 2.5$, which is $7.5$.
	To sum it up:
	\begin{itemize}
	\item For v-pairs the charge is decreased by $4$,
	\item for e-pairs the charge is decreased by at least $8$,
	\item for n-pairs the the charge is increased by at most $7.5$.
	\end{itemize}
	Altogether, the charge is decreased by at least $4.5$.

	If the o-vertex $v$ is asymmetric, then in an analogical way we have
	that for v-pairs the charge is decreased by 3, for e-pairs the charge is decreased by at least 4,
	and for n-pairs the the charge is increased by at most $4.5$.
	Altogether, the charge is decreased by at least $2.5$.

\item
	The analysis is similar as above. We get $-3$ for v-pairs, $-2$ for e-pairs, and $\leq 4.5$ for n-pairs.
	Altogether, the charge is decreased by at least $0.5$.
\item
This case is symmetric to Case 2. Hence, the charge is decreased by at least $0.5$ as well.
\item
	In this case, when counting how the charge was changed because of e-pairs, we need to bound both
	the number of e-edges between a vertex in $u$ and a vertex in $v$, and the number of e-edges
	between a vertex inside $u$ or $v$ and a vertex inside one of their other o-neighbors.
	This depends also on the values of ${\mathop{\rm dif}}(u)$ and ${\mathop{\rm dif}}(v)$.

	We analyze four subcases of o-edges whose both end-o-vertices are
	broken -- they are numbered as in Fig.~\ref{figure:ctv-edges}.

	\begin{enumerate}[label=\Roman*.,leftmargin=*]
	\item

\begin{figure}[t]
\centering
\includegraphics{case1}
\caption{A simplified illustration to the analysis of Case 1. Vertices of $A''$ are marked in white, and edges are as in $S(G',A'')$
before the step (left to the arrow) and after the step (right to the arrow).
\label{figure:case1}}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics{caseI}
\caption{A simplified illustration to the analysis of Case 4, I. Vertices of $A''$ are marked in white, and edges are as in $S(G',A'')$ before the step (left to the
arrow) and after the step (right to the arrow).\label{figure:caseI}}
\end{figure}

\begin{figure}
\centering
\includegraphics{ctv-broken-edges}
\caption{All possible illegal switches of o-edges (up to symmetry). Vertices
of $A$ are marked in white and edges are as in $G$ (left to the arrow) and as in
$S(G',A)$ (right to the arrow). In the highlighted cases, both end-o-vertices
are broken.\label{figure:ctv-edges}}
\end{figure}

	First assume that ${\mathop{\rm dif}}(u) = 0$ and ${\mathop{\rm dif}}(v) = 0$ (see Fig.~\ref{figure:caseI}). We can see that vertices
	inside $v$ contribute by $-2$ to ${\mathop{\rm dif}}(u)$. Hence, outside $v$, there must be two more
	vertices in o-neighbors of $u$ that are in $A''$ than those not in $A''$.
	The same holds symmetrically for o-neighbors of $v$ outside $u$.

	We may without loss of generality assume that the Algorithm chose to set
	$$A'' := (A'' \cup \{v', v'', v''', v''''\}) \setminus \{u', u'', u''', u''''\}.$$
	Then, the number of e-pairs adjacent to both $u$ and $v$ is decreased by 10; the number of e-pairs adjacent to $u$ and not to $v$
	is decreased by $2$, and the number of e-pairs adjacent to $v$ and not to $u$ is increased by $6$. Altogether,
	the charge is decreased by $6$ for e-pairs.

	For v-pairs, the charge is decreased by $6$, and for n-pairs, the charge is increased by at most $6\cdot 1.5$. Altogether,
	the charge is decreased by at least $3$.

	It remains to analyze the cases when ${\mathop{\rm dif}}(u)$ and ${\mathop{\rm dif}}(v)$ are different. As neither Case 2 nor Case 3 applies, we know
	that none of ${\mathop{\rm dif}}(u)$, ${\mathop{\rm dif}}(v)$ is equal to $2$.

	By analogical ideas as above, we get that if one of ${\mathop{\rm dif}}(u)$, ${\mathop{\rm dif}}(v)$ is equal to $0$ and the other one to $-2$,
	the charge is decreased by at least $9$. If both ${\mathop{\rm dif}}(u)$, ${\mathop{\rm dif}}(v)$ are equal to $-2$, then the charge is decreased by at least $7$.
	\item[II.]
	As $u$ is asymmetric and $v$ is symmetric, we have that for n-pairs the
	charge is increased by $3 \cdot 2.5 + 3 \cdot 1.5$, which is $12$. For v-pairs, the
	charge is decreased by $3 + 4$, which is $7$.

	We consider the case when the Algorithm chose to set
	$$A'' := A'' \cup \{u', u'', u''', u''''\} \setminus \{v', v'', v''', v''''\}$$
	(if we get a sufficient bound for this case, then the other case could
	only be better).

	To count the decrease for e-pairs, we need to consider the values of
	${\mathop{\rm dif}}(u)$ and ${\mathop{\rm dif}}(v)$.
	Assume that ${\mathop{\rm dif}}(u) = 0$. Then, outside $v$, there must be the same number of vertices in
	o-neighbors of $u$ that are in $A''$ as those that are not in $A''$.

	If ${\mathop{\rm dif}}(v) = 0$, then outside $u$ there must be two more vertices in o-neighbors of $v$ that are in
	$A''$ than those not in $A''$. Then for e-pairs, the charge is decreased
	by $12$. If ${\mathop{\rm dif}}(v) = 2$, then using analogous ideas we get that for e-pairs, the charge is decreased
        by $16$. If ${\mathop{\rm dif}}(v) = -2$, we get $8$.

	Now assume that ${\mathop{\rm dif}}(u) = -2$. By considering the number of vertices in
	o-neighbors of $u$ and $v$, we get that the charge decrease for e-pairs is
	either $14$ (if ${\mathop{\rm dif}}(v) = -2$) or $18$ (if ${\mathop{\rm dif}}(v) = 0$) or $22$ (if
	${\mathop{\rm dif}}(v)= 2$).

	As Case 2 does not apply, we know that ${\mathop{\rm dif}}(u)$ is not equal to $2$.
	Hence, we have considered all the cases, and the charge decrease for
	e-pairs is at least $8$. Altogether, the charge is decreased by at least
	$-12 +7 + 8$, which is $3$.

	\item[III.]
	As both $u$ and $v$ are asymmetric, we have that for n-pairs the charge is increased
	by $6 \cdot 1.5$, which is $9$. For v-pairs, the charge is decreased by
	$3 + 3$, which is $6$.

	Again, we consider the case when the Algorithm chose to set
        $$A'' := A'' \cup \{u', u'', u''', u''''\} \setminus \{v', v'', v''', v''''\}.$$

	By using the same idea as above, we get that for e-pairs, the charge is
	decreased by $18$ (if ${\mathop{\rm dif}}(u) = 0$ and ${\mathop{\rm dif}}(v) = 0$), or by $24$ (if
	${\mathop{\rm dif}}(u) = -2$ and ${\mathop{\rm dif}}(v) = 0$, or if ${\mathop{\rm dif}}(u) = 0$ and ${\mathop{\rm dif}}(v) =
	2$), or by $30$ (if ${\mathop{\rm dif}}(u) = -2$ and ${\mathop{\rm dif}}(v) = 2$).

	As Case 2 does not apply, we know that ${\mathop{\rm dif}}(u)$ cannot be $2$ and
	${\mathop{\rm dif}}(v)$ cannot be $-2$. Hence, we have considered all the cases and for e-pairs, the charge is decreased by
	at least $18$. Altogether, the charge is decreased by at least
	$-9 + 6 + 18$, which is $15$.

	\item[IV.]
	As both $u$ and $v$ are symmetric, we have that for n-pairs the charge is increased
	by $6 \cdot 2.5$, which is $15$. For v-pairs, the charge is decreased by
	$4 + 4$, which is $8$.

	Without loss of generality, we consider only cases when ${\mathop{\rm dif}}(u) \leq {\mathop{\rm dif}}(v)$ (the other cases
	are symmetric). Thus, we may limit ourselves again to the case when the Algorithm
	chose to set
        $$A'' := A'' \cup \{u', u'', u''', u''''\} \setminus \{v', v'', v''', v''''\}.$$

	If ${\mathop{\rm dif}}(u) = {\mathop{\rm dif}}(v)$, then we easily check that the charge decrease for e-pairs
	is $8$. If ${\mathop{\rm dif}}(u) = 0$ and ${\mathop{\rm dif}}(v) = 2$ then the charge decrease for
	e-pairs is $12$. If ${\mathop{\rm dif}}(u) = -2$ and ${\mathop{\rm dif}}(v) = 0$ then the decrease is $12$,
	and if ${\mathop{\rm dif}}(u) = -2$ and ${\mathop{\rm dif}}(v) = 2$ then the decrease is $16$.

	Altogether, the charge decrease for e-pairs is at least $8$, and the
	total decrease is at least $-15 + 8 + 8$, which is $1$.
	\end{enumerate}

\item
If Case 5 applies, then all remaining broken o-vertices must be pairwise non-adjacent
(because Case~4 does not apply). Hence, there must be at most two broken o-vertices left
(otherwise, there would be a triangle in the complement of the input graph,
which would contradict the assumptions).
Further, each of these o-vertices has ${\mathop{\rm dif}} = 0$, because all its o-neighbors are
legal and Case 1 does not apply. Thus, the charge change for e-pairs due to this
last step is $0$.

To count the charge change for n-pairs and v-pairs, we analyze the five cases (one or two o-vertices, symmetric or asymmetric).
If there is one symmetric o-vertex left, then the charge increase for n-pairs is
$3 \cdot 2.5$ and the decrease for v-pairs is $4$, hence the total increase is $7.5
- 4$, which is $3.5$. If there is one asymmetric o-vertex, then the total
increase is $3\cdot 1.5 - 3$, which is $1.5$.

If there are two broken o-vertices left and both are asymmetric, then
the total increase is $6\cdot 1.5 - 6$, which is $3$. If one of them is
symmetric and the other one is asymmetric we get $5$; if both are symmetric, we
get~$7$. Altogether, we get that the charge is increased by at most 7.
\end{enumerate}

We have proved Claim~\ref{cl:decrease}. Further, by Claim~\ref{cl:upper-bound} and
Claim~\ref{cl:decrease} we have that $|E(S(G',A''))| \leq |E(S(G',A))| + 7$, and hence $A''$ is the sought legalization of
$A$.

We continue the proof of Proposition~\ref{prop:eq}.
We have already argued that a legal set $A''$ defines a subset $V_{A''}$ of $V(G)$, and hence a cut in $G$.
Assume that ${\mathop{\rm cutset}}(V_{A''})$ has $j'$ edges.
From the proof of the first implication of Proposition~\ref{prop:eq} we know that the number of edges in
$S(G',A'')$ can be expressed as $|E(G')| - 16j'$.

On the other hand, we have proved that the number of edges in $S(G',A'')$ is at most $|E(G')| - 16j + 7$. We get that
$|E(G')| - 16j'  \leq  |E(G')| - 16j + 7$, and hence $j' \geq j - 7/16$. As both $j$ and $j'$ are
integers, we have that $j' \geq j$. Hence, ${\mathop{\rm cutset}}(V_{A''})$ has at least $j$
edges, and Proposition~\ref{prop:eq} is proved
\qed\end{proof}

\begin{theorem}
\label{thm:sw-few-npc}
{\sc Switch-Few-Edges} is NP-complete.
\end{theorem}
\begin{proof}
Theorem~\ref{thm:large-deg-max-cut} in the next section gives the NP-completeness of
\textsc{Large-Deg-Max-Cut}. Further, by Proposition~\ref{prop:eq}, an instance
$(G,j)$ of \textsc{Large-Deg-Max-Cut} can be transformed into an instance
$(G',j')$ of {\sc Switch-Few-Edges} such that there is a cut in $G$ with at
least $j$ cut-edges if and only if $G'$ is $(\leq j')$-switchable. The
transformation works in polynomial time.

Finally, it is clear that the problem {\sc Switch-Few-Edges} is in NP
\qed\end{proof}

\section{The NP-Completeness of {\sc Large-Deg-Max-Cut}}\label{sec:npc-large-max-cut}

Let $G$ be a graph with $2n$ vertices. A \emph{bisection of $G$} is a partition
$S_1$, $S_2$ of $V(G)$ such that $|S_1| = |S_2| = n$ (hence, a bisection is a
special case of a cut). The size of ${\mathop{\rm cutset}}(S_1)$
is called the \emph{size} of the bisection $S_1$, $S_2$. A \emph{minimum bisection
of $G$} is a bisection of $G$ with minimum size.

Garey et al.~\cite{GJS76} proved that, given a graph $G$ and an integer $b$, the
problem to decide if $G$ has a bisection of size at most $b$ is NP-complete (by a reduction
of \textsc{Max-Cut}). Their formulation is slightly different from ours -- two distinguished
vertices must be each in one part of the partition, and the input graph does not
have to be connected. However, their reduction from \textsc{Max-Cut}
(see~\cite[pages 242--243]{GJS76}) produces only
connected graphs as instances of the bisection problem, and it is immediate that
the two distinguished vertices are not important in the proof. Hence, their
proof gives also the NP-completeness of the following version of the problem.

\vskip\fboxsep
\vskip\fboxsep
\noindent
\framebox[\hsize][l]{\begin{minipage}{\sirka}
\textsc{Connected-Min-Bisection}\\
 \textbf{Input:} A connected graph $G$ with $2n$ vertices, an integer $b$\\
 \textbf{Question:} Is there a bisection $S_1$, $S_2$ of $V(G)$ such that
${\mathop{\rm cutset}}(S_1)$ contains at most $b$ edges?
 \end{minipage}}
\vskip\fboxsep
\vskip\fboxsep

From the NP-completeness of \textsc{Min-Bisection}, Bui et al.~\cite{BCLS87}
proved the NP-completeness of \textsc{Min-Bisection} restricted to 3-regular
graphs (as a part of a more general result, see~\cite[proof of Theorem
2]{BCLS87}). We use their result to prove the NP-completeness of
\textsc{Large-Deg-Max-Cut}.

\vskip\fboxsep
\vskip\fboxsep
\noindent
\framebox[\hsize][l]{\begin{minipage}{\sirka}
\textsc{Large-Deg-Max-Cut}\\
 \textbf{Input:} A graph $G$ with $2n$ vertices such that the minimum vertex
degree of $G$ is $2n-4$ and the complement of $G$ is connected and does not contain triangles; an integer $j$\\
 \textbf{Question:} Does there exist a cut $V_1$ of $G$ with at least $j$ cut-edges?
 \end{minipage}}
\vskip\fboxsep
\vskip\fboxsep

\begin{lemma}\label{lemma:bisection}
Let $G$ be a connected 3-regular graph on $2n$ vertices. Let $b$ be the size of the minimum bisection
in $G$ and let $c$ be the size of the maximum cut in~$\overline{G}$. Then $b =
n^2 - c$.
\end{lemma}
\begin{proof}
Let $S_1$, $S_2$ be a minimum bisection in $G$ and let $b$ be the size of the bisection.
In $\overline{G}$, the partition $S_1$, $S_2$ yields a cut with $n^2 - b$ cut-edges.
Hence, $c \geq n^2 - b$.

On the other hand, let $V_1$, $V_2$ be a maximum cut in $\overline{G}$ for which the sizes of $V_1$ and $V_2$ are
as close as possible. If $|V_1| = |V_2| = n$, the partition $|V_1|$, $|V_2|$ gives
a bisection in $G$ of size $n^2 - c$, hence $b \leq n^2 - c$ and we are done.

Otherwise, assume that $|V_1| = n - k$ and $|V_2| = n+k$ for a $k \geq 1$. As the graph $G$ is connected, there is a vertex
$v$ in $V_2$ that has at least one neighbor in $V_1$. We set $V_1' = V_1 \cup \{v\}$ and $V_2' = V_2 \setminus \{v\}$.

The vertex $v$ has at least one neighbor in $V_1$. Hence, in $G$, there is at least one edge between
$v$ and $V_1$, and in $\overline{G}$, there are at most $n-k-1$ cut-edges adjacent to $v$.

Further, $v$ has at most two neighbors in $V_2$ and at least $n+k-3$ non-neighbors in $V_2$.
Hence, in the partition  $V_1'$, $V_2'$, there will be at least $n + k - 3$ cut-edges adjacent to $v$.
Cut edges that are not adjacent to $v$ are the same in $V_1$, $V_2$ as in $V_1'$, $V_2'$.

Altogether, $|{\mathop{\rm cutset}}(V_1')| - |{\mathop{\rm cutset}}(V_1)| \geq n+ k - 3 - (n-k-1) \geq 2k-2 \geq 0$.
Hence, the partition $V_1'$, $V_2'$ has smaller difference of the sizes of the two parts while the size of the
cut is not smaller, which is a contradiction with the choice of $V_1$,
$V_2$.\qed
\end{proof}

\begin{theorem}\label{thm:large-deg-max-cut}
\textsc{Large-Deg-Max-Cut} is NP-complete.
\end{theorem}
\begin{proof}
Let $(G,b)$ be an instance of \textsc{Connected-Min-Bisection}. We use the construction
of Bui et al.~\cite[proof of Theorem 2]{BCLS87}. Their first step is to construct from
an instance $(G,b)$ of \textsc{Min-Bisection} a 3-regular graph
$G^*$ such that $G$ has a minimum bisection of size $b$ if and only if $G^*$ has
a minimum bisection of size $b$. Further, it is immediate from their construction that $G^*$
contains no triangles, and if $G$ is connected, then $G^*$ is connected as well.
Moreover, $G^*$ has an even number of vertices.

We see that $\overline{G^*}$ fulfills the conditions of an instance of
\textsc{Large-Deg-Max-Cut}. By Lemma~\ref{lemma:bisection} we know that $G^*$
has a minimum bisection of size $b$ if and only if $\overline{G^*}$ has a maximum
cut of size $m^2 - b$.

Altogether, $G$ has a minimum bisection of size $b$ if and only if
$\overline{G^*}$ has a maximum cut of size $m^2 - b$. Hence, $(\overline{G^*},
m^2 - b)$ is an equivalent instance of \textsc{Large-Deg-Max-Cut}.
To finish the proof that \textsc{Large-Deg-Max-Cut} is NP-complete, we observe that
\textsc{Large-Deg-Max-Cut} is in NP.
\qed\end{proof}

\section{Switching of Graphs with Bounded Density}

The \emph{density} of a graph $G$ is defined as
\begin{displaymath}
D(G) = \frac{|E(G)|}{\binom{|V(G)|}{2}} =
\frac{2|E(G)|}{|V(G)|(|V(G)|-1)}.
\end{displaymath}

In connection with properties of simplicial complexes, Matou\v sek and Wagner~\cite{MW14}
asked if deciding switching-minimality was easy for graphs of bounded density. We give a partial negative answer
by proving that the problem \textsc{Switch-Few-Edges} stays NP-complete
even for graphs of density bounded by an arbitrarily small constant. This is in
contrast with Proposition~\ref{prop:maxdeg}, which shows that any graph $G$ with
maximum degree at most $|V(G)|/4$ is switching-minimal. The core of our
argument is the following Proposition.

\begin{proposition}\label{proposition:graphbc}
Let $G$ be a graph, let $k$ be an integer, and let $c$ be a fixed constant in
$(0,1)$. In polynomial time, we can find a graph $G'$ and an integer $k'$ such
that
\begin{enumerate}
\item\label{cond:dens} $D(G') \leq c$,
\item\label{cond:sw}   $G'$ is $(\leq k')$-switchable if and only if $G$ is $(\leq k)$-switchable,
\item\label{cond:min}   $G'$ is switching-minimal if and only if $G$ is
switching-minimal, and
\item\label{cond:size} $|V(G')| = O({|V(G)|})$.
\end{enumerate}
\end{proposition}

\begin{proof}
Let $n = |V(G)|$ and let
$N=\max\left\{n,\left\lceil\frac{3n}{4c}\right\rceil\right\}$. We construct the
graph $G'$ in the following way (see also Fig.~\ref{figure:graphbc-construct}).
Let $V=V(G)$. Then
\begin{displaymath}
V(G') = V \cup Y \cup Z,
\end{displaymath}
where $Y$ is a set of $N$ vertices and $Z$ is a set of $N$ more vertices, and
\begin{displaymath}
E(G') = \{ \{v_1,v_2\}\colon v_1 \in Y, v_2 \in V \} \cup E(G).
\end{displaymath}

\begin{figure}
\centering
\includegraphics{graphbc-construct}
\caption{The graph $G'$.\label{figure:graphbc-construct}}
\end{figure}

We prove that $G'$ fulfills the conditions of
Proposition~\ref{proposition:graphbc}. It is easy to see
that Condition~\ref{cond:size} holds and that $G'$ can be obtained in
polynomial time.
We prove that Conditions~\ref{cond:sw} and~\ref{cond:min} hold, too.

Assume that $G$ is switching-reducible, i.~e., there exists a set $A\subseteq V$
such that $S(G,A)$ contains fewer edges than~$G$. Let us count the number of
edges in $S(G',A)$.

It is easy to see that if we switch a subset of $V$ in $G'$, the number of
edges whose one endpoint is outside $V$ is unchanged, and the number of edges
with both endpoints outside $V$ remains zero.
We also observe that $S(G',A)[V]$ (the induced subgraph of $S(G',A)$ on the vertex subset $V$) is equal to $S(G,A)$. Hence, $S(G',A)$ has fewer
edges than $G'$, showing that $G'$ is switching-reducible.

Moreover, if $S(G,A)$ has $l$ edges for an integer $l$, then $S(G',A)$ has $l + nN$ edges. Thus, if
$G$ is $(\leq k)$-switchable, we have that $G'$ is $(\leq k+nN)$-switchable.

Now assume that $G'$ is switching-reducible, i.~e., there exists a set
$A\subseteq V(G')$ such that $S(G',A)$ has fewer edges than $G'$. If
$A\subseteq V$, we have that $S(G,A)$ has fewer edges than $G$, and Condition
\ref{cond:min} is satisfied. On the other hand, if $A \not\subseteq V$, we use
the following Claim.

\begin{claimm}\label{claim:dobrehran}
Let $A$ be a subset of $V(G')$ and let $A' = A\cap V$. Then the number of edges in $S(G',A')$ is less than or equal to
the number of edges in $S(G',A)$.
\end{claimm}
To prove the claim, we fix a set $A\subseteq V(G')$. We may assume that $|A\cap
(Y\cup Z)| \le |Y\cup Z|/2=N$, otherwise we replace $A$ by its complement
$\overline{A}=V(G')\setminus A$ (note that $S(G',A\cap V)$ has the same number
of edges as $S(G',\overline{A}\cap V)$).

Define the sets $A'=A\cap V$ and $A''=A\setminus A' =A \cap(Y\cup Z)$. Let
$G'_1= S(G',A')$ and $G'_2=S(G',A)$. Note that $G'_2=S(G'_1,A'')$. To prove the
claim, we need to show that $G'_1$ has at most as many edges as $G'_2$.

In $G'_2$, every vertex of $A''$ is adjacent to every vertex of
$(Y\cup Z)\setminus A''$, whereas no such pair is adjacent in $G'_1$. This
means that $|E(G'_2)\setminus E(G'_1)|\ge |A''|(|Y|+|Z|-|A''|) \ge |A''|N$,
where we used the fact that $A''$ has size at most $N$.

On the other hand, an edge belonging to $G'_1$ but not to $G'_2$ must
necessarily connect a vertex from $A''$ with a vertex from $V$. Therefore,
$|E(G'_1)\setminus E(G'_2)|\le |A''|n$. Combining these estimates, we get
\begin{align*}
 |E(G'_2)| - |E(G'_1)| &= |E(G'_2)\setminus E(G'_1)| - |E(G'_1)\setminus
E(G'_2)|\\
&\ge |A''|N - |A''|n\\
&\ge 0.
\end{align*}
This proves the claim.
As a consequence of Claim~\ref{claim:dobrehran}, if $G'$ is switching-reducible,
then it can be reduced by switching a set $A'\subseteq V$. The same set $A'$
then reduces $G$, and Condition~\ref{cond:min} of the Proposition holds.
Analogically, if $G'$ can be switched to contain $L$ edges for an integer $L$,
then $G$ can be switched to contain $L - nN$ edges. Hence, we have proved Condition~\ref{cond:sw}
with $k' = k + nN$.

It remains to check Condition~\ref{cond:dens}. By definition, the density of
$G'$ is

\begin{align*}
D(G') &= \frac{ 2|E(G')|}{(2N+n)(2N+n-1)}\\ &\le \frac{2\left(\binom{n}{2} + nN\right)}{(2N+n)(2N+n-1)}\\
&\le \frac{n^2+ 2nN}{4N^2}\\ &\le \frac{3nN}{4N^2}= \frac{3n}{4N}\\ &\le c.
\end{align*}
This completes the proof
\qed\end{proof}

Proposition~\ref{proposition:graphbc} allows us to state a stronger version of Theorem~\ref{thm:sw-few-npc}
for the special case of graphs with bounded density.

\begin{theorem}\label{theorem:npc-c}
For every $c>0$, the problem \textsc{Switch-Few-Edges} is NP-complete for graphs
of density at most $c$.
\end{theorem}
\begin{proof}
As shown by Proposition~\ref{proposition:graphbc}, a general instance $(G,k)$ of
\textsc{Switch-Few-Edges} can be transformed into an equivalent instance $(G',k')$ of
density at most~$c$. Since \textsc{Switch-Few-Edges} is NP-complete on general
instances by Theorem~\ref{thm:sw-few-npc}, it remains NP-complete on instances
of density at most~$c$
\qed\end{proof}

\section{Concluding Remarks}

{\bf 5.1.}
We have been trying to prove that the problem \textsc{Switch-Reducible} is NP-complete (and hence,
\textsc{Switch-Minimal} is co-NP-complete). We have not yet succeeded. However,
if it is true, then Proposition~\ref{proposition:graphbc} gives the following analogue of Theorem~\ref{theorem:npc-c}
even for these problems.

\begin{proposition}\label{theorem:swred-npc-c}
If the problem \textsc{Switch-Reducible} is NP-complete, then for every $c>0$,
the problem \textsc{Switch-Reducible} is NP-complete for graphs
of density at most $c$, and the problem \textsc{Switch-Minimal} is
co-NP-complete for graphs of density at most $c$.
\end{proposition}

\medskip\noindent
{\bf 5.2.} Lindzey~\cite{Lindzey14}
noticed that it is possible to speed-up several graph algorithms using
switching to a lower number of edges -- he obtained up to super-polylogarithmic
speed-ups of algorithms for diameter, transitive closure, bipartite maximum
matching and general maximum matching. However, he focuses on switching digraphs
(with a definition somewhat
different to Seidel's switching in undirected graphs),
 where the situation is in
sharp contrast with our results -- a digraph with the minimum number of edges in
its switching-class can be found in $O(n+m)$ time.

\medskip\noindent
{\bf 5.3.} It has been observed before (cf. e.g. \cite{EHHR00-issues}) that for a graph property $\cal P$, the complexity of deciding $\cal P$ is independent on the complexity of deciding if an input graph can be switched to a graph possessing the property $\cal P$. Switching to few edges thus adds another example of a polynomially decidable property (counting the edges is easy) whose switching version is hard. Previously known cases are the NP-hardness of  deciding switching-equivalence to a regular graph
\cite{Kratochvil03} and deciding switching-equivalence to an $H$-free graph for certain specific graphs $H$~\cite{JK14-hfree}.

\medskip\noindent
{\bf 5.4.}
Let $d>0$ be a constant. What can we say about the complexity of
\textsc{Switch-Reducible} and \textsc{Switch-Few-Edges} on graphs of maximum
degree at most~$dn$? If $d\le\frac 1 4$, the two problems are trivial by
Proposition~\ref{prop:maxdeg}. On the other hand, for $d\ge \frac 1 2$ the
restriction on maximum degree becomes irrelevant, since any switching-minimal
graph has maximum degree at most $\frac n 2$ by Proposition~\ref{pro:pul}. For
any $d\in(\frac 1 4,\frac 1 2)$, the complexity of the two problems on instances
of maximum degree at most $dn$ is open.

\bibliographystyle{plain}


\section{Introduction}
\label{sec:intro}

Speech recognition is a typical sequence to sequence transduction problem, i.e., given a sequence of acoustic observations, the speech recognition engine decodes the corresponding sequence of words or phonemes. A key component in a speech recognition system is the acoustic model, which computes the conditional probability of the output sequence given the input sequence. However, directly computing this conditional probability is challenging due to many factors including the variable lengths of the input and output sequences. The hidden Markov model (HMM) converts this sequence-level classification task into a frame-level classification problem, where each acoustic frame is classified into one of the hidden states, and each output sequence corresponds to a sequence of hidden states. To make it computationally tractable, HMMs usually rely on the conditional independence assumption and the first-order Markov rule --- the well-known weaknesses of HMMs~\cite{gillick2011don}. Furthermore, the HMM-based pipeline is composed of a few relatively independent modules, which makes the joint optimisation nontrivial.

There has been a consistent research effort to seek architectures to replace HMMs and overcome their limitation for acoustic modelling, e.g., ~\cite{ostendorf1996,smith2001speech, gunawardana2005hidden, hifny2009speech}; however these approaches have not yet improved speech recognition accuracy over HMMs. In the past few years, several neural network based approaches have been proposed and demonstrated promising results. In particular, the connectionist temporal classification (CTC) ~\cite{graves2014towards, Hannun2014Deep, sak2015fast, miao2015eesen} approach defines the loss function directly to maximise the conditional probability of the output sequence given the input sequence, and it usually uses a recurrent neural network to extract features. However, CTC simplifies the sequence-level error function by a product of the frame-level error functions (i.e., independence assumption), which means it essentially still does frame-level classification. It also requires the lengths of the input and output sequence to be the same, which is inappropriate for speech recognition. CTC deals with this problem by replicating the output labels so that a consecutive frames may correspond to the same output label or a {\it blank} token.

Attention-based RNNs have been demonstrated to be a powerful alternative sequence-to-sequence transducer, e.g., in machine translation ~\cite{bahdanau2014neural}, and speech recognition ~\cite{chorowski2015attention, lu2015study, chan2015listen}. A key difference of this model from HMMs and CTCs is that the attention-based approach does not apply the conditional independence assumption to the input sequence. Instead, it maps the variable-length input sequence into a fixed-size vector representation at each decoding step by an attention-based scheme (see ~\cite{bahdanau2014neural} for further explanation). It then generates the output sequence using an RNN conditioned on the vector representation from the source sequence. The attentive scheme suits the machine translation task well, because there may be no clear alignment between the source and target sequence for many language pairs. However, this approach does not naturally apply to the speech recognition task, as each output token only corresponds to a small size window of acoustic spectrum.

In this paper, we study segmental RNNs~\cite{kong2015segmental} for acoustic modelling. This model is similar to CTC and attention-based RNN in the sense that an RNN encoder is also used for feature extraction, but it differs in the sense that the sequence-level conditional probability is defined using an segmental (semi-Markov) CRF~\cite{sarawagi2004semi}, which is an extension on the standard CRF~\cite{lafferty2001conditional}. There have been numerous works on CRFs and their variants for speech recognition, e.g, ~\cite{gunawardana2005hidden, hifny2009speech, zweig2011speech} (see \cite{fosler2013conditional} for an overview). In particular, feed-forward neural networks have been used with segmental CRFs for speech recognition~\cite{abdel2013deep, he2015segmental}. However, segmental RNNs are different in that they are end-to-end models --- they do not depend on external systems to provide segmentation boundaries and features, instead, they are trained by marginalising out all possible segmentations, while the features are derived from the encoder RNNs, which are trained jointly with the segmental CRFs. Our experiments were performed on the TIMIT dataset, and we achieved 17.3\% PER from first-pass decoding with zeroth-order CRF and without using any language model --- the best reported result using CRFs.

\section{Segmental Recurrent Neural Networks}

\subsection{Segmental Conditional Random Fields}

Given a sequence of acoustic frames $\mathbf{X} = \{\mathbf{x}_1, \cdots, \mathbf{x}_T\}$ and its corresponding sequence of output labels $\mathbf{y} = \{y_1, \cdots, y_J\}$, where $T\ge J$, segmental (or semi-Markov) conditional random field defines the sequence-level conditional probability with the auxiliary segment labels $\mathbf{E} = \{\mathbf{e}_1, \cdots, \mathbf{e}_J\}$ as
\begin{align}
\label{eq:crf}
P(\mathbf{y}, \mathbf{E} \mid \mathbf{X}) = \frac{1}{Z(\mathbf{X})} \prod_{j=1}^J \exp f \left( y_j, \mathbf{e}_j, \mathbf{X} \right),
\end{align}
where $\mathbf{e}_j = \langle s_{j}, n_{j} \rangle$ is a tuple of the beginning ($s_{j}$) and the end ($n_{j}$) time tag for the segment of $y_j$, and $n_j > s_j $ while $n_j, s_j \in [1, T]$; $y_j \in \mathcal{Y}$ and $\mathcal{Y}$ denotes the vocabulary set; $Z(\mathbf{X})$ is the normaliser that that sums over all the possible $(\mathbf{y, E})$ pairs, i.e.,
\begin{align}
Z(\mathbf{X}) = \sum_{\mathbf{y,E}} \prod_{j=1}^J \exp f \left( y_j, \mathbf{e}_j, \mathbf{X} \right).
\end{align}
Here, we only consider the zeroth-order CRF, while the extension to higher order models is straightforward. Similar to other CRF-based models, the function $f(\cdot)$ is defined as
\begin{align}
\label{eq:phi}
f \left( y_j, \mathbf{e}_j, \mathbf{X} \right) = \mathbf{w}^\top \Phi (y_j, \mathbf{e}_j, \mathbf{X}),
\end{align}
where $\Phi(\cdot)$ denotes the feature function, and $\mathbf{w}$ is the weight vector. Previous works on CRF-based acoustic models mainly use heuristically handcrafted feature function $\Phi(\cdot)$. They also usually rely on an external system to provide the segment labels. In this paper, we define $\Phi(\cdot)$ using neural networks, and the segmentation $\mathbf{E}$ is marginalised out during training, which makes our model self-contained.

\subsection{Feature Representations}

We use neural networks to define the feature function $\Phi(\cdot)$, which maps the acoustic segment and its corresponding label into a joint feature space. More specifically, $y_j$ is firstly represented as a one-hot vector $\mathbf{v}_j$, and it is then mapped into a continuous space by a linear embedding matrix $\mathbf{M}$ as
\begin{align}
\mathbf{u}_j = \mathbf{Mv}_j
\end{align}
Given the segment label $\mathbf{e}_j$, we use an RNN to map the acoustic segment to a fixed-dimensional vector representation,  i.e.,
\begin{align}
&\mathbf{h}_{1}^j =   r(\mathbf{h}_0, \mathbf{x}_{s_j}) \\
&\mathbf{h}_{2}^j =  r(\mathbf{h}_1^j, \mathbf{x}_{s_j + 1}) \\
& \quad \vdots \nonumber \\
\label{eq:emb}
&\mathbf{h}_{d_j}^j   =  r(\mathbf{h}_{d_j -1}^j, \mathbf{x}_{n_{j}})
\end{align}
where $\mathbf{h}_0$ denotes the initial hidden state, $d_j = n_{j} - s_{j}$ denotes the duration of the segment and $r(\cdot)$ is a non-linear function. We take the final hidden state $\mathbf{h}_{d_j}^j$ as the segment embedding vector, then $\Phi(\cdot)$ can be represented as
\begin{align}
\Phi(y_j, \mathbf{e}_j, \mathbf{X}) = g(\mathbf{u}_j, \mathbf{h}_{d_j}^j),
\end{align}
where $g(\cdot)$ corresponds to one layer or multiple layers of linear or non-linear transformation. In fact, it is flexible to include other relevant features as additional inputs to the function $g(\cdot)$, e.g., the duration feature which can be obtained by converting $d_j$ into another embedding vector. In practice, multiple RNN layers can be used transform the acoustic signal $\mathbf{X}$ before extracting the segment embedding vector $\mathbf{h}_{d_j}^j$ as Figure \ref{fig:segrnn}.

\begin{figure}[t]
\small
\centerline{\includegraphics[width=0.45\textwidth]{segrnn}} \vskip -4mm
\caption{Segmental RNN using a first-order CRF. The coloured circles denote the segment embedding vector $\mathbf{h}_{d_j}^j$ in Eq.\eqref{eq:emb}. Using bi-directional RNNs is straightforward. }
\label{fig:segrnn}
\vskip -5mm
\end{figure}

\subsection{Conditional Maximum Likelihood Training}

For speech recognition, the segmentation labels $\mathbf{E}$ are usually unknown,  training the model by maximising the conditional probability as Eq. \eqref{eq:crf} is therefore not practical. The problem can be addressed by defining the loss function as the negative marginal log-likelihood as
\begin{align}
\mathcal{L}(\theta) &= - \log P(\mathbf{y} \mid \mathbf{X}) \nonumber \\
 &= - \log \sum_{\mathbf{E}} P(\mathbf{y, E} \mid \mathbf{X}) \nonumber \\
&= - \log \underbrace{\sum_{\mathbf{E}} \prod_j \exp f \left( y_j, \mathbf{e}_j, \mathbf{X} \right)}_{\equiv Z(\mathbf{X}, \mathbf{y})} + \log Z(\mathbf{X}),
\end{align}
where $\theta$ denotes the set of model parameters, and $Z(\mathbf{X}, \mathbf{y})$ denotes the summation over all the possible segmentations when only $\mathbf{y}$ is observed. To simplify notations, the objective function $\mathcal{L}(\theta)$ is define with only one training utterance.

However, the number of possible segmentations is exponential with the length of $\mathbf{X}$, which makes the naive computation of both $Z(\mathbf{X}, \mathbf{y})$ and $Z(\mathbf{X})$ impractical. Fortunately, this can be addressed by using the following dynamic programming algorithm as proposed in~\cite{sarawagi2004semi}:
\begin{align}
\alpha_0 &= 1 \\
\label{eq:alpha}
\alpha_{t} & = \sum_{0<k<t} \alpha_{k} \times \sum_{y\in \mathcal{Y}} f(y, \langle k, t \rangle, \mathbf{X}) \\
Z(\mathbf{X}) & = \alpha_T
\end{align}
In Eq. \eqref{eq:alpha}, the first summation is over all the possible segmentation up to timestep $t$, and the second summation is over all the possible labels from the vocabulary. The computation cost of this algorithm is $O(T^2\cdot |\mathcal{Y}|)$, where $|\mathcal{Y}|$ is the size of the vocabulary. The cost can be further reduced by introducing an upper bound of  the segment length, in which case Eq. \eqref{eq:alpha} can be rewritten as
\begin{align}
\label{eq:alpha2}
\alpha_{t} & = \sum_{l<k<t} \alpha_{k} \times \sum_{y\in \mathcal{Y}} f(y, \langle k, t \rangle, \mathbf{X}) \\
\label{eq:seglen}
l & = \left \{ \begin{array}{l}
0 \qquad \quad \text{if} \quad t - L < 0 \\
t - L \qquad \text{otherwise} \\
\end{array}
\right .
\end{align}
where $L$ denotes the maximum value of the segment length. The cost is then reduced to $O(L\cdot T\cdot |\mathcal{Y}|)$, and for long sequences like speech signals where $T \gg L$, the computational savings are substantial.

The term $Z(\mathbf{X}, \mathbf{y})$ can be computed similarly. In this case, since the label $\mathbf{y}$ is now observed, the summation over all the possible labels $y \in \mathcal{Y}$ in Eq. \eqref{eq:alpha} is not necessary, i.e.,
\begin{align}
\beta_{0,0} &= 1 \\
\label{eq:beta}
\beta_{t,j} & = \sum_{0<k<t} \beta_{k,j-1} \times  f(y_j, \langle k, t \rangle, \mathbf{X}) \\
Z(\mathbf{X}, \mathbf{y}) & = \beta_{T,J}
\end{align}
Again, we can limit the length of the possible segments as Eq. \eqref{eq:alpha2}. Given $Z(\mathbf{X})$ and $Z(\mathbf{X}, \mathbf{y})$, the loss function $\mathcal{L}(\theta)$ can be minimised using the stochastic gradient decent (SGD) algorithm similar to training other neural network models. Other losses, for example, hinge, can be considered in future work.

\begin{figure}[t]
\small
\centerline{\includegraphics[width=0.3\textwidth]{subsample}} \vskip -4mm
\caption{ Hierarchical subsampling recurrent network~\cite{graves2012hierarchical} . The size of the subsampling window is two in this example.  }
\label{fig:hsrnn}
\vskip -5mm
\end{figure}

\subsection{Viterbi Decoding}

During decoding, we need to search the target label sequence $\mathbf{y}$ that yields the highest posterior probability given $\mathbf{X}$ by marginalising out all the possible segmentations:
\begin{align}
\mathbf{y}^* = \arg\max_{\mathbf{y}} \log \sum_{\mathbf{E}} P(\mathbf{y}, \mathbf{E} \mid \mathbf{X})
\end{align}
This involves minor modification of the recursive algorithm in Eq. \eqref{eq:alpha} that instead of summing over all the possible labels, the Viterbi path up to the timestep $t$ is
\begin{align}
\alpha_{t}^* & = \sum_{0<k<t} \alpha_{k}^* \times \max_{y\in \mathcal{Y}} f(y, \langle k, t \rangle, \mathbf{X})
\end{align}
However, marginalising out all the possible segmentations is still expensive. The computational cost can be further reduced by greedy searching the most likely segmentation,  i.e.,
\begin{align}
\alpha_{t}^* & = \max_{0<k<t} \alpha_{k}^* \times \max_{y\in \mathcal{Y}} f(y, \langle k, t \rangle, \mathbf{X}),
\end{align}
which corresponds to the decoding objective as
\begin{align}
\mathbf{y}^*, \mathbf{E}^*= \arg\max_{\mathbf{y, E}} \log P(\mathbf{y}, \mathbf{E} \mid \mathbf{X})
\end{align}
This joint maximization algorithm may yield high search error, because it only considers one segmentation.  In the future, we shall investigate the beam search algorithm which may yield a lower search error.

\subsection{Further Speedup}
\label{sec:subsample}

It is computationally expensive for RNNs to model long sequences, and the number of possible segmentations is exponential with the length of the input sequence as mentioned before. The computational cost can be significantly reduced by using the hierarchical subsampling RNN~\cite{graves2012hierarchical} to shorten the input sequences, where the subsampling layer takes a window of hidden states from the lower layer as input as shown in Figure \ref{fig:hsrnn}.  In this work, we consider three variants: a) {\it concatenate} -- the hidden states in the subsampling window are concatenated before been fed into the next layer; b) {\it add} -- the hidden states are added into one vector for the next layer; c) {\it skip} -- only the last hidden state in the window is kept and all the others are skipped. The last two schemes are computationally cheaper as they do not introduce extra model parameters.

\section{Experiments}
\label{sec:exp}

 \begin{table}
 \centering \small
\caption{Speedup by hierarchical subsampling networks. }\vskip 1.5mm

\label{tab:speedup}
\begin{tabular}{l|cc}
\hline

\hline
subsampling   & $L$ &  speedup  \\ \hline
No & 30  & 1 \\
1 layer & 15   & $\sim$3x\\
2 layers & 8 & $\sim$10x \\

\hline

\hline
\end{tabular}
\vskip-4mm
\end{table}

 \begin{table}
 \centering \small
\caption{Results of hierarchical subsampling networks. $d(\mathbf{w})$ and $d(\mathbf{h}_j)$ denote the dimension of $\mathbf{w}$ and $\mathbf{h}_{d_j}^j$ in Eqs. \eqref{eq:phi} and \eqref{eq:emb} respectively. {\tt layers} denotes the number of LSTM layers and {\tt hidden} is the dimension of the LSTM  cells. We reduced the dimension of $\mathbf{h}_{d_j}^j$ from the LSTM output for computational reasons. {\tt conc} is short for the concatenating operation. }\vskip 1.5mm

\label{tab:hsrnn}
\begin{tabular}{l|ccccc}
\hline

\hline
System  & $d(\mathbf{w}$) & $d(\mathbf{h}_{d_j}^j)$ & layers & hidden &  PER(\%) \\ \hline
{\tt skip} & 64 & 64 & 3 & 128 & 21.2 \\
{\tt conc} & 64 & 64 & 3 & 128  & 21.3 \\
{\tt add}  & 64 & 64 & 3 & 128  & 23.2 \\ \hline
{\tt skip} & 64 & 64 & 3 & 250 & 20.1 \\
{\tt conc} & 64 & 64 & 3 & 250 & 20.5 \\
{\tt add} & 64 & 64 & 3 & 250 & 21.5  \\

\hline

\hline
\end{tabular}
\vskip-5mm
\end{table}

\subsection{System Setup}

We used the TIMIT dataset to evaluate the segmental RNN acoustic models. This dataset was preferred for the rapid evaluation of different system settings, and for the comparison to other CRF and end-to-end systems. We followed the standard protocol of the TIMIT dataset, and our experiments were based on the Kaldi recipe~\cite{povey2011kaldi}. We used the core test set as our evaluation set, which has 192 utterances. We used 24 dimensional log fiterbanks (FBANKs) with delta and double-delta coefficients, yielding 72 dimensional feature vectors. Our models were trained with 48 phonemes, and their predictions were converted to 39 phonemes before scoring. The dimension of $\mathbf{u}_j$ was fixed to be 32. For all our experiments, we used the long short-term memory (LSTM) networks~\cite{hochreiter1997long} as the implementation of RNNs, and the networks were always bi-directional. We set the initial SGD learning rate to be 0.1, and we exponentially decay the learning rate by a factor of 2 when the validation error stopped decreasing. Our models were trained with dropout regularisation~\cite{srivastava2014dropout}, using an specific implementation for recurrent networks~\cite{zaremba2014recurrent}. The dropout rate was 0.2 unless specified otherwise. Our models were randomly initialised with the same random seed.

\subsection{Results of Hierarchical Subsampling}

We first demonstrate the results of the hierarchical subsampling recurrent network, which is the key to speed up our experiments. We set the size of the subsampling window to be 2, therefore each subsampling layer reduced the time resolution by a factor of 2. We set the maximum segment length $L$ in Eq. \eqref{eq:seglen} to be 300 milliseconds, which corresponded to 30 frames of FBANKs (sampled at the rate of 10 milliseconds).  With two layers of subsampling recurrent networks, the time resolution was reduced by a factor of 4, and the value of $L$ was reduced to be 8, yielding around 10 times speedup as shown in Table \ref{tab:speedup}.

Table \ref{tab:hsrnn} compares the three implementations of the recurrent subsampling network detailed in section \ref{sec:subsample}. We observed that concatenating all the hidden states in the subsampling window did not yield lower phone error rate (PER) than using the simple {\it skipping} approach, which may be due to the fact that the TIMIT dataset is small and it prefers a smaller model. On the other hand, adding the hidden states in the subsampling window together worked even worse, possibly due to that the sequential information in the subsampling window was flattened. In the following experiments, we sticked to the {\it skipping} method, and using two subsampling layers.

 \begin{table}
 \centering \small
\caption{Results of tuning the hyperparameters. }\vskip 1.5mm
\label{tab:tune}
\begin{tabular}{c|cccccc}
\hline

\hline
Dropout  & $d(\mathbf{w}$) & $d(\mathbf{h}_{d_j}^j)$ & layers & hidden & PER  \\ \hline
 & 64 & 64 & 3 & 128  & 21.2 \\
& 64 & 32 & 3 & 128 & 21.6 \\
 & 32 & 32 & 3 & 128  & 21.4 \\ \cline{2-6}
  & 64 & 64 & 3 & 250 & 20.1 \\
 0.2 & 64 & 32 & 3 & 250 & 20.4 \\
 & 32 & 32 & 3 & 250 & 20.6 \\ \cline{2-6}
 & 64 & 64 & 6 & 250 & 19.3 \\
 & 64 & 32 & 6 & 250 & 20.2  \\
 & 32 & 32 & 6 & 250 & 20.2 \\ \hline
 & 64 & 64 & 3 & 128 & 21.3 \\
0.1 & 64 & 64 & 3 & 250 & 20.9 \\
 & 64 & 64 & 6 & 250 & 20.4 \\ \hline
$\times$  & 64 & 64 & 6 & 250 & 21.9 \\
\hline

\hline
\end{tabular}
\vskip-4mm
\end{table}

\begin{table}
 \centering \small
\caption{Results of three types of acoustic features. }\vskip 1.5mm
\label{tab:feautre}
\begin{tabular}{l|cccccc}
\hline

\hline
Features  & Deltas & $d(\mathbf{x}_t)$ & PER  \\ \hline
 24-dim FBANK & $\surd$ & 72 & 19.3 \\
 40-dim FBANK & $\surd$ & 120 & 18.9 \\
 Kaldi & $\times$ & 40 &  17.3 \\
 \hline

\hline
\end{tabular}
\vskip-5mm
\end{table}

\subsection{Hyperparameters and Different Features}

We then evaluated the model by tuning the hyperparameters, and the results are given in Table \ref{tab:tune}. We tuned the number of LSTM layers, and the dimension of LSTM cells, as well as the dimensions of $\mathbf{w}$ and the segment vector $\mathbf{h}_{d_j}^j$. In general, larger models with dropout regularisation yielded higher recognition accuracy. Our best result was obtained using 6 layers of 250-dimensional LSTMs. However, without the dropout regularisation, the model can be easily overfit due to the small size of training set. In the future, we shall evaluate this model with a large dataset.

We then evaluated another two types of features using the same system configuration that achieved the best result in Table \ref{tab:tune}. We increased the number of FBANKs from 24 to 40, which yielded slightly lower PER. We also evaluated the standard Kaldi features --- 39 dimensional MFCCs spliced by a context window of 7, followed by LDA and MLLT transform and with feature-space speaker-dependent MLLR, which were the same features used in the HMM-DNN baseline in Table \ref{tab:compare}. The well-engineered features improved the accuracy of our system by more than 1\% absolute.

 \begin{table}
 \centering \small
\caption{Comparison to Related Works. {\tt LM} denotes the language model, and {\tt SD} denotes speaker-dependent transform. The HMM-DNN baseline was trained with cross-entropy using the Kaldi recipe. Sequence training did not improve it due to the small amount of data. Note that RNN transducer and attention-based RNN are equipped with built-in RNNLMs.}\vskip 1.5mm

\label{tab:compare}
\begin{tabular}{l|ccc}
\hline

\hline
System  & LM & SD & PER  \\ \hline
HMM-DNN & $\surd$ & $\surd$  & 18.5 \\
first-pass SCRF~\cite{zweig2012classification} & $\surd$ & $\times$ & 33.1  \\
Boundary-factored SCRF~\cite{he2012efficient} & $\times$  & $\times$ & 26.5 \\
Deep Segmental NN~\cite{abdel2013deep} & $\surd$ & $\times$ & 21.9 \\
Discriminative segmental cascade~\cite{tang2015discriminative} & $\surd$ & $\times$ & 21.7 \\
$\quad$ + 2nd pass with various features & $\surd$ & $\times$ & 19.9 \\ \hline
CTC~\cite{graves2013speech} & $\times$ & $\times$ & 18.4 \\
RNN transducer~\cite{graves2013speech} & -- & $\times$ & 17.7 \\
Attention-based RNN~\cite{chorowski2015attention} & -- & $\times$ & 17.6 \\

Segmental RNN &$\times$ & $\times$ & 18.9 \\
Segmental RNN &$\times$ & $\surd$ & 17.3 \\

\hline

\hline
\end{tabular}
\vskip-4mm
\end{table}

\subsection{Comparison to Related Works }

In Table \ref{tab:compare}, we compare our result to other reported results using segmental CRFs as well as recent end-to-end systems. Previous state-of-the-art result using segmental CRFs on the TIMIT dataset is reported in~\cite{tang2015discriminative}, where the first-pass decoding was used to prune the search space, and the second-pass was used to re-score the hypothesis using various features including neural network features. Besides, the ground-truth segmentation was used in~\cite{tang2015discriminative}. We achieved considerably lower PER with first-pass decoding, despite the fact that our CRF was zeroth-order, and we did not use any language model. Furthermore, our results are also comparable to that from the CTC and attention-based RNN end-to-end systems. The accuracy of segmental RNNs may be further improved by using higher-order CRFs or incorporating a language model into the decode step, and using beam search to reduce the search error.

\section{Conclusions}
In this paper, we present the segmental RNN --- a novel acoustic model that combines the segmental CRF with an encoder RNN for end-to-end speech recognition. We discuss the practical training and decoding algorithms of this model for speech recognition, and the subsampling network to reduce the computational cost. Our experiments were performed on the TIMIT dataset, and we achieved strong recognition accuracy using zeroth-order CRF, and without using any language model. In the future, we shall investigate discriminative training criteria, and incorporating a language model into the decoding step. Future works also include implementing a weighted finite sate transducer (WFST) based decoder and scaling this model to large vocabulary datasets.

\newpage
\small
\bibliographystyle{IEEEtran}