# Fast Biclustering by Dual Parameterization

Pål Grønås Drange  Felix Reidl  Fernando Sánchez Villaamil  Somnath Sikdar

###### Abstract

We study two clustering problems, Starforest Editing, the problem of adding
and deleting edges to obtain a disjoint union of stars, and the generalization
Bicluster Editing. We show that, in addition to being NP-hard, none of the
problems can be solved in subexponential time unless the exponential time
hypothesis fails.

Misra, Panolan, and Saurabh (MFCS 2013) argue that introducing a bound on the
number of connected components in the solution should not make the problem
easier: In particular, they argue that the subexponential time algorithm for
editing to a fixed number of clusters ($p$-Cluster Editing) by Fomin et al.
(J. Comput. Syst. Sci., 80(7) 2014) is an _exception_ rather than the rule.
Here, $p$ is a secondary parameter, bounding the number of components in the
solution.

However, upon bounding the number of stars or bicliques in the solution, we
obtain algorithms which run in time $2^{5\sqrt{pk}}+O(n+m)$ for $p$-Starforest
Editing and $2^{O(p\sqrt{k}\log(pk))}+O(n+m)$ for $p$-Bicluster Editing. We
obtain a similar result for the more general case of $t$-Partite $p$-Cluster
Editing. This is subexponential in $k$ for a fixed number of clusters, since
$p$ is then considered a constant.

Our results even out the number of multivariate subexponential time algorithms
and give reasons to believe that this area warrants further study.

##  1 Introduction

Identifying clusters and biclusters has been a central motif in data mining
research [21] and forms the cornerstone of algorithmic applications in e.g.
biology [24] and expression data analysis [7]. Cai [6] showed that
clustering—among many other graph modification problems of similar flavor—is
solvable in fixed-parameter tractable time. Parallel to these general results,
some progress was made in the area of graphs of topological nature: many
problems are, when restricted to classes characterized by a finite set of
forbidden minors, solvable in _subexponential parameterized time_ , i.e. they
admit algorithms with time complexity $2^{o(k)}\cdot\operatorname{poly}(n)$.

The complexity class of problems admitting such an algorithm is called SUBEPT
and was defined by Flum and Grohe in the seminal textbook on parameterized
complexity [13]. They simultaneously noticed that most natural problems did,
in fact, _not_ live in this complexity class: The classical NP-hardness
reductions paired with the _exponential time hypothesis_ of Impagliazzo,
Paturi and Zane [19] is enough to show that no
$2^{o(k)}\cdot\operatorname{poly}(n)$ algorithm exists.

In this context, Jianer Chen posed the following open problem in the field of
parameterized algorithms [5]: Are there examples of natural problems on
graphs, that do not have such a topological constraint, and also have
subexponential parameterized running time? Alon, Lokshtanov and Saurabh [1]
partially answered this question in the positive by providing a subexponential
time algorithm for Feedback Arc Set on tournament graphs. However, tournament
graphs form a rather atypical class of graphs111For instance, Dominating Set
is W[2]-hard on tournament graphs, but not expected to be NP-hard., so Chen’s
question cannot be considered fully answered—are there problems which are in
SUBEPT on general graphs?

This is indeed the case. Fomin and Villanger [15] showed that Minimum Fill-In
was solvable in time $2^{O(\sqrt{k}\log k)}+\operatorname{poly}(n)$. Minimum
Fill-In is the problem of completing a graph into a chordal graph, adding as
few edges as possible. Following this, a line of research was established
investigating whether more graph modification problems admit such algorithms.
It proved to be a fruitful area; Since the result by Fomin and Villanger, we
now know that several graph modification problems towards classes such as
split graphs [16], threshold graphs [10], trivially perfect graphs [11],
(proper) interval graphs [3, 4] and more admit subexponential time algorithms.

While these classes are rather “simple”, they certainly are much more complex
than simple cluster or bicluster graphs. Therefore, the problems Cluster
Editing and Cluster Deletion were logical candidates for subexponential time
algorithms. Surprisingly, we cannot expect that such algorithms exist.
Komusiewicz and Uhlmann gave an elegant reduction proving that both
parameterized and exact subexponential time algorithms were not achievable,
unless ETH fails [20]. On the other hand, the problem $p$-Cluster Editing,
where the number of components in the target class is fixed to be at most
$p$—rather surprisingly—does indeed admit a subexponential parameterized time
algorithm; This was shown by Fomin et al. [14], who designed an algorithm
solving this problem in time $2^{O(\sqrt{pk})}\cdot\operatorname{poly}(n)$.

Misra, Panolan, and Saurabh [22] explicitly stated their surprise about this
result: In their opinion, bounding the number of components in the target
graph should in general _not_ facilitate subexponential time algorithms
(ibid.): “We show that this sub-exponential time algorithm for the fixed
number of cliques is rather an exception than a rule.”

We show that the related problem Bicluster Editing and its generalization
$t$-Partite $p$-Cluster Editing as well as the special case Starforest Editing
also belong to this exceptional class of problems where a bound on the number
of target components greatly improves their algorithmic tractability. Since
Bicluster Editing is an important tool in molecular biology and biological
data analysis222For more motivations for biclustering problems, we refer to
the two surveys related to biological research, by Madeira and Oliveira [21],
and by Tanay, Sharan and Shamir [24].  and the necessary second parameter is
not outlandish in these settings, we feel that this is a noteworthy insight.
We complement these results with NP-completeness proofs for Bicluster Editing
and $t$-Partite $p$-Cluster Editing on subcubic graphs and further show that,
unless ETH fails, no parameterized or exact subexponential algorithm is
possible without the secondary parameter. That a bound on the maximal degree
does not contribute towards making these problems more tractable contrasts
many other graph modification problems (like modifications towards split and
threshold graphs [23]) which are polynomial time solvable in this setting.

Previously, it was known Bicluster Editing in general is NP-complete [2], and
Guo, Hüffner, Komusiewicz, and Zhang [17] studied the problem from a
parameterized point of view, giving a linear problem kernel with $6k$
vertices, and an algorithm solving the problem in time $O(3.24^{k}+m)$.

#### Our contribution.

In this paper, we study both the very general $t$-Partite $p$-Cluster Editing
as well as editing to the aforementioned special cases. On the positive side,
we show that

  * •

$p$-Starforest Editing is solvable in time $O(2^{5\sqrt{pk}}+n+m)$, and

  * •

both $p$-Bicluster Editing and the more general $t$-Partite $p$-Cluster
Editing are solvable in time $2^{O(p\sqrt{k}\log(pk))}+O(n+m)$ facilitated by
a kernel of size $O(ptk)$, where $t=2$ in the case of $p$-Bicluster Editing.

In many cases, $p$ is considered a constant, and in this case our kernel has
size linear in $k$. We supplement these algorithms with hardness results;
Specifically, we show that

  * •

assuming ETH, Starforest Editing and Bicluster Editing cannot be solved in
time $2^{o(k)}\cdot\operatorname{poly}(n)$ and thus neither can $t$-Partite
Cluster Editing, and

  * •

$p$-Starforest Editing is W[1]-hard if parameterized by $p$ alone.

#### Organization of the paper.

In Section 3 we give a subexponential time parameterized algorithm for the
Starforest Editing problem when parameterized by the editing budget and the
number of stars in the solution simultaneously.

A necessary ingredient for our subexponential algorithms is a polynomial
kernel. A kernel for Bicluster Editing exists already [17] and we provide one
for the $t$-partite case in Section 4. In Section 5 we show that $p$-Bicluster
Editing is solvable in subexponential time in $k$; We give a
$2^{O(p\sqrt{k}\log(pk))}+O(n+m)$ algorithm and generalize it to editing to
$t$-partite $p$-cluster graphs. The parameter $p$ is usually considered to be
a fixed constant, hence the running time is truly subexponential,
$2^{o(k)}+O(n+m)$ in the editing budget $k$. However, for a more fine-grained
complexity analysis and for lower bounds, we treat $p$ as a parameter.

In Section 6 we show that we cannot expect such an algorithm without an
exponential dependency on $p$; The problem is not solvable in time
$2^{o(k)}n^{O(1)}$ unless ETH fails. Further, we show that Starforest Editing
is W[1]-hard if parameterized by $p$ alone, before we conclude in Section 7.

##  2 Preliminaries

We consider only finite simple graphs $G=(V,E)$ and we use $n$ and $m$ to
denote the size of the vertex set and edge set, respectively. We denote by
$N_{G}(v)$ the set of neighbors of $v$ in $G$, and let
$\deg_{G}(v)=|N_{G}(v)|$. We omit subscripts when the graph in question is
clear from context. We refer to the monograph by Diestel [9] for graph
terminology and notation not defined here. For information on parameterized
complexity, we refer to the textbook by Flum and Grohe [13]. We consider an
edge in $E(G)$ to be a set of size two, i.e., $e\in E(G)$ is of the form
$\\{u,v\\}\subseteq V(G)$ with $u\neq v$. We denote by $\left[V(G)\right]^{2}$
the set of all size two subsets of $G$. When
$F\subseteq\left[V(G)\right]^{2}$, we write $G\triangle F$ to denote
$G^{\prime}=(V,E\triangle F)$, where $\triangle$ is the _symmetric difference_
, i.e., $E\triangle F=(E\setminus F)\cup(F\setminus E)$. When the graph is
clear from context, we will refer to $F$ simply as a set of edges rather than
$F\subseteq\left[V(G)\right]^{2}$.

Let us fix the following terminology: A _star graph_ is a tree of diameter at
most two (a graph isomorphic to $K_{1,\ell}$ for some $\ell$). The degree-one
vertices are called _leaves_ and the vertex of higher degree the _center_. A
_starforest_ is a forest whose connected components are stars or,
equivalently, a graph that does not contain $\\{K_{3},P_{4},C_{4}\\}$ as
induced subgraphs. A biclique is a complete bipartite graph $K_{a,b}$ for some
$a,b\in\mathbb{N}$, and a _bicluster graph_ is a disjoint union of bicliques.
A $t$-partite clique graph is a graph whose vertex set can be partitioned into
at most $t$ independent sets, all pairwise fully connected, and a $t$-partite
cluster graph is a disjoint union of $t$-partite cliques. The problem of
editing towards a starforest (resp. bicluster and $t$-partite cluster) is the
algorithmic problem of adding and deleting as few edges as possible to convert
a graph $G$ to a starforest (resp. bicluster and $t$-partite cluster).

#### Exponential time hypothesis.

To show that there is no subexponential time algorithm for Starforest Editing
we give a linear reduction from 3Sat, that is, a reduction which constructs an
instance whose parameter is bounded linearly in the size of the input formula.
The constructed instance will also have _size_ bounded linearly in the size of
the formula, and we use this to also rule out an exact subexponential
algorithm of the form $2^{o(n+m)}\cdot\operatorname{poly}(n)$. Pipelining such
a reduction with an assumed subexponential parameterized algorithm for the
problem would give a subexponential algorithm for 3Sat, contradicting the
complexity hypothesis of Impagliazzo, Paturi, and Zane [19]. Their
Sparsification Lemma shows that, unless ETH fails, 3Sat cannot be solved in
time $2^{o(n+m)}$, where $n$ and $m$ here refer to the number of variables and
the number of clauses, respectively.

##  3 Editing to starforests in subexponential time

A first natural step in handling modification problems related to bicluster
graphs is modification towards the subclass of bicluster graphs called
starforest. Recall that a graph is a starforest if it is a bicluster where
every biclique has one side of size exactly one, or equivalently, every
connected component is a star.

Input: A graph $G=(V,E)$ and a non-negative integer $k$. Parameter: $k$
Question: Is there a set of at most $k$ edges $F$ such that $G\triangle F$ is
a disjoint union of stars? Starforest Editing

The problem where we only allow to _delete_ edges is referred to as Starforest
Deletion. These two problems can easily be observed to be equivalent; Adding
an edge to a forbidden induced subgraph will create one of the other forbidden
subgraphs, or simply put, it never makes sense to add an edge.

In Section 6 we show that this problem is NP-hard, and that it is not solvable
in time $2^{o(k)}n^{O(1)}$ unless the exponential time hypothesis fails.

#### Multivariate analysis.

Since no subexponential algorithm is possible under ETH, we introduce a
secondary parameter by $p$ which bounds the number of connected components in
a solution graph. This has previously been done with success in the Cluster
Editing problem [14]. Hence, we define the following multivariate variant of
the above problem.

Input: A graph $G=(V,E)$ and a non-negative integer $k$. Parameter: $p,k$
Question: Is there a set $F$ of edges of size at most $k$ such that
$G\triangle F$ is a disjoint union of exactly $p$ stars? $p$-Starforest
Editing

Observe that this problem is _not_ the same as $p$-Starforest Deletion since
we might need to merge stars to achieve the desired value $p$ for the number
of connected components. In Section 6 we show that the problem is W[1]-hard
parameterized by $p$ alone, and that we therefore need to parameterize on both
$p$ and $k$.

######  Lemma 1.

Let $(G,k)$ be input to $p$-Starforest Editing. If $(G,k)$ is a yes-instance,
there can be at most $p+2k$ vertices with degree at least $2$.

###### Proof.

Suppose $H=G\triangle F$ is a disjoint union of $p$ stars with $|F|\leq k$.
Let $C$ be the set of $p$ centers. Now, $V(H)\setminus C$ is a set of leaves
of which at most $2k$ can be incident to $F$ in $G$. Since all other leaves
must already have degree one in $G$, the claim follows. ∎

The following bound will be key to obtain the subexponential running time.

######  Proposition 2 ([14]).

If $a$ and $b$ are non-negative integers, then $\binom{a+b}{a}\leq
2^{2\sqrt{ab}}$.

######  Lemma 3.

Given a graph $G$ and a vertex set $S$, we can compute in linear time $O(n+m)$
an optimal editing set $F$ such that $G\triangle F$ is a starforest, when
restricted to have $S$ as the set of centers in the solutions.

###### Proof.

Observe that we need to delete every edge whose endpoints either lie both
inside $S$ or both outside of $S$. What remains is a bipartite graph with $S$
being one side of the bipartition. To complete the editing, for every vertex
$v\in V\setminus S$, with $\deg(v)>1$, we delete all but one edge, and for
every isolated vertex, we arbitrarily attach it to some vertex of $S$. It is
easy to see that this solution is optimal. ∎

We now describe an algorithm which solves $p$-Starforest Editing in time
$O(2^{5\sqrt{pk}}+n+m)$.

#### The algorithm.

Let $(G,k)$ be an input instance for $p$-Starforest Editing. If the number of
vertices of degree at least two is greater than $p+2k$, we say no in
accordance with Lemma 1. Otherwise we split the graph into $G_{1}$ and $G_{2}$
as follows: Let $X\subseteq V(G)$ be the collection of vertices contained in
connected components of size one or two, i.e., $G[X]$ is a collection of
isolated vertices and edges. Let $G_{1}=G[X]$ and $G_{2}=G[V(G)\setminus X]$.
Clearly, there are no edges going out of $X$ in $G$. We will treat
$G_{1},G_{2}$ as (almost) independent subinstances by guessing the budgets
$k_{1}+k_{2}=k$ and the number of components in their respective solutions
$p_{1}+p_{2}=p$. The only time we cannot treat them as independent instances
is when $p_{1}$ or $p_{2}$ is zero; Let $p_{i}^{*}$ be the number of stars
completely contained in $G_{i}$ in an optimal solution. If both $p_{i}^{*}>0$,
then there always exist an optimal solution that does not add any edge between
$G_{1}$ and $G_{2}$.

#### Solving $(G_{1},k_{1})$ with $p_{1}$ components:

Assume $G_{1}$ contains $s$ isolated edges and $t$ isolated vertices, with
$p_{1}>0$. If $|V(G_{1})|<p_{1}$, we immediately say no, since we need exactly
$p_{1}$ connected components. Depending on the values of $s$ and $t$, we
execute the following operations as long as the budget $k_{1}$ is positive. If
$s\leq p_{1}$ and $s+t\leq p_{1}$, we have too few stars, and we arbitrarily
delete edges to increase the number of connected components to $p_{1}$.

If $s=0$ we turn the isolated vertices arbitrarily into $p_{1}$ stars.
Otherwise, fix an arbitrary endpoint $c$ of an isolated edge. Assume that
$s\leq p_{1}$: then we connect enough isolated vertices to $c$ such that the
number of stars is $p_{1}$. Finally, if $s>p_{1}$, we first dissolve $s-p_{1}$
edges and continue as in the previous case. It is easy to check that the above
solutions are optimal.

#### Solving $(G_{2},k_{2})$ with $p_{2}$ components:

By Lemma 1, the number of vertices of degree at least two is bounded by
$p_{2}+2k_{2}$. Every vertex of degree one in $G_{2}$ is adjacent to a vertex
of larger degree, thus it never makes sense to choose it as a center (its
neighbor will always be cheaper). Hence, it suffices to enumerate every set
$S_{2}$ of $p_{2}$ vertices of degree larger than one and test in linear time,
as per Lemma 3, whether a solution inside the budget $k_{2}$ is possible.
Using Proposition 2 we can bound the running time by

$\binom{p_{2}+2k_{2}}{p_{2}}\cdot pk+O(n+m)=O(2^{5\sqrt{p_{2}k_{2}}}+n+m).$

We are left with the cases where $p_{1}$ or $p_{2}$ are equal to zero: then
the only possible solution is to remove  _all_ edges within $G_{1}$ or
$G_{2}$, respectively, and connect all the resulting isolated vertices to an
arbitrary center in the other instance. We either follow through with the
operation, if within the respective budget, or deduce that the subinstance is
not solvable. We conclude that the above algorithm will at some point guess
the correct budgets for $G_{1}$ and $G_{2}$ and thus find a solution of size
at most $k$. The theorem follows.

######  Theorem 4.

$p$-Starforest Editing is solvable in time $O(2^{5\sqrt{pk}}+n+m)$.

##  4 A polynomial kernel for $t$-partite $p$-cluster editing

We show a simple $O(ktp)$ kernel for the $t$-Partite $p$-Cluster Editing
problem—which will be the foundation of the subsequent subexponential
algorithms—with a single rule, Rule 1, which can be exhaustively applied in
time $O(n+m)$. The problem at hand is the following generalization of
$p$-Bicluster Editing:

Input: A graph $G=(V,E)$ and a non-negative integer $k$. Parameter: $p,k$
Question: Is there a set $F\subseteq\left[V\right]^{2}$ of edges of size at
most $k$ such that $G\triangle F$ is a disjoint union of exactly $p$ complete
$t$-partite graphs? $t$-Partite $p$-Cluster Editing

For our rule, we say that a set $X\subseteq V(G)$ is a _non-isolate twin
class_ if for every $v$ and $v^{\prime}$ in $X$,
$N_{G}(v)=N_{G}(v^{\prime})\neq\emptyset$. Note that this is by definition a
_false twin class_ , i.e., $vv^{\prime}\notin E(G)$, or in other words, a non-
isolate twin class is an independent set.

######  Rule 1.

If there is a non-isolate twin class $X\subseteq V(G)$ of size at least
$2k+2$, then delete all but $2k+1$ of them.

######  Lemma 5.

Rule 1 is sound and can be exhaustively applied in linear time.

###### Proof.

To reduce the number of connected components by one we need to add at least
one edge. Hence, a yes-instance cannot contain more than $p+k$ connected
components.

It is sufficient to observe that a non-isolated class of false twins $X$ of
size at least $2k+1$ will never be touched by a minimal solution; Let $(G,k)$
be a yes instance with $F$ a solution. Suppose $X$ is a non-isolated class of
false twins of size at least $2k+1$. At most $2k$ vertices are touched by $X$,
and we claim that $F^{\prime}$, the set of edges of $F$ not incident to any
vertex of $X$ is a solution. Let $x\in X$ be a vertex not incident on $F$.
This means that $N_{G}(x)$ is exactly the entire complete $t$-partite
component except its own part. But since $t$-partite $p$-clusters are closed
under adding non-isolated false twins, we may add as many false twins to $x$
in $G$ as we want without changing the solution. It follows that we may assume
that its false twins will not be touched by $F$ and hence $F^{\prime}$ is a
solution as well.

The rule can be applied in linear time by first computing a modular
decomposition of the input graph, which can be done in linear time [18], and
marking all the vertices to be deleted. ∎

The following result is an immediate consequence of the above rule and its
correctness.

######  Theorem 6.

The problem $t$-Partite $p$-Cluster Editing admits a kernel with
$pt(2k+1)+2k=O(ptk)$ vertices.

###### Proof.

We now count the number of vertices we can have in a yes instance after the
rule above has been applied. We claim that if $G$ has more than $pt(2k+1)+2k$
vertices, it is a no instance.

Let $(G,k)$ be the reduced instance according to Rule 1 and let $F$ be a
solution of size at most $k$. At most $2k$ vertices can be touched by $F$, so
the rest of the graph remains as it is, and is a disjoint union of at most $p$
complete $t$-partite graphs, each of which has at most $t$ non-isolate twin
classes. It follows that in a yes instance, $G$ has at most
$pt(2k+1)+2k=O(ptk)$ vertices. ∎

##  5 Editing to bicluster graphs in subexponential time

In this section we lift the result of Section 3 by showing that the following
problem is solvable in time $2^{O(p\sqrt{k}\log(pk))}+O(n+m)$. Observe that we
lose the subexponential dependence on $p$, however, contrary to the result of
Misra et al. [22], for fixed (or small, relative to $k$) $p$, this still is
truly subexponential parameterized by $k$.

Input: A graph $G=(V,E)$ and a non-negative integer $k$. Parameter: $p,k$
Question: Is there a set $F\subseteq\left[V\right]^{2}$ of edges of size at
most $k$ such that $G\triangle F$ is a disjoint union of $p$ complete
bipartite graphs? $p$-Bicluster Editing

We denote a biclique of $G$ as $C=(A,B)$ and call the sets $A,B$ the _sides_
of $C$. Before describing the algorithm for the general problem, we show that
the following simpler problem is solvable in linear time using a greedy
algorithm:

Input: A bipartite graph $G=(A,B,E)$, a partition
$\mathcal{A}=\\{A_{1},A_{2},\dots,A_{p}\\}$ of $A$ and a non-negative integer
$k$. Question: Is there a set $F\subseteq\left[V\right]^{2}$ of edges of size
at most $k$ such that $G\triangle F$ is a disjoint union of $p$ complete
bipartite graphs with each one side in $\mathcal{A}$? Annotated Bicluster
Editing

######  Lemma 7.

Annotated Bicluster Editing is solvable in time $O(n+m)$.

###### Proof.

Let $G=(A,B,E)$, $\mathcal{A}=\\{A_{1},\dots,A_{p}\\}$, $k$ be an instance of
Annotated Bicluster Editing. Consider a vertex $v\in B$ and define
$\operatorname{cost}_{i}(v)$ to be the cost of placing $v$ in $B_{i}$ where
$C_{i}=(A_{i},B_{i})$ is the $i$th biclique of the solution, i.e.,

$\operatorname{cost}_{i}(v)=|A_{i}|-2\deg_{A_{i}}(v)+\deg(v),$

where $\deg_{A_{i}}(v)=|N(v)\cap A_{i}|$. We prove the following claim which
implies that we can greedily assign each vertex $v\in B$ to a biclique of
minimum cost.

######  Claim 8.

An optimal solution will always have $v\in B$ in a biclique
$C_{i}=(A_{i},B_{i})$ which minimizes $\operatorname{cost}_{i}(v)$.

Suppose that $\operatorname{cost}_{i}(v)$ is minimal but $v$ is placed by a
solution $F$ in a biclique $C_{j}=(A_{j},B_{j})$ with
$\operatorname{cost}_{j}(v)>\operatorname{cost}_{i}(v)$. Deleting from $F$ all
edges $E_{j}$ between $v$ and $A_{j}$ and adding all edges $E_{i}$ between $v$
and $A_{i}$ creates a new solution $F^{\prime}=\left(F\setminus
E_{j}\right)\cup E_{i}$. Since
$\operatorname{cost}_{j}(v)>\operatorname{cost}_{i}(v)$, we have that
$|F|>|F^{\prime}|$ hence $F$ is not optimal. This concludes the proof of the
claim and the lemma. ∎

###  5.1 Subexponential time algorithm

We now show that the problem $p$-Bicluster Editing is solvable in
subexponential time by using the kernel from Theorem 6, guessing the annotated
sets and applying the polynomial time algorithm for the annotated version of
the problem. The important ingredient will be _cheap_ vertices, by which we
mean vertices that are known to receive very few edits. Intuitively, a cheap
vertex is a “pin” that in subexponential time reveals for us its neighborhood
in the solution, and thus can be leveraged to uncover parts of said solution.

We adopt the following notation and vocabulary. For an instance $(G,k)$ of
$p$-Bicluster Editing, and a solution $F$, we call $H=G\triangle F$ the
_target_ graph. A vertex $v$ is called _cheap_ with respect to $F$ if it
receives at most $\sqrt{k}$ edits. Observe that any set $X$ of size larger
than $2\sqrt{k}$ has a cheap vertex. We call such a set _large_ and all sets
that contain at most $2\sqrt{k}$ vertices _small_. We will further classify
the bicliques in the target graph into two different classes: A biclique is
small if its vertex set is small and large otherwise.

The algorithm now works as follows. Given an input instance $(G,k)$ of
$p$-Bicluster Editing, we try all combinations of $p_{s}+p_{\ell}=p$, with the
intended meaning that $p_{s}$ is the number of small bicliques and $p_{\ell}$
is the number of large bicliques in the target graph.

#### Handling small bicliques.

We enumerate a set of $p_{s}$ sets $\mathcal{A}_{s}\subseteq 2^{V}$ with the
property that they are pairwise disjoint, and each of size at most
$2\sqrt{k}$. Furthermore, $G[\bigcup\mathcal{A}_{s}]$ contains at most $k$
edges. Delete all edges in $\mathcal{A}_{s}$ and reduce the budget
accordingly. These are going to be all the left sides in small bicliques. This
enumeration takes time

$(2\sqrt{k})^{p_{s}}{n\choose
2\sqrt{k}}^{p_{s}}\leq(2\sqrt{k})^{p}{pk+k^{2}\choose
2\sqrt{k}}^{p}=2^{O(p\sqrt{k}\log(pk))}.$

#### Handling large bicliques.

The large bicliques have the following nice property. Since the vertex set of
each such biclique is large, every biclique contains a cheap vertex. We guess
a set $\mathcal{B}_{\ell}$ of size $p_{\ell}$. For the biclique $C_{i}$, the
vertex $v_{i}$ of $\mathcal{B}_{\ell}$ will be a cheap vertex in $B_{i}$. Now,
we enumerate all combinations of $p_{\ell}$ sets $\mathcal{N}=\langle
N_{1},N_{2},\dots,N_{p_{\ell}}\rangle$, each of size at most $2\sqrt{k}$ which
will be the edited neighborhood of each cheap vertex, and we conclude that
$A_{i}=N_{H}(v_{i})=N_{G}(v_{i})\triangle N_{i}$. The enumeration of this
asymptotically takes time

$\binom{n}{p_{\ell}}\cdot(2\sqrt{k})^{p_{\ell}}\binom{n}{2\sqrt{k}}^{p_{\ell}}\leq\binom{pk+k^{2}}{p}\cdot(2\sqrt{k})^{p}\binom{pk+k^{2}}{2\sqrt{k}}^{p}=2^{O(p\sqrt{k}\log(pk))}.$

#### Putting things together.

With the above two steps, in time $2^{O(p\sqrt{k}\log(pk))}$ we obtained all
the left sides $\mathcal{A}$, partitioned into $\mathcal{A}_{s}$ and
$\mathcal{A}_{\ell}$. Using this information, we can in polynomial time
compute whether the Annotated Bicluster Editing instance $(G,k,\mathcal{A})$
is a yes-instance. If so, we conclude yes, otherwise, we backtrack.

######  Theorem 9.

$p$-Bicluster Editing is solvable in time $2^{O(p\sqrt{k}\log(pk))}+O(n{+}m)$.

###### Proof.

We now show that the algorithm described above correctly decides $p$-Bicluster
Editing given an instance $(G,k)$. Suppose that the algorithm above concludes
that $(G,k)$ is a yes instance. The only time it outputs yes, is when
Annotated Bicluster Editing for a given set $\mathcal{A}$ and a given budget
$k^{\prime}$ outputs yes. Since this budget is the leftover budget from making
$A$ an independent set, it is clear that any Annotated Bicluster Editing
solution of size at most $k^{\prime}$ gives a yes instance for $p$-Bicluster
Editing.

Suppose now for the other direction that $(G,k)$ is a yes instance for
$p$-Bicluster Editing and let $F$ be a solution. Consider the left sides
$A_{1},\dots,A_{p}$ of $G\triangle F$ with the restriction that the smaller of
the two sides in $C_{i}$ is named $A_{i}$. First we observe that during our
subexponential time enumeration of sets, all the $A_{i}$s that are of size at
most $2\sqrt{k}$ will be enumerated in one of the branches where $p_{s}$ is
set to the number of small bicliques. Furthermore, if $A_{j}$ is large, then
both are large, and then, for each of the large bicliques, there is a branch
where we selected exactly one cheap vertex for each of the largest sides.
Given these cheap vertices, there is a branch where we guess exactly the edits
affecting each of the cheap vertices, hence we can conclude that in some
branch, we know the entire partition $\mathcal{A}$. From Lemma 7, we can
conclude that the algorithm described above concludes correctly that we are
dealing with a yes-instance. ∎

###  5.2 The $t$-partite case

We can in fact obtain similar (we treat $t$ here as a constant so the results
are up to some constant factors in the exponents) results for the more general
case of $t$-Partite $p$-Cluster Editing. Again we need the polynomial kernel
described in Theorem 6. The only difference now to the bicluster case is that
we define a cluster to be small if _every side_ is small. In this case, we can
enumerate $\binom{n}{\sqrt{k}}^{tp}$ sets, which will form the small clusters.

In the other case a cluster $C=(A_{1},A_{2},\dots,A_{t})$ is divided into
$A_{1},A_{2},\dots,A_{t_{s}}$ small sides and
$A_{t_{s}+1},A_{t_{s}+2},\dots,A_{t}$ large sides. For this case, we guess
_all_ the small sides and for each of the large sides we guess a cheap vertex.
Guessing the neighborhoods $N_{t_{s}+1},N_{t_{s}+2},\dots,N_{t}$ for the cheap
vertices $v_{t_{s}+1},v_{t_{s}+2},\dots,v_{t}$ gives us complete information
on $C$; To compute what $A_{j}$ is, if $j>t_{s}$, we simply take the
intersection $\bigcap_{t_{s}<i\leq t,i\neq j}N_{i}$ and remove $\bigcup_{i\leq
t_{s}}A_{i}$. We arrive at the following lemma whose proof is directly
analogous to that of Theorem 9.

######  Theorem 10.

The problem $t$-Partite $p$-Cluster Editing is solvable in subexponential time
$2^{O(p\sqrt{k}\log(pk))}+O(n+m)$.

##  6 Lower bounds

We show that (a) Starforest Editing is NP-hard and that we cannot expect a
subexponential algorithm unless the ETH fails; and (b) that $p$-Starforest
Editing is W[1]-hard parameterized only by $p$.

###  6.1 Starforest editing

In the following we describe a linear reduction from 3Sat to Starforest
Editing. Furthermore, the instance we reduce to has maximal degree three, thus
not only showing that Starforest Editing is NP-hard on graphs of bounded
degree, but also not solvable in subexponential time on subcubic graphs.

######  Theorem 11.

The problem Starforest Editing is NP-complete and, assuming ETH, does not
admit a subexponential parameterized algorithm when parameterized by the
solution size $k$, i.e., it cannot be solved in time $O^{\star}(2^{o(k)})$,
nor in exact exponential time $O^{\star}(2^{o(n+m)})$, even when restricted to
subcubic graphs.

$G_{x}$$c$$C^{x}_{p}$$D^{x}_{p}$$\top^{x}_{0}$$\bot^{x}_{0}$$A^{x}_{0}$$B^{x}_{0}$$C^{x}_{0}$$D^{x}_{0}$
(a) .45

$G_{x}$$G_{y}$$G_{z}$$c=x\lor\neg y\lor z$ (b) .45

Figure 1: Reduction from 3Sat to Starforest Editing on subcubic graphs.

To prove the theorem above we will reduce from 3Sat. But to obtain the result,
it is crucial that in our reduction, both the parameter $k$, and the size of
the instance $G$ are bounded in linearly in $n$ and $m$. Such results have
been shown earlier, in particular by Komusiewicz and Uhlmann for Cluster
Editing [20] and Drange and Pilipczuk for Trivially Perfect Editing [12]. Thus
we resort to similar reductions as used there, however, the reductions here
are tweaked to work for the problem at hand. We also achieve lower bounds for
subcubic graphs. See Figures 1a and 1b for figures of the gadgets.

#### Variable gadget.

Let $\varphi$ be an input instance of 3Sat, and denote its variable set and
clause set as $\mathcal{V}(\varphi)$ and $\mathcal{C}(\varphi)$, respectively.
We construct for $x\in\mathcal{V}(\varphi)$ a graph $G_{x}\cong C_{6p_{x}}$
where $p_{x}$ is the number of clauses in $\varphi$ which $x$ appears in. The
vertices of $G_{x}$ are labeled, consecutively,
$\top^{x}_{i},\bot^{x}_{i},A^{x}_{i},B^{x}_{i},C^{x}_{i},D^{x}_{i}$ for
$i\in[0,p_{x}-1]$.

There are exactly three ways of deleting $G_{x}$ into a starforest using at
most $k_{x}=6p_{x}$ edges. Clearly a collection of $P_{3}$s is a starforest
and is our target graph. We will define the $\top$-deletion for $G_{x}$ as the
deletion set $S^{x}_{\top}=\\{C^{x}_{i}D^{x}_{i},\bot^{x}_{i}A^{x}_{i}\mid
i\leq p_{x}-1\\}$ and the $\bot$-deletion for $G_{x}$ as the deletion set
$S^{x}_{\bot}=\\{A^{x}_{i}B^{x}_{i},D^{x}_{i}\top^{x}_{i+1}\mid i\leq
p_{x}-1\\}$, taking the $i+1$ in the index of $\top^{x}_{i+1}$ modulo $p_{x}$.
In other words, in the gadget $G_{x}$, we are _keeping_ the edges

  * •

$D^{x}_{i-1}\top^{x}_{i}\bot^{x}_{i},A^{x}_{i}B^{x}_{i}C^{x}_{i}$, when $x$ is
set to true, and

  * •

$\top^{x}_{i}\bot^{x}_{i}A^{x}_{i},B^{x}_{i}C^{x}_{i}D^{x}_{i}$, when $x$ is
set to false.

Observe that when $x$ is set to true, we will have paths on three vertices,
where $\top^{x}_{i}$ is the middle vertex, and if $x$ is set to false, we will
have paths on three vertices with $\bot^{x}_{i}$ being the middle vertex.
Later, we will see that if $x$ satisfies a clause $c$, the $i$th clause $x$
appears in, then either $\top^{x}_{i}$ or $\bot^{x}_{i}$ will be the middle
vertex of a claw, depending on whether $x$ appears positively or negatively in
$c$.

######  Observation 12.

In an optimal edge edit of a cycle of length divisible by $6$, no edge is
added and exactly every third consecutive edge is deleted.

#### Clause gadget.

A clause gadget simply consists of one vertex, i.e., for a clause
$c\in\mathcal{C}(\varphi)$, we construct the vertex $v_{c}$. This vertex will
be connected to $G_{x}$, $G_{y}$ and $G_{z}$, for $x,y,z$ being its variables,
in appropriate places, depending on whether or not the variable occurs negated
in $c$. In fact, it will be connected to $\top^{x}_{i}$ if $c$ is the $i$th
clause $x$ appears in, and $x$ appears positively in $c$, and it is connected
to $\bot^{x}_{i}$ if $c$ is the $i$th clause $x$ appears in, and $x$ appears
negatively in $c$.

Let $k_{\varphi}=2|\mathcal{C}|+2\sum_{x}p_{x}=2|\mathcal{C}|+3\cdot
2|\mathcal{C}|=8|\mathcal{C}|$ be the budget for a formula $\varphi$. We now
observe that the budget is tight.

######  Lemma 13.

The graph $G_{\varphi}$ has no starforest editing set of size less than
$k_{\varphi}$, and if the editing set has size $k_{\varphi}$ it contains only
deletions.

###### Proof.

It is straightforward to verify that for each induced variable gadget $G_{x}$
we need at least $2p_{x}$ edges. Since every clause contains three variables,
we have $|\mathcal{C}|/3$ such gadgets, and their necessary budget sum up to
exactly $\sum_{x}2p_{x}\cdot 3=6|\mathcal{C}|$.

Since no two consecutive edges in $G_{x}$ will be deleted, by the previous
observation, we have that for each clause, after deleting edges in the
variable gadgets, we will have an induced subdivided claw with the clause
vertex as its center, and this graph needs at least two edits to become a star
forest. This can be verified by observing that we have three induced $P_{5}$s,
and at most two of them can be removed by one edge edit.

From the above analysis, we can conclude that $G_{\varphi}$ needs at least
$6|\mathcal{C}|\cdot 2|\mathcal{C}|=8|\mathcal{C}|=k_{\varphi}$ edits to
become a starforest graph. ∎

We now continue to the main lemma, from which Theorem 11 follows.

######  Lemma 14.

A 3Sat instance $\varphi$ is satisfiable if and only if
$(G_{\varphi},k_{\varphi})$ is a yes instance for Starforest Editing.

###### Proof.

Suppose $\varphi$ was satisfiable and let
$\alpha\colon\mathcal{V}(\varphi)\to\\{\top,\bot\\}$ be a satisfying
assignment. We show that $G-F$ for $F$ defined below is a starforest graph and
that $|F|\leq k_{\varphi}$ (since the budget is tight, we have equality). For
$x\in\mathcal{V(\varphi)}$ we define $F_{x}$ to be the following set of edges:

  * •

$F_{x}=\\{C^{x}_{i}D^{x}_{i},\bot^{x}_{i}A^{x}_{i}\mid i\leq p_{x}-1\\}$, if
$\alpha(x)=\top$.

  * •

$F_{x}=\\{A^{x}_{i}B^{x}_{i},D^{x}_{i}\top^{x}_{i+1}\mid i\leq p_{x}-1\\}$, if
$\alpha(x)=\bot$.

Finally, for a clause $c\in\mathcal{C(\varphi)}$, let $x_{c}$ be a variable
satisfying $c$. Define $F_{c}$ to be the two edges not incident to $x_{c}$.

We now show that
$F=\bigcup_{x\in\mathcal{V}}F_{x}\cup\bigcup_{c\in\mathcal{C}}F_{c}$ is our
solution. It should at this point be clear that $|F|\leq k_{\varphi}$. Since
$G_{x}-F_{x}$ is a collection of $P_{3}$s, we only need to verify that no
clause gadget $c$ is in an obstruction. Let $c$ be an arbitrary clause gadget
and let $x_{c}$ be the variable that is still incident to $c$. Clearly, since
$c$ is of degree $1$, it has to be in an obstruction with $x_{c}$. However,
since $x_{c}$ satisfies $c$, and (for the moment) assuming that $x_{c}$
appears positively in $c$, $\alpha(x)=\top$ and from $G_{x}$, we deleted
$C^{x}_{i}D^{x}_{i}$ and $\bot^{x}_{i}A^{x}_{i}$ for every $i$. Since $c$
connects to some vertex $\top^{x}_{i}$, the connected component containing $c$
is a claw centered in $\top^{x}_{i}$ with leaves $c$, $D^{x}_{i}$ and
$\bot^{i}_{x}$. Hence $c$ cannot be in an obstruction. The case when $x_{c}$
appears negatively is symmetric. This concludes the forward direction of the
proof.

For the reverse direction, suppose $(G_{\varphi},k_{\varphi})$ is a yes-
instance for Starforest Editing and let $F$ be a solution. Since the budget is
tight, by the above lemma and observation, we know that $F$ contains only
deletions. There are unique ways of deleting all the $G_{x}$s for the variable
gadgets, so construct an assignment for the variables of $\varphi$,
$\alpha_{F}\colon\mathcal{V(\varphi)}\to\\{\top,\bot\\}$ by letting
$\alpha_{F}(x)=\top$ if for some $i$, the edge $\bot^{x}_{i}A^{x}_{i}$ is
deleted, and let $\alpha_{F}(x)=\bot$ otherwise. We claim that $\alpha_{F}$ is
a satisfying assignment. Suppose that a clause $c$ is not satisfied by any of
its variables, and consider $x_{c}$, the variable $c$ is still adjacent to. We
know it must be adjacent to at least one vertex since the budget is tight (not
all three edges were deleted). Suppose $x_{c}$ appeared positively in $c$
(thus the vertex for $c$ is adjacent to some $\top^{x}_{i}$). Since $G-F$ is a
starforest (recall that $F$ can only contain deletions in the given budget),
we know that in the subgraph $G_{x}$ to which $x_{c}$ belongs, we must have
deleted the edge $\bot^{x}_{i}A^{x}_{i}$, for otherwise, since every third
edge is deleted, the edges $D^{x}_{i-1}\top^{x}_{i}$ and
$C^{x}_{i-1}D^{x}_{i}$ would remain and form an induced $P_{4}$, contradicting
the assumption that $G-F$ was a starforest graph. But since
$\bot^{x}_{i}A^{x}_{i}$ was deleted, by the construction of $\alpha_{F}$, we
set $x$ to true, so $x$ indeed satisfies $c$ contradicting the initial
assumption. The case where $x_{c}$ appears negatively in $c$ is symmetric. ∎

Observing that the maximum degree of $G_{\varphi}$ is three—the clause
vertices have exactly degree three, and the variable gadgets are cycles with
some vertices connected to at most one clause vertex—this concludes the proof
of Theorem 11. From the discussions above, the following result is an
immediate consequence:

######  Corollary 15.

The problem Starforest Deletion is NP-complete and not solvable in
subexponential time under ETH, even on subcubic graphs.

Before going into parameterized lower bounds of Starforest Editing, we show
that the exact same reduction above simultaneously proves similar results for
the bicluster case. We note that the NP-hardness was shown by Amit [2], but
their reduction suffers a quadratic blowup and is therefore not suitable for
showing subexponential lower bounds.

######  Corollary 16.

The problems Bicluster Editing and Bicluster Deletion are NP-complete and not
solvable in subexponential time under ETH, even on subcubic graphs.

###### Proof.

We show that every optimum solution of $(G_{\varphi},k_{\varphi})$ for the
above constructed $G_{\varphi}$ and $k_{\varphi}$ will yield a starforest and
hence the corollary follows from the above result. We first show that
Observation 12 also holds for the Bicluster Editing case, that is, for budget
$k_{x}$, there is a unique (up to rotation) solution which consists of
deleting every third edge. First, we observe that deleting every third edge
indeed is a solution as starforests are a subclass of biclusters. Second, we
can pack $3p_{x}$ paths of length four such that each pair of $P_{4}$s share
at most one edge, and such that any edit can eliminate at most two
obstructions. Hence we need at least $2\cdot 3p_{x}=k_{x}$ edges to eliminate
all the $P_{4}$s. Since the budget is tight for $G_{x}$, we now show that we
still need at least two edges to eliminate $G_{c}$

Consider a clause-gadget. Since we have the same situation as above, i.e., it
contains three induced $P_{5}$s, we observe that at least two edits inside the
gadget are necessary. Suppose that one of the edits is an edge addition
(needed to make a biclique that is not a star), then we must use that edge to
construct a $C_{4}$. But this edit leaves one induced $P_{5}$ which cannot be
resolved by the remaining edit.

By combining the arguments for $G_{x}$ and $G_{c}$, we conclude that
$G_{\varphi},k_{\varphi}$ is a yes instance if and only if $\varphi$ is
satisfiable and furthermore that the solution will only delete edges, thus
yielding a starforest. ∎

###  6.2 W[1]-hardness parameterized by $p$

In this section we show that the parameterization by $k$ is necessary, even
for the case of $p$-Starforest Editing. That is, we show that when we
parameterize by $p$ alone, the problem becomes W[1]-hard, and we can thus not
expect any algorithms of the form $f(p)\cdot\operatorname{poly}(n)$ for any
function $f$ solving $p$-Starforest Editing. We reduce from the problem
Multicolored Regular Independent Set. An instance of this problem consists of
a regular graph colored into $p$ color classes, each color class inducing a
complete graph, and we are asked to find an independent set of size $p$.

######  Proposition 17 ([8, Corollary 14.23]).

The problem Multicolored Regular Independent Set is W[1]-complete.

Since each color class is complete, any independent set will be of size at
most $p$ and any independent set of size $p$ is maximum. The reduction is
direct; In fact we have that given a budget $k=(n-p)(d-1)$, where $d$ is the
regularity degree, the following direct translation between the two problems
holds:

######  Lemma 18.

Let $G$ be a $d$-regular graph on $n$ vertices, $p\leq n$ and $k=(n-p)(d-1)$.
Then $(G,p)$ is a yes instance for Multicolored Regular Independent Set if and
only if $(G,k)$ is a yes instance for $p$-Starforest Editing.

###### Proof.

In the forwards direction, suppose $S$ is an independent set of size $p$ in
$G$. Then, since $S$ is maximal, every vertex in $G-S$ is adjacent to $S$. For
every vertex $v\notin S$, delete $d-1$ edges, but keep one connected to a
vertex in $S$. Since there are $n-p$ vertices outside $S$, and since $S$ is an
independent set, this is exactly all the edges we need keep and we obtain a
starforest editing with exactly budget $k$.

For the reverse direction, let us assume that $G$ does not contain an
independent set of size $p$. Hence, any set of $p$ centers contains at least
one edge; the total budget needed to edit to a starforest is then at least
$(n-p)(d-1)+1>k$ and hence the answer for $(G,k)$ is no, as well. ∎

Combining Proposition 17 with Lemma 18 yields the following result:

######  Theorem 19.

$p$-Starforest Editing is W[1]-hard when parameterized by $p$ alone.

##  7 Conclusion

We presented subexponential time algorithms for editing problems towards
bicluster graphs, and more generally, $t$-partite cluster graphs when the
number of connected components in the target graph is bounded. We supplemented
these findings with lower bounds, showing that this dual parameterization is
indeed necessary.

As an interesting open problem, we pose the question of whether $t$-Partite
$p$-Cluster Editing can be solved in time $2^{O(\sqrt{pk})}n^{O(1)}$, i.e., in
subexponential time with respect to both parameters. It is known that
Bicluster Editing admits a linear kernel, but when introducing the secondary
parameter, we only obtain a kernel whose size is bounded by the product of
both parameters; Recall that we got a $tp(2k+1)+2k$ kernel, which in the
bicluster case is $p(4k+2)+2k$. Does Bicluster Editing admit a truly linear
kernel, i.e., a kernel with $O(p+k)$ vertices?

#### Acknowledgments.

We thank Daniel Lokshtanov for pointing us in the direction of Regular
Independent Set [8]. We would like to thank the anonymous reviewers for their
feedback which greatly improved the quality of this paper.

Pål Grønås Drange has received funding from the European Research Council
under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC
Grant Agreement n. 267959.

Fernando Sánchez Villaamil supported by DFG Project RO 927/13-1 “Pragmatic
Parameterized Algorithms”.

## References

  * [1] N. Alon, D. Lokshtanov, and S. Saurabh.  Fast FAST.  In ICALP. Springer, 2009.
  * [2] N. Amit.  The bicluster graph editing problem.  Master’s thesis, Tel Aviv University, 2004.
  * [3] I. Bliznets, F. V. Fomin, M. Pilipczuk, and M. Pilipczuk.  A subexponential parameterized algorithm for interval completion.  CoRR, abs/1402.3473, 2014.
  * [4] I. Bliznets, F. V. Fomin, M. Pilipczuk, and M. Pilipczuk.  A subexponential parameterized algorithm for proper interval completion.  In ESA. Springer, 2014.
  * [5] H. L. Bodlaender, L. Cai, J. Chen, M. R. Fellows, J. A. Telle, and D. Marx.  Open problems in parameterized and exact computation, 2006.  IWPEC.
  * [6] L. Cai.  Fixed-parameter tractability of graph modification problems for hereditary properties.  Inf. Proc. Lett., 58(4):171–176, 1996.
  * [7] Y. Cheng and G. M. Church.  Biclustering of expression data.  In ISMB, 1999.
  * [8] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [9] R. Diestel.  Graph theory (Graduate texts in mathematics).  Springer, 2005.
  * [10] P. G. Drange, M. Dregi, D. Lokshtanov, and Blair D. Sullivan.  On the threshold of intractability.  In ESA. Springer, 2015.
  * [11] P. G. Drange, F. V. Fomin, M. Pilipczuk, and Y. Villanger.  Exploring subexponential parameterized complexity of completion problems.  In STACS. Schloss Dagstuhl, 2014.
  * [12] P. G. Drange and M. Pilipczuk.  A polynomial kernel for trivially perfect editing.  In ESA. Springer, 2015.
  * [13] J. Flum and M. Grohe.  Parameterized complexity theory.  Springer, 2006.
  * [14] F. V. Fomin, S. Kratsch, M Pilipczuk, M. Pilipczuk, and Y. Villanger.  Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters.  J. Comput. Syst. Sci., 80(7):1430–1447, 2014.
  * [15] F. V. Fomin and Y. Villanger.  Subexponential parameterized algorithm for minimum fill-in.  SIAM J. Comput., 42(6):2197–2216, 2013.
  * [16] E. Ghosh, S. Kolay, M. Kumar, P. Misra, F. Panolan, A. Rai, and M. S. Ramanujan.  Faster parameterized algorithms for deletion to split graphs.  Algorithmica, 71(4):989–1006, 2015.
  * [17] J. Guo, F. Hüffner, C. Komusiewicz, and Y. Zhang.  Improved algorithms for bicluster editing.  In TAMC. Springer, 2008.
  * [18] M. Habib and C. Paul.  A survey of the algorithmic aspects of modular decomposition.  Computer Science Review, 4(1):41–59, 2010.
  * [19] R. Impagliazzo, R. Paturi, and F. Zane.  Which problems have strongly exponential complexity?  J. Comput. Syst. Sci., 63(4):512–530, 2001.
  * [20] C. Komusiewicz and J. Uhlmann.  Cluster editing with locally bounded modifications.  Discrete Appl. Math., 160(15):2259–2270, 2012.
  * [21] S. C. Madeira and A. L Oliveira.  Biclustering algorithms for biological data analysis: a survey.  ACM Trans. Comput. Biol. Bioinform, 1(1):24–45, 2004.
  * [22] N. Misra, F. Panolan, and S. Saurabh.  Subexponential algorithm for $d$-cluster edge deletion: Exception or rule?  In MFCS. Springer, 2013.
  * [23] A. Natanzon, R. Shamir, and R. Sharan.  Complexity classification of some edge modification problems.  Discrete Appl. Math., 113(1):109–128, 2001.
  * [24] A. Tanay, R. Sharan, and R. Shamir.  Biclustering algorithms: A survey.  Handbook of Comp. Mol. Biol., 9(1-20):122–124, 2005.


11institutetext: School of Institute of Geophysics and Geomatics, China
University of Geosciences(Wuhan), China 22institutetext: School of Automation,
China University of Geosciences(Wuhan), China 33institutetext: School of
Institute of Geophysics and Geomatics, China University of
Geosciences(Wuhan),China

# Amplification of rotation velocity using weak measurements in Sagnac’s
interferometer

Jing-Hui Huang 11 Xue-Ying Duan 22 Xiang-Yun Hu _Present address:_
<EMAIL_ADDRESS>
(Received: date / Revised version: date)

###### Abstract

We study the amplification of rotation velocity with the Sagnac interferometer
based on the concept of weak-value amplification. By using a different scheme
to perform the Sagnac interferometer with the probe in momentum space, we have
demonstrated the new weak measure protocol to detect the small rotation
velocity by amplifying the phase shift of the Sagnac effect. At the given the
maximum incident intensity of the initial spectrum, the detection limit of the
intensity of the spectrometer and the accuracy of angular velocity
measurement, we can theoretical give the appropriate potselection and the
minimum of optical path area before experiment. In addition, we put forward a
new optical design to increase the optical path area and decrease the size of
the interferometer to overcome the limit of instrument size. Finally, our
modified Sagnac’s interferometer based on weak measurement is innovative and
efficient probing the small rotation velocity signal.

###### pacs:

PACS-keydiscribing text of that key and PACS-keydiscribing text of that key

††offprints:

##  1 Introduction

A general form of quantum weak measurement was first proposed by Aharonov et
alAAV , where information is gained by weakly coupling the probe to the
system. By appropriately selecting the initial and final state of the system,
the measurement can be much larger than the eigenvalues of observables. Thus,
weak-values technique has been widely used to measure and amplify small
physical quantities and effects which are not directly detected by
conventional techniques in experiment, such as direct measuring the real and
imaginary components of the wave-function 2011Spectroscopy , amplification of
angular rotations PhysRevLett.112.200401 , longitudinal velocity
shifts2013Weak , frequency shiftsPhysRevA.82.063822 , optical
nonlinearitiesPhysRevLett.107.133603  and even the test of non-classical
features in quantum mechanics2015Weak ; PhysRevLett.102.020404 .

Although weak measurement have widely used to amplifying the small physical
signal, its application in measuring rotation velocity was rarely reported.
High-resolution rotation velocity measurements plays an important role in many
emerging field. Especially in the rotational seismology, it has been noted by
theoretical seismologists for decades that—in addition to translations and
strains—the rotational part of ground motions should also be
recordedJacopo2012Horizontal ; 2009Introduction ; 0Broad . The optical
interferometer based on the Sagnac effectHeiner2007Broad  has made success in
measuring rotation.

Figure 1: Schematic of Sagnac’s interferometer. A=light source; B= observer;
BS = beam spliter ; D1 and D2 are common mirrors; D3 is a special curved
mirror

The basic principle of Sagnac’s interferometer is given in Fig.
fig:sagnac_interferometer. The light beam coming from the source A is split by
the beam spliter C into a beam circulating the loop in clockwise D1D2D3D4D1
and a beam circulating the same loop in a counterclockwise direction
D1D4D3D2D1. The two beams are reunited in B. When the whole interferometer is
set in rotation with an angular rate of $\Omega$ rad/sec, a fringe shift
$\Delta z$ with respect to the fringe position for the stationary is observed,
which is given by the form

$\displaystyle\Delta z=\frac{4\Omega S}{\lambda_{0}c}$ (1)

where S is the area enclosed by the light path. The vacuum wavelength is
$\lambda_{0}$ and the free space velocity of light is c. Normally, in order to
detecte the small rotation signal, the larger S is need. For example, the
$4\times 4m$ ring laser system 0Broad  that was installed at the geodetic
observatory Wettzell, SE-Germany to detecting the earthquake-induced ground
motions far from seismic sources. In the traditional Sagnac’s interferometer,
the light intensity $I$ at B is recorded, which is dependence of the angular
rate of $\Omega$ rad/sec:

$\displaystyle I=A[1+cos(2\pi\Delta z+\Delta\phi_{m})]$ (2)

Where $\Delta\phi_{m}$ is the phase modulation to get the high sensitivity.
The outgoing light intensity $I$ can not be measured accurately and stably duo
to the relative intensity noise of the light source, the loss and scattering
of optical fibers, especially when the intensity of the detection light is
very small. In that case, we put forward a modified Sagnac’s interferometer
based on weak measurement and analyze it in the momentum(frequency) domain.
Our scheme is essentially different from the traditional Sagnac’s
interferometer, because the the angular rate of $\Omega$ do not depend on
outgoing light intensity $I$, but is sensitive to the shifts of the center
wavelength of the spectrum. As a result, we find that weak-value amplification
of small rotation velocity can be performed with classical light with an
finite bandwidth.
The rest of this paper is organized in the following way. In Section 2, we
give a brief review about weak measurements. In Section 3, we present a scheme
for Amplification of rotation velocity using weak measurements in Sagnac’s
interferometer, and the numerical result is shown In Section 4. Finally, in
Section 5, we give the conclusion about the work. Throughout this paper we
adopt the unit $\hbar=1$.

##  2 The review of Weak measurement

In this section, we briefly review the weak measurement proposed by Aharonov
et al. AAV . The weak measurement is characterized by state preparation, a
weak perturbation, and postselection. We prepare the initial state
$|{\phi_{i}}\rangle$ of the system and $|{\psi_{i}}\rangle$ of the probe.
After a certain interaction between the system and the probe, we postselect a
system state $|{\phi_{f}}\rangle$ and obtain information about a physical
quantity $\hat{A}$ from the probe wave function by the weak value

$\displaystyle
A_{w}:=\frac{\langle{\phi_{f}}|\hat{A}|{\phi_{i}}\rangle}{\langle{\phi_{f}}|{\phi_{i}}\rangle},$
(3)

which can generally be a complex number. More precisely, the shifts of the
position and momentum in the probe wave function are given by the real and
imaginary parts of the weak value $A_{w}$, respectively. We can easily see
from Eq. weak_value that when $|{\phi_{i}}\rangle$ and $|{\phi_{f}}\rangle$
are almost orthogonal, the absolute value of the weak value can be arbitrarily
large. This leads to the weak-value amplification, as we will explain below.
As a trade-off, the probability of obtaining a postselected state that is
almost orthogonal to the preselected state is very small. To make the large
probe shift definite, the weak measurement should be performed many times.

For the weak measurement, the coupling interaction is taken to be the standard
von Neumann Hamiltonian,

$\displaystyle H=g\delta(t-t_{0})\hat{A}\otimes\hat{p},$ (4)

where $g$ is a coupling constant and $\hat{p}$ is the probe momentum operator
conjugate to the position operator $\hat{q}$. We have taken the interaction to
be impulsive at time $t=t_{0}$ for simplicity. The time evolution operator
becomes $\displaystyle e^{-ig\hat{A}\otimes\hat{p}}$. After postselection, the
probe state becomes

$\displaystyle|{\psi_{f}}\rangle=\langle{\phi_{f}}|e^{-ig\hat{A}\otimes\hat{p}}|{\phi_{i}}\rangle|{\psi_{i}}\rangle.$
(5)

We denote the expectation values of the initial and final probe momentum as

$\displaystyle\langle\hat{p}\rangle_{i}:=\frac{\langle{\psi_{i}}|\hat{p}|{\psi_{i}}\rangle}{\langle{\psi_{i}}|{\psi_{i}}\rangle},\
\ \
\langle\hat{p}\rangle_{f}:=\frac{\langle{\psi_{f}}|\hat{p}|{\psi_{f}}\rangle}{\langle{\psi_{f}}|{\psi_{f}}\rangle}.$
(6)

The shift of the expectation value of the momentum is defined by

$\displaystyle\Delta\langle\hat{p}\rangle:=\langle\hat{p}\rangle_{f}-\langle\hat{p}\rangle_{i}.$
(7)

Here, we write ${\Gamma}_{i}(p):=\langle{p}|{\psi_{i}}\rangle$ as the initial
probe wave functions in the momentum spaces, respectively.

To see how the weak value emerges in theory, first consider the weak-coupling
case following the original work AAV . The probe state after the post
selection becomes

$\displaystyle|{\psi_{f}}\rangle$ $\displaystyle=$
$\displaystyle\langle{\phi_{f}}|e^{-ig\hat{A}\otimes\hat{p}}|{\phi_{i}}\rangle|{\psi_{i}}\rangle$
(8) $\displaystyle=$
$\displaystyle\langle{\phi_{f}}|\left[1-ig\hat{A}\otimes\hat{p}\right]|{\phi_{i}}\rangle|{\psi_{i}}\rangle+O(g^{2})$
$\displaystyle=$
$\displaystyle\langle{\phi_{f}}|{\phi_{i}}\rangle\left[1-igA_{w}\hat{p}\right]|{\psi_{i}}\rangle+O(g^{2})$
$\displaystyle=$ $\displaystyle\langle{\phi_{f}}|{\phi_{i}}\rangle
e^{-igA_{w}\hat{p}}|{\psi_{i}}\rangle+O(g^{2})$

for $g|A_{w}|\ll 1$. The probe wave function in the position space after the
postselection becomes

$\displaystyle\langle{p}|{\psi_{f}}\rangle$ $\displaystyle\approx$
$\displaystyle\langle{\phi_{f}}|{\phi_{i}}\rangle
e^{-igA_{w}\hat{p}}\langle{p}|{\psi_{i}}\rangle$ (9)

and therefore, its absolute value squared $|\langle{p}|{\psi_{f}}\rangle|^{2}$
is obtained. Thus, we obtain the shift of the expectation value of the probe
momentum as

$\displaystyle\Delta\langle\hat{p}\rangle=2gW^{2}ImA_{w},$ (10)

which is proportional to the imaginary part of the weak value.

From Eqs. (p_linear), we can extract the weak value, and we can see that, as
the weak value increases the probe position shift is amplified. This effect is
called the weak-value amplification. It is emphasized that the first-order
approximation in $g$ and $|A_{w}|$ is used in the above calculation.

##  3 Weak-value amplification on small rotation velocity

In the following we will consider an weak measurement model probing the small
ratation velocity, meanwhile the numerical result and the discussion are
shown.

###  3.1 Weak-value amplification on the Sagnac’s interferometer

Figure 2: Schematic of the modified Sagnac’s interferometer based on weak
measurements. A=light source; B= observer (the spectrometer) ; D1, D2, D3 and
D4 are common mirrors; F is the Gaussian Filter; P1 is the polarizer
corresponding with preselection, P2 is the polarizer corresponding with
postselection.

We consider a small rotation velocity measurement on the Sagnac’s
interferometer. The Sagnac’s interferometer we consider is shown in
Fig.fig:interferometer. This scheme comprises there parts: state preparation,
a weak perturbation, and postselection. Gwnerally, the state after preparation
can be written as:

$\displaystyle|{\phi_{i}}\rangle=sin(\alpha)|{H}\rangle+cos(\alpha)|{V}\rangle$
(11)

where $|{H}\rangle$ $|{V}\rangle$ represents the horizontal and vertical
polarization, the angel $\alpha$ represents the angle between the direction of
polarization $P1$ and the vertical direction. The beam is injected into a
Sagnac’s interferometer, where the horizontally and vertically polarized
components of the beam circulate in opposite directions. Then the
postselection stated can be obtained by adjusting the polarizer P2:

$\displaystyle|{\phi_{f}}\rangle=$ $\displaystyle-$ $\displaystyle
cos(\alpha+\beta)e^{-i\varphi/2}|{H}\rangle$ (12) $\displaystyle+$
$\displaystyle sin(\alpha+\beta)e^{i\varphi/2}|{V}\rangle$

where the angel $\beta$ represents the angle between the direction of
polarization $P2$ and the horizontal direction of polarization $P1$, and the
phase shift $\varphi$ is produced by the Sagnac effect1967Sagnac  from Eq.
(deltz)

$\displaystyle\varphi=2\pi\Delta z=\frac{8\pi S}{\lambda_{0}c}\Omega$ (13)

In our scheme, the observable $\hat{A}$ satisfies:

$\displaystyle\hat{A}=|{H}\rangle\langle{H}|-|{V}\rangle\langle{V}|$ (14)

After weak correlation and postselection, the probe wave function in the
momentum space becomes

$\displaystyle\langle{p}|{\psi_{f}}\rangle$ $\displaystyle=$
$\displaystyle\langle{\phi_{f}}|{\phi_{i}}\rangle
e^{-igA_{w}\hat{p}}\langle{p}|{\psi_{i}}\rangle$ (15) $\displaystyle=$
$\displaystyle
me^{-igp}\langle{p}|{\psi_{i}}\rangle+ne^{igp}\langle{p}|{\psi_{i}}\rangle$

with

$\displaystyle m=-sin(\alpha+\beta)cos(\alpha)e^{i\varphi/2}$ $\displaystyle
n=cos(\alpha+\beta)sin(\alpha)e^{-i\varphi/2}$

and therefore, its absolute value squared is given by:

$\displaystyle|\langle{p}|{\psi_{f}}\rangle|^{2}$ $\displaystyle=$
$\displaystyle|m+n|^{2}|cos(pg)+ImAwsin(pg)|^{2}$ (16) $\displaystyle\times$
$\displaystyle|\langle{p}|{\psi_{i}}\rangle|^{2}$

With the preselection and postselection, we can derive the so-called weak
value(Eq. weak_value):

$\displaystyle A_{w}$ $\displaystyle=$
$\displaystyle\frac{\langle{\phi_{f}}|\hat{A}|{\phi_{i}}\rangle}{\langle{\phi_{f}}|{\phi_{i}}\rangle}=\frac{m-n}{m+n}$
(17)

$p=\frac{2\pi}{\lambda}$ In our weak measurement protocol, we can get the
shift of the center wavelength $\lambda_{0}$ from the Eq. p_linear with
$g=2\pi/p_{0}$ 2018Optical ; Li:16 , $p_{0}$ corresponds to the center
wavelength $\lambda_{0}=2\pi/p_{0}$.

$\displaystyle\delta\lambda_{0}=-\frac{4\pi(\Delta\lambda)^{2}}{\lambda_{0}}ImA_{w}$
(18)

It is noteworthy that under actual experimental conditions, it is efficient
and convenient to recording the spectrum and fitting the central wavelength of
the spectrum with the Gauss function. Finally, the relationship of the shift
of the central wavelength $\delta\lambda_{0}$ and the rotation velocity
$\Omega$ of the interferometer can be obtain from Eq. (inter_delt_lambda),
because in Eq. (inter_delt_lambda) the rotation velocity $\Omega$ is hidden
variable of the weak value $A_{w}$. In addition, the sensitivity of our scheme
can be defined:

$\displaystyle k=abs(\frac{d\delta\lambda_{0}}{d\Omega})$ (19)

which represents the ratio of the change in the output of the interferometer
to the change in the corresponding input. In the absence of noise
interference, greater sensitivity is our design goal. In this paper, the
results of our simulation experiment will be shown in the next section.

###  3.2 Numerical result and discussion

Figure 3: The results of our simulation experiment with different model.
Table 1: Parameters and the numerical values of our obtain results: S
$[m^{2}]$ is the light area; $\alpha$ $[rad]$ is corresponding to the
preslection and $\beta$ $[rad]$ is corresponding to the postslection; k
[nm/(rad/sec)] is the sensitivity of our scheme and is the absolute value of
the slope in the Fig. result22.

model | $S$ | $\alpha$ | $\beta$ | k
---|---|---|---|---
model1 | 16 | 0.1 | -0.5 | 9.9 $\times 10^{1}$
model2 | 16 | 0.1 | -0.3 | 2.9 $\times 10^{2}$
model3a | 16 | 0.1 | -0.1 | 1.9 $\times 10^{3}$
model4 | 3 | 0.1 | -0.1 | 4.9 $\times 10^{2}$

a The absolute value of the slope with model3 is calculated ( -0.03
$<\Omega<0.03$ ) at small angular velocity.

Figure 4: The shift of the central wavelength $\delta\lambda_{0}$ dependence
of the rotation velocity $\Omega$ with different model.

In what follows, we fix a specific experimental setup, that is, the given
chosen preselected state, postselected state and the initial probe in momentum
space, so that we can calculate the weak value and the shift of the center
wavelength of the probe before the experiment. In our numerical model, We take
the initial probe wave function in ’Gaussian’ form:

$\displaystyle{\Gamma}_{i}(p)={\Gamma}_{i}(\lambda)=I_{0}e^{-(\lambda-\lambda_{0})^{2}/W^{2}},$
(20)

where $W=\Delta\lambda$ is the variance of the initial probe, $\lambda_{0}$ is
the center wavelength of the initial probe, $I_{0}$ is the maximum incident
intensity of the initial spectrum. It is noted that the wavelength and the
momentum of the probe has the relationship $p=2\pi/\lambda$. Then, by using
the Eq. (eq_final_probe) and Eq. (inter_delt_lambda), we obtain probe function
and the shifts of the center wavelength with different values of $S$, and
$\beta$ in Fig. (result_numberical) and Tab. (tab:1).

Fig. (result_numberical) with model1, model2 and model3 show the results of
our simulation experiment with different value of $\beta$ when the optical
path area $S=16m^{2}$ and the angler $\alpha=0.1$ rad are given. The the
optical path area $S=16m^{2}$ is fixed when referring to the actual optical
path area in the $4\times 4m$ ring laser system 0Broad . From the Eq.
(weak_value), we could conclude that the more large amplification is set, the
value of the $\langle{\phi_{f}}|{\phi_{i}}\rangle$ need be smaller. Namely,
The smaller anger $\alpha$ is, the greater shift of the center
$\delta\lambda_{0}$ wavelength will be obtained. Because of the quantum
mechanics principle of measurement, if the preselection state $\phi_{i}$ and
the postselection sate $\phi_{f}$ tend to be orthogonal, we can hardly detect
the final spectrum of the probe. The amplification of the rotation velocity
can not be infinite due to the detection limit of the intensity of the
spectrometer.

Fig. (result_numberical) with model3 and model4 show the results of our
simulation experiment with different value of the optical path area $S$ when
$\beta=0.1$ rad and the angler $\alpha=0.1$ rad are given. The larger the area
S is, the the amplification effect is more obvious. It is convenient and
necessary to design the optical path area smaller in the laboratory.
Meanwhile, the minimum of optical path area is confined by the detection limit
of the intensity of the spectrometer.

###  3.3 A new optical design to increasing the optical path area

Our numerical results show that increasing the optical path area $S$ is the
efficient way to improving the sensitivity of measurement of the rotation
velocity. Due to the limit of size of the interferometer, it is necessary to
design a optic model with the bigger optical path area $S$ and with the small
size of the interferometer. In this paper, we use the radius $R_{s}$ to
describe the size of the interferometer.

Figure 5: The new optical design to increasing the optical path area. A=light
source; B= observer (the spectrometer); F is the Gaussian Filter; D1 and D2
are common mirrors; D3 is a special curved mirror; P1 is the polarizer
corresponding with preselection, P2 is the polarizer corresponding with
postselection.

In the Schematic of traditional Sagnac’s interferometer(Fig.
fig:sagnac_interferometer), the optical path can be replaced by N loops of
fiber, so the fringe shift $\Delta z$ can be be enlarged to $N\times\Delta z$.
Usually, the fiber optic gyroscopes based on principle of traditional Sagnac’s
interferometer Yozo1996Fiber ; articleChung  are commonly used for attitude
and position control in various navigation systems. Due to the low loss in
optical fibers, loops containing several kilometers of the fiber can be used
in order to increase the sensitivity of the device. But in the modified
Sagnac’s interferometer(Fig. fig:interferometer), the scheme to replace the
optical path with optical fiber seems inappropriate. Though the fiber can
transfer polarized lights, it is difficult to technologically ensure that the
polarization of the light at both ends of the fiber is consistent. In that
case, we put forward a complex optical design to increasing theoptical path
area, which is shown in Fig. fig:interferometer2.

Figure 6: The detail of the light passing through the interior of curved
mirror D3.

The main difference between the scheme in Fig. fig:interferometer and the
scheme in Fig. fig:interferometer2 is how to realize the loop of the light.
The new optical design is made to increase the optical path area $S$ and
decrease the size $R_{s}$ of the interferometer. The special curved mirror D3
is made to ensure the light passing through the interiorof curved mirror D3 in
multiple circles. Geometrical optics can decide the relationship of the number
of turns ($N_{r}$) and the angle $\theta_{r}$ of incidence of light rays:

$\displaystyle N_{r}=\frac{\mathcal{F}(2\theta_{r},360^{0})}{360^{0}}$ (21)

where $\mathcal{F}(2\theta_{r},360^{0})$ is the function to obtain the least
common multiple between $2\theta_{r}$ and $360^{0}$. Then we get the
equivalent optical path area $S_{r}$:

$\displaystyle
S_{r}=\frac{\mathcal{F}(2\theta_{r},360^{0})}{2\theta_{r}}Rs^{2}sin(\beta_{r})cos(\beta_{r})$
(22)

where $\beta_{r}=90^{0}-\theta_{r}$. In the scheme(Fig. fig:interferometer2),
we set $\theta_{r}=25^{0}$ and the equivalent optical path area $S_{r}\approx
14Rs^{2}$ is obtained. When we comparing $S_{r}$ to the path area $S=4Rs^{2}$
of the scheme (Fig. fig:interferometer) with square length $2Rs$, the new
design (Fig. fig:interferometer2) could increase the equivalent optical path
area about 3 times the optical path area in the scheme (Fig.
fig:interferometer) with the same size of the interferometer. Finaly, the
above discussion shows the new optical design is efficient way to increase the
optical path area $S$ and decrease the size $R_{s}$ of the interferometer.

##  4 Conclusion

In conclusion, we use weak measurement to probe the small rotation velocity in
Sagnac’s interferometer. By choosing the appropriate preselection,
postselection, the initial probe in the momentum space and the size of the
Sagnac’s interferometer, we obtain the relationship between the shifts of the
center wavelength and the rotation velocity. This amplification effect can’t
be explained by classical wave interference Heiner2007Broad ; 1991Optical ,
due to the statistical feature of preselection and postselection with
disturbancePhysRevLett.113.120404 .

Our scheme is essentially different from the traditional Sagnac’s
interferometer, because the the angular rate of $\Omega$ do not depend on
outgoing light intensity $I$, but is sensitive to the shifts of the center
wavelength of the spectrum. At the given the maximum incident intensity
$I_{0}$ of the initial spectrum, the detection limit of the intensity of the
spectrometer and the accuracy of angular velocity measurement, we can
theoretical give the appropriate potselection and the minimum of optical path
area before experiment. In addition, we put forward a new optical design
increase the optical path area $S$ and decrease the size $R_{s}$ of the
interferometer. Finally, our modified Sagnac’s interferometer based on weak
measurement is efficient probing the small rotation velocity signal and the
relevant optical experiments are taking in progress.

##  5 Authors contributions

All the authors were involved in the preparation of the manuscript. All the
authors have read and approved the final manuscript.

## Acknowledgements

We acknowledge financial support from National Natural Science Foundation of
China (Grants No. 2018YFC1503700, No. G1323519204).

## References

  * (1) Y. Aharonov, D. Z. Albert and L. Vaidman, Phys. Rev. Lett. 60, 1351 (Apr 1988).
  * (2) A. Weissberger and B. W. Rossiter, Nature 474, 188 (2011).
  * (3) O. S. Magaña Loaiza, M. Mirhosseini, B. Rodenburg and R. W. Boyd, Phys. Rev. Lett. 112, 200401 (May 2014).
  * (4) G. I. Viza, J. Martínez-Rincón, G. A. Howland, H. Frostig, I. Shomroni, B. Dayan and J. C. Howell, Optics Letters 38, 2949 (2013).
  * (5) D. J. Starling, P. B. Dixon, A. N. Jordan and J. C. Howell, Phys. Rev. A 82, 063822 (Dec 2010).
  * (6) A. Feizpour, X. Xing and A. M. Steinberg, Phys. Rev. Lett. 107, 133603 (Sep 2011).
  * (7) G. Li, T. Wang, M. Y. Ye and H. S. Song, European Physical Journal D 69 (2015).
  * (8) J. S. Lundeen and A. M. Steinberg, Phys. Rev. Lett. 102, 020404 (Jan 2009).
  * (9) J. Belfi, N. Beverini, G. Carelli, A. D. Virgilio, E. Maccioni, G. Saccorotti, F. Stefani and A. Velikoseltsev, Journal of Seismology (2012).
  * (10) W. H. K. Lee, M. Celebi, M. I. Todorovska and H. Igel, Bulletin of the Ssmological Society of America 99, 945 (2009).
  * (11) I. Heiner, C. Alain, W. Joachim, F. Asher, S. Ulrich, V. Alex and P. D. Nguyen, Geophysical Journal International , 182.
  * (12) E. Post, Geophysical Journal International , 475 (1967).
  * (13) E. J. Post, Review of Modern Physics 39, 475 (1967).
  * (14) D. Li, T. Guan, F. Liu, A. Yang, Y. He, Q. He, Z. Shen and M. Xin, Applied Physics Letters 112, 213701 (2018).
  * (15) D. Li, Z. Shen, Y. He, Y. Zhang, Z. Chen and H. Ma, Appl. Opt. 55, 1697 (Mar 2016).
  * (16) Y. c/o Osaka Works of Sumitomo Nishiura, Fiber-optic gyroscope (1996).
  * (17) H. Chung, L. Ojeda and J. Borenstein, Robotics and Automation, IEEE Transactions on 17, 80 (03 2001).
  * (18) F. Riehle, T. Kisters, A. Witte, J. Helmcke and C. J. Bordé, Physical Review Letters 67, 177 (1991).
  * (19) C. Ferrie and J. Combes, Phys. Rev. Lett. 113, 120404 (Sep 2014).