# Odd Cycle Transversal on $P_{5}$-free Graphs in Polynomial Time111Funding
acknowledgements: Agrawal is supported by SERB Startup Research Grant, no.
SRG/2022/000962; Lima is supported by the Independent Research Fund Denmark
grant agreement number 2098-00012B; Lokshtanov is supported by NSF grant
CCF-2008838; Rzążewski is supported by the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation programme
grant agreement number 948057; Saurabh is supported by the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme grant agreement number 819416, and by a Swarnajayanti Fellowship
(No. DST/SJF/MSA01/2017-18).

Akanksha Agrawal Indian Institute of Technology Madras, Chennai, India,
<EMAIL_ADDRESS>Paloma T. Lima IT University of Copenhagen,
Copenhagen, Denmark<EMAIL_ADDRESS>Daniel Lokshtanov University of California,
Santa Barbara, USA<EMAIL_ADDRESS>Paweł Rzążewski  Warsaw University of
Technology, Warsaw, Poland and Institute of Informatics, University of Warsaw,
Warsaw, Poland<EMAIL_ADDRESS>Saket Saurabh Institute of
Mathematical Sciences, Chennai, India and University of Bergen, Norway,
<EMAIL_ADDRESS>Roohani Sharma<EMAIL_ADDRESS>
###### Abstract

An _independent set_ in a graph $G$ is a set of pairwise non-adjacent
vertices. A graph $G$ is _bipartite_ if its vertex set can be partitioned into
two independent sets. In the Odd Cycle Transversal problem, the input is a
graph $G$ along with a weight function w associating a rational weight with
each vertex, and the task is to find a smallest weight vertex subset $S$ in
$G$ such that $G-S$ is bipartite; the weight of $S$,
$\textnormal{{w}}(S)=\sum_{v\in S}\textnormal{{w}}(v)$. We show that Odd Cycle
Transversal is polynomial-time solvable on graphs excluding $P_{5}$ (a path on
five vertices) as an induced subgraph. The problem was previously known to be
polynomial-time solvable on $P_{4}$-free graphs and NP-hard on $P_{6}$-free
graphs [Dabrowski, Feghali, Johnson, Paesani, Paulusma and Rzążewski,
Algorithmica 2020]. Bonamy, Dabrowski, Feghali, Johnson and Paulusma
[Algorithmica 2019] posed the existence of a polynomial-time algorithm on
$P_{5}$-free graphs as an open problem, this was later re-stated by Rzążewski
[Dagstuhl Reports, 9(6): 2019] and by Chudnovsky, King, Pilipczuk, Rzążewski,
and Spirkl [SIDMA 2021], who gave an algorithm with running time
$n^{O(\sqrt{n})}$.

##  1 Introduction

In a vertex deletion problem, the input is a graph $G$ along with a weight
function $\textnormal{{w}}:V(G)\rightarrow\mathbb{Q}$, and the task is to find
a smallest weight vertex subset $S$ such that removing $S$ from $G$ results in
a graph that belongs to a certain target class of graphs; the weight of $S$
being defined as $\textnormal{{w}}(S)=\sum_{v\in S}\textnormal{{w}}(v)$. By
varying the target graph class we can obtain many classic graph problems, such
as deletion to edge-less graphs (Vertex Cover), deletion to acyclic graphs
(Feedback Vertex Set), deletion to bipartite graphs (Odd Cycle Transversal),
or deletion to planar graphs (Planarization). With the exception of the class
of all graphs, for every target class that contains an infinite set of graphs
and is closed under vertex deletion, the vertex deletion problem to that graph
class is NP-hard [LY80]. For this reason a substantial research effort has
been dedicated to understanding the computational complexity of various vertex
deletion problems when the input graph $G$ is required to belong to a
restricted graph class as well (see [BS+99] and the companion website
[DR+16]).

In this paper, we consider the Odd Cycle Transversal (OCT) problem, that is
the vertex deletion problem to bipartite graphs. A vertex set $S$ is
independent if no edge has both its endpoints in $S$ and a graph $G$ is
bipartite if its vertex set can be partitioned into two independent sets. A
graph is bipartite if and only if it has no odd cycles [Die12]. The OCT
problem is very well studied, and has been considered from the perspective of
approximation [GW98, FHRV07, KSS12], heuristics [Hüf09, AI16], exact
exponential time [RSS07, TM18, KR02] and parameterized algorithms [KW14,
LNR+14, RSV04, LSS09, LSW12, JK11, KMRS20, JBDP21, IOY14, KR10].

From the viewpoint of restricting the input to specific classes of graphs, OCT
is known to be polynomia-time solvable on permutation graphs [BK85] and more
generally on graphs of bounded mim-width [BXTV13]. More recently, $H$-free
graphs, that is, graph classes defined by one forbidden induced subgraph,
received particular attention. Chiarelli et al. [CHJ+18] showed that OCT is
NP-complete on graphs of small fixed girth and line graphs. This implies that
if $H$ contains a cycle or a claw, then OCT is NP-hard on $H$-free graphs.
Hence, we can restrict ourselves to the case in which $H$ is a linear forest
(i.e., each connected component of $H$ is a path). For $P_{4}$-free graphs a
polynomial-time algorithm follows directly from the algorithm of Brandstädt
and Kratsch [BK85] for permutation graphs. Bonamy et al. [BDF+19] posed the
question of the existence of a polynomial-time algorithm for OCT on
$P_{k}$-free graphs, for all $k\geq 5$. Subsequently, Okrasa and Rzążewski
[OR20] showed that OCT is NP-hard on $P_{13}$-free graphs, and shortly
thereafter Dabrowski et al. [DFJ+20] proved that the problem remains NP-hard
even on $(P_{2}+P_{5},P_{6})$-free graphs. On the other hand, OCT is known to
be polynomial-time solvable on $sP_{2}$-free graphs [CHJ+18] and on
$(sP_{1}+P_{3})$-free graphs [DFJ+20], for every constant $s\geq 1$. Thus,
prior to our work, the only connected graph $H$ such that the complexity
status of OCT on $H$-free graphs remained unknown was the $P_{5}$. For this
reason, resolving the complexity status of OCT on $P_{5}$-free graphs was
posed as an open problem by Rzążewski [CPS19], and by Chudnovsky et al.
[CKP+21], who gave an algorithm for OCT on $n$-vertex $P_{5}$-free graphs with
running time $n^{O(\sqrt{n})}$. In this paper, we resolve the open case
regarding the computational complexity of OCT on $P_{5}$-free graphs.
Specifically, we prove the following theorem.

######  Theorem 1.

Odd Cycle Transversal on $P_{5}$-free graphs is polynomial-time solvable.

Note that OCT problem can also be rephrased as the problem of finding a
maximum weight bipartite (induced) subgraph in the input. The proof of Theorem
1 has two main steps as described below.

Small covering family for a solution. Our main technical contribution towards
the proof of Theorem 1 is Lemma 1. We show that if $G$ is a $P_{5}$-free
graph, then in polynomial time one can construct an $\mathcal{O}(n^{6})$-sized
family $\mathcal{C}$ of bipartite sets of $G$, such that there exists a
maximum weight bipartite subgraph of $G$ which is obtained by taking the
induced packing of some of the sets in the family $\mathcal{C}$. Here induced
packing means that no two sets intersect, or have an edge between them.

######  Lemma 1.

Given a $P_{5}$-free graph $G$ and a weight function
$\textnormal{{w}}:V(G)\to\mathbb{Q}$, there exists a polynomial-time algorithm
that outputs a collection $\mathcal{C}\subseteq 2^{V(G)}$ of size
$\mathcal{O}(n^{6})$ such that:

  1. 1.

for each $C\in\mathcal{C}$, $G[C]$ is bipartite, and

  2. 2.

there exists a set $S\subseteq V(G)$ such that $G[S]$ is bipartite and
$\textnormal{{w}}(S)$ is maximum such that
$S=\bigcup_{C\in\mathcal{C}^{\prime}}C$, where
$\mathcal{C}^{\prime}\subseteq\mathcal{C}$ and for each
$C_{1},C_{2}\in\mathcal{C}^{\prime}$, $C_{1}\cap C_{2}=\emptyset$, and
$E(C_{1},C_{2})=\emptyset$.

The proof of Lemma 1 heavily relies on the structure of $P_{5}$-free graphs,
including the classical result that every connected $P_{5}$-free graph has a
dominating $P_{3}$ or dominating clique [BT90], as well as a somewhat
surprising application of the concept of modules [Gal67] (a module in a graph
$G$ is a set $M$ of vertices such that every vertex outside of $M$ either is
adjacent to all of $M$ or to none of $M$). The formal proof of Lemma 1 appears
in Section 3.

Reduction to maximum weight independent set in $P_{5}$-free graphs. Equipped
with Lemma 1, we are now looking for a maximum weight bipartite subgraph, each
of whose connected components is contained in a given polynomial-sized family
$\mathcal{C}$ of connected, bipartite sets. One can now reduce the problem of
finding a maximum weight bipartite subgraph in the input graph $G$ to the
problem of finding a maximum weight independent set in an auxiliary graph
defined as follows: there is a vertex for each set in $\mathcal{C}$, an edge
between a pair of vertices if and only if the corresponding sets are not
disjoint or have an edge connecting them, and the weight of a vertex is the
sum of the weights of the vertices in the set that it corresponds to. As
observed in [GLP+21], if $G$ is $P_{5}$-free, then so is this auxiliary graph.
Therefore, the problem actually reduces to the problem of finding a maximum
weight independent set in $P_{5}$-free graphs, which has been shown to be
polynomial-time solvable by Lokshtanov, Vatshelle, and Villanger [LVV14]. The
formal details of this step appears in Section 4.

##  2 Preliminaries

We denote the set of natural numbers and the set of rational numbers by
$\mathbb{N}=\\{1,2,\cdots\\}$ and $\mathbb{Q}$, respectively, and let
$\mathbb{Q}_{\geq 0}=\\{x\in\mathbb{Q}\mid x\geq 0\\}$. For $c\in\mathbb{N}$,
$[c]$ denotes the set $\\{1,\cdots,c\\}$. For a set $X$, we denote by $2^{X}$
the collection of all subsets of $X$, by ${X\choose i}$ the collection of all
$i$-sized subsets of $X$, by ${X\choose\leq i}$ all subsets of $X$ of size at
most $i$, and by ${X\choose j_{1}\leq i\leq j_{2}}$ the collection of all
$i$-sized subsets of $X$ where $j_{1}\leq i\leq j_{2}$.

Consider a graph $G$. For $v\in V(G)$, $N_{G}(v)$ denotes the set of neighbors
of $v$ in $G$, and $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. For $X\subseteq V(G)$,
$N_{G}(X)=(\bigcup_{x\in X}N_{G}(x))\setminus X$ and $N_{G}[X]=N_{G}(X)\cup
X$. For a subgraph $H$ of $G$, we sometimes write $N_{G}(H)$ (resp.
$N_{G}[H]$) as a shorthand for $N_{G}(V(H))$ (resp. $N_{G}[V(H)]$). For any
$X,Y\subseteq V(G)$, $E_{G}(X,Y)$ denotes the set of edges of $G$ with one
endpoint in $X$ and the other in $Y$. Whenever the graph $G$ is clear from the
context, we drop the subscript $G$ from the above notations. For any
$X\subseteq V(G)$, $G[X]$ denotes the graph induced by $X$, i.e., $V(G[X])=X$
and $E(G[X])=\\{(u,v)\in E(G)\mid u,v\in X\\}$. Moreover, by $G-X$ we denote
the graph $G[V(G)\setminus X]$. For any $v\in V(G)$, we use $G-v$ as a
shorthand for $G-\\{v\\}$. For two graphs $G_{1}$ and $G_{2}$ by $G_{1}\cup
G_{2}$ we denote the graph with vertex set $V(G_{1})\cup V(G_{2})$ and edge
set $E(G_{1})\cup E(G_{2})$.

For any $i\in\mathbb{N}$, $P_{i}$ is a path on $i$ vertices and a $P_{i}$-free
graph is a graph that has no induced subgraph isomorphic to $P_{i}$. A
dominating set in a graph $G$ is a set of vertices $D\subseteq V(G)$ such that
$N[D]=V(G)$.

######  Proposition 2.1 (Theorem $8$, [BT90]).

Every connected $P_{5}$-free graph $G$ has a dominating set $D$ such that
$G[D]$ is either a $P_{3}$ or a clique.

As noted earlier, the OCT problem can be restated as a maximization problem.
We define it directly as a maximization problem below.

Odd Cycle Transversal (OCT) Input: An undirected graph $G$ on $n$ vertices and
a weight function $\textnormal{{w}}:V(G)\to\mathbb{Q}$. Output: Find
$S\subseteq V(G)$, such that $G[S]$ is bipartite and
$\textnormal{{w}}(S)=\sum_{v\in S}\textnormal{{w}}(v)$ is maximized.

A set $S\subseteq V(G)$ such that $G[S]$ is bipartite, is called a solution of
$G$. If $\textnormal{{w}}(S)$ is maximum then we call it an optimal solution
of $(G,\textnormal{{w}})$. We will assume that the weight of each vertex is
positive, as otherwise, we can remove the vertices with non-positive weight
without changing the optimal solution.

##  3 Finding a small covering family of the connected components of a
solution

The goal of this section is to prove Lemma 1.

See 1

At the heart of our proof for the above lemma lies a property that we prove:
for any $S\subseteq V(G)$ where $G[S]$ is a bipartite graph and $C$ is the
connected component of $G[S]$, there is a small set $\widetilde{D}\subseteq
V(G)$, which can be guessed efficiently, such that after doing some
appropriate cleaning operation of the graph, $N[\widetilde{D}]=N[C]$. With
such a set $\widetilde{D}$ at hand, we find a replacement for $C$ in $S$ and
put this replacement in the family $\mathcal{C}$: by a replacement for $C$ we
mean a set $C^{\prime}$ such that $S\setminus C\cup C^{\prime}$ is also a
bipartite set of weight as large as $S$. Such a replacement $C^{\prime}$ is
found by exploiting the known algorithm for computing independent sets on
$P_{5}$-free graphs. We will now intuitively explain the steps of our
algorithm, and we give a concrete pseudo-code for it in Algorithm 1.

In the following, we denote the input graph by $G^{\prime}$ (instead of $G$).
Consider a set $S\subseteq V(G^{\prime})$ where $G^{\prime}[S]$ is bipartite,
and let $C$ be an arbitrary connected component of $G^{\prime}[S]$. Our goal
is to compute a polynomial-sized family $\mathcal{C}$ of vertex subsets that
either contains $C$ itself or a replacement for $C$.

To cover the trivial case when $C$ has exactly one vertex, we add the sets
$\\{v\\}$ for each $v\in V(G)$ to the family $\mathcal{C}$ in Line 1.
Hereafter, assume that $C$ has at least $2$ vertices. As $C$ is a connected,
$P_{5}$-free and bipartite graph, from Proposition 2.1, there must exist a
dominating induced $P_{3}$ or a dominating $P_{2}$ for $C$; let one such
$P_{3}$ or $P_{2}$ be $D$. Note that $V(C)\subseteq N[D]$. The loop at Line 2
of Algorithm 1 will precisely be iterating over such potential $D$s. We will
next explain our operations for this fixed $D$, and since we will delete some
vertices from our graph, we initialize $G=G^{\prime}$ at Line 3. We remark
that, at all point of time we will implicitly maintain that $S\subseteq V(G)$,
and thus maintain that $C$ is the connected component of $G[S]$.

Figure 1: Illustration of various sets and connected components used in the
algorithm. The striped ovals denote removal of the corresponding vertices by
the algorithm.

We let $C_{L}\uplus C_{R}$ be the unique bipartition of $C$ and $D_{L}\uplus
D_{R}$ be the bipartition of $D$ such that $D_{L}\subseteq C_{L}$ and
$D_{R}\subseteq C_{R}$ (see Figure 1).222Note that both $C$ and $D$ are
connected bipartite graphs. Thus, upto switching parts, there is exactly one
valid bipartition of each of these graphs. Recall that $C$ is the connected
component of $G[S]$. Notice that any vertex $u\in N(D_{L})\cap N(D_{R})$ must
lie outside of $S$.333Unless stated explicitly, inside the loop starting at
Line 2, we will only be concerned with the graph $G$, and thus, we omit the
graph subscripts from the notations like $N(D_{L})$. Thus, Line 5-7 removes
such vertices from $G$.

A set of vertices $A\subseteq V(G)$ is a module in $G$, if for every pair
$x,y\in A$, $N(x)\setminus A=N(y)\setminus A$. Note that checking whether a
set $A\subseteq V(G)$ is a module can be done in polynomial time.

We let $X$ be the neighbors of $C$ outside $N(D)$, i.e., $X=N(C)\setminus
N(D)$. Also, we let $Y$ be the vertices outside of $C$ and its neighborhood,
i.e., $Y=V(G)\setminus N[C]$. We will establish the following statements:

(In Claim 3.1) There are no edges between a vertex in $X$ and a vertex in $Y$,
i.e., $E(X,Y)=\emptyset$.

(In Claim 3.2) Each connected component of $G[Y]$ is a module in $G$.

(In Claim 3.3, stated roughly here) the graph $G[X\cup V(C)]$ has a dominating
set $\widetilde{D}$ such that: $D\subseteq\widetilde{D}$ and
$|\widetilde{D}\setminus D|\leq 3$.

Recall our assumption that $V(C)\subseteq N[D]$. Using the first property that
we establish, we can obtain that for any connected component $Z$ of $G-N[D]$,
either $V(Z)\subseteq X$ or $V(Z)\subseteq Y$. Now using the second property
stated above, we can obtain that the vertices in a non-module connected
component of $G-N[D]$ must belong to $X$, and thus it cannot contain a vertex
from $S$. This leads us to Line 8-10 of our algorithm, where we remove
vertices from all such non-module connected components. We let $R\subseteq X$
be the vertices remaining after the above stated deletion of vertices from
$X$.

The third property will be used to completely identify the vertices of $N[C]$,
however, we may not be able to precisely distinguish which vertices from
$N[C]$ belong to $C$. To this end, we will iterate over the potential choices
of $D^{\prime}$ of size at most $3$, so that $\widetilde{D}=D\cup D^{\prime}$
is a dominating set for $G[R\cup V(C)]$, at Line 11. We will argue that for
such a correct $\widetilde{D}$, we must have $N[\widetilde{D}]=N[C]$. Thus,
knowing $\widetilde{D}$ precisely gives us $N[C]$, and at Line 12 we denote
the respective set by $C^{*}_{D,D^{\prime}}=N[\widetilde{D}]=N[C]$.

Recall that $C$ is a connected biparitite induced subgraph of $G[S]$, and any
vertex from $G[N[\widetilde{D}]]=G[N[C]]$ that has a neighbor from
$V(G^{\prime})\setminus N[\widetilde{D}]$ cannot belong to $S$ (and thus $C$).
Thus, at Line 13-15 we do the cleaning operation by removing such vertices
from $G$.

After this (in the graph resulting after the previous deletions), we obtain
that $N[C]$ is a connected component of $G$ (not necessarily bipartite) and
$S\subseteq V(G)$. Now instead of finding $V(C)$ inside $N[C]$ exactly, we
will find some $C^{\prime}$ which will be as good as $V(C)$ as follows. We
recall that $D$ is a connected bipartite dominating set for $C$ and thus (upto
switching parts), $D$ has a unique bipartition $D_{L}\uplus D_{R}$, which we
have fixed at Line 4, and we have assumed that $D_{L}\subseteq C_{L}$ and
$D_{R}\subseteq C_{R}$. Due to the cleaning operation of $G$ at Line 5-7,
$D_{L}$ and $D_{R}$ have no common neighbors, i.e., $N[D_{L}]\cap
N[D_{R}]=\emptyset$. Moreover, as $D$ is a dominating set for the bipartite
connected graph $C$, it must be the case that $C_{L}\subseteq N[D_{R}]$ and
$C_{R}\subseteq N[D_{L}]$. Also, recall due to the operations at Line 13-15 we
will be able to conclude that $N[C]$ is a connected component in $G$ and $S$
is an induced subgraph of $G$. Now instead of finding $C_{L}$ and $C_{R}$
precisely, we find maximum weight independent sets $I_{L}$ and $I_{R}$ on
graphs $G[N[D_{R}]]$ and $G[N[D_{L}]]$, respectively. Notice that due to our
discussions above, $I_{L}$ and $I_{R}$ must be disjoint. We then show that
$C_{D,D^{\prime}}=I_{L}\uplus I_{R}$ serves as a replacement for $V(C)$, and
thus we add $C_{D,D^{\prime}}$ to $\mathcal{C}$ at Line 19.

We next state a known result regarding computation of independent sets on
$P_{5}$-free graphs.

######  Proposition 3.1 ([LVV14], Independent Set on $P_{5}$-free).

Given a graph $G$ and a weight function
$\textnormal{{w}}:V(G)\to\mathbb{Q}_{\geq 0}$, there is a polynomial-time
algorithm that outputs a set $I\subseteq V(G)$ such that $I$ is an independent
set in $G$ and $\textnormal{{w}}(I)=\sum_{u\in I}\textnormal{{w}}(u)$ is the
maximum.

Algorithm 1 Isolating a connected Component

0: An undirected graph $G^{\prime}$, a vertex $v\in V(G^{\prime})$ and a
weight function $\textnormal{{w}}:V(G^{\prime})\to\mathbb{Q}_{\geq 0}$

0: $\mathcal{C}\subseteq 2^{V(G^{\prime})}$ satisfying the properties of Lemma
1

1: Initialize $\mathcal{C}=\\{\\{v\\}:v\in V(G)\\}$.

2: for all $D\subseteq{V(G^{\prime})\choose{2\leq i\leq 3}}$, where
$G^{\prime}[D]$ is connected and bipartite do

3: Initialize $G=G^{\prime}$.

4: Fix a bipartition $D=D_{L}\uplus D_{R}$.

5: while there exists $u\in N(D_{L})\cap N(D_{R})$ do

6: Delete $u$ from $G$. That is, $G=G-u$.

7: end while

8: while there exists a connected component $Z$ of $G-N[D]$ such that $V(Z)$
is not a module in $G$ do

9: Delete $Z$ from $G$. That is, $G=G-V(Z)$.

10: end while

11: for all $D^{\prime}\subseteq{V(G)\choose\leq 3}$ do

12: Let $C_{D,D^{\prime}}^{*}=N[D\cup D^{\prime}]$.

13: while there exists $u\in C_{D,D^{\prime}}^{*}$ such that
$N_{G^{\prime}}(u)\setminus C_{D,D^{\prime}}^{*}\neq\emptyset$ do

14: Delete $u$ from $G$. That is, $G=G-u$.

15: end while

16: Let $I_{L}$ be a maximum weight independent set obtained by running the
algorithm of Proposition 3.1 on input $(G[N(D_{R})],\textnormal{{w}})$.

17: Let $I_{R}$ be a maximum weight independent set obtained by running the
algorithm of Proposition 3.1 on input $(G[N(D_{L})],\textnormal{{w}})$.

18: Let $C_{D,D^{\prime}}=I_{L}\cup I_{R}$.

19: Update $\mathcal{C}=\mathcal{C}\cup\\{C_{D,D^{\prime}}\\}$.

20: end for

21: end for

We remark that for our algorithm we need the algorithm of Proposition 3.1 to
return a maximum weight independent set and not just the weight such a set.
The arguments in [LVV14] suffice to output such a set. The following
observation is immediate from the description of the algorithm and Proposition
3.1.

######  Observation 2.

Algorithm 1 runs in polynomial time.

We prove the correctness of our algorithm in the next lemma.

######  Lemma 3.

The family $\mathcal{C}$ outputted by Algorithm 1 satisfies the properties of
Lemma 1.

###### Proof.

To bound the size of the family $\mathcal{C}$, observe that $\mathcal{C}$ is
initialized in Line 1 and updated only in Line 19. At Line 1 the size of
$\mathcal{C}$ is $n$ and Line 19 is executed at most $O(n^{6})$ times: inside
the for-loop at Line 2 which contains the for-loop at Line 11.

It is also easy to see that the sets of $\mathcal{C}$ induce bipartite
subgraphs of $G$. Indeed, at Line 1 we add singleton sets, and the sets
$C_{D,D^{\prime}}$ added at Line 19 are the union of two independent sets
$I_{L}$ and $I_{R}$ (Line 18), and therefore $G[C_{D,D^{\prime}}]$ is
bipartite.

We will now show the second property of the lemma. Let $S\subseteq
V(G^{\prime})$ such that $G^{\prime}[S]$ is bipartite, $\textnormal{{w}}(S)$
is maximum and $S$ has the maximum number of connected components from
$\mathcal{C}$. If all connected components of $S$ are in $\mathcal{C}$ then we
are done. Otherwise let $C$ be a connected component of $G^{\prime}[S]$ such
that $C\not\in\mathcal{C}$. If $C$ has exactly one vertex then
$C\in\mathcal{C}$ from Line 1, and hence a contradiction. Therefore assume
that $|V(C)|\geq 2$. As $C$ is a connected, $P_{5}$-free and bipartite graph
on at least $2$ vertices (therefore triangle-free, from Proposition 2.1 there
exists a dominating set $D$ of $C$ which either induces a $P_{3}$ or a
$P_{2}$. We consider the execution of the for-loop at Line 2 for this $D$, and
let $D_{L}\uplus D_{R}$ be the bipartition of $D$ considered at Line 4 of
Algorithm 1. Furthermore, let $C_{L}\uplus C_{R}$ be the bipartition of $C$
such that $D_{L}\subseteq C_{L}$ and $D_{R}\subseteq C_{R}$.

[Lines 5-7] Note that any vertex $u\in N(D_{L})\cap N(D_{R})$ is not in $C$.
Furthermore, such a vertex $u\not\in S$ because $u\in N(C)$ (since $D\subseteq
V(C)$). Thus, $S$ is an induced bipartite subgraph of $G$.

[Lines 8-10] We will now show that any connected component of $G-N[D]$ which
is not a module, is a subset of $N(C)$. Once this is proved, $S$ also induces
a bipartite subgraph in $G-V(Z)$, where $Z$ is a connected component of
$G-N[D]$ that is not a module. Let $X=N(C)\setminus N(D)$ and let
$Y=V(G)\setminus N[C]$.

Figure 2: Illustration of various elements in the proof of Claim 3.1.

######  Claim 3.1.

$E(X,Y)=\emptyset$.

###### Proof.

Suppose for the sake of contradiction that there exists $y\in Y$ and $x\in X$
such that $(y,x)\in E(G)$ (see Figure 2). Since $x\in X$ and $X=N(C)\setminus
N(D)$, there exists $c\in C$ such that $(x,c)\in E(G)$. Also $c\not\in D$, as
otherwise $x\in N(D)$. Without loss of generality, say $c\in C_{L}\setminus D$
(the other case is symmetric). Since $D$ is a dominating set of $C$, there
exists $d\in D_{R}$, such that $(c,d)\in E(G)$. Let $d^{\prime}\in D_{L}$, and
note that $(d,d^{\prime})\in E(G)$.

Consider the path $P^{*}=(y,x,c,d,d^{\prime})$. We claim $P^{*}$ is an induced
$P_{5}$. First observe that all the vertices of $P^{*}$ except $y,x$ are in
$C$. Also $E(Y,C)=\emptyset$ because $Y\cap N(C)=\emptyset$ by the definition
of $Y$. In particular, $(y,c),(y,d),(y,d^{\prime})\not\in E(G)$. Since $x\in
X$ and $X\cap N(D)=\emptyset$, $(x,d),(x,d^{\prime})\not\in E(G)$. Finally,
since $c,d^{\prime}\in C_{L}$ and $C_{L}$ is an independent set (because it is
one of the parts of the bipartition of $C$), $(c,d^{\prime})\not\in E(G)$. ∎

From Claim 3.1, for any connected component $Z$ of $G-N[D]$, either
$V(Z)\subseteq X$, or $V(Z)\subseteq Y$.

Figure 3: Illustration of various elements in the proof of Claim 3.2.

######  Claim 3.2.

Let $Y^{\prime}$ be a connected component of $G[Y]$. Then $V(Y^{\prime})$ is a
module in $G$.

###### Proof.

First note that, from Claim 3.1, $N_{G}(Y)\subseteq N(D)\setminus V(C)$. For
the sake of contradiction, say $V(Y^{\prime})$ is not a module, and thus there
exists $y_{1},y_{2}\in V(Y^{\prime})$ and $u\in N(D)\setminus V(C)$ such that
$(y_{1},u)\not\in E(G)$ and $(y_{1},y_{2}),(y_{2},u)\in E(G)$ (see Figure 3).
Since $u\in N(D)\setminus V(C)$ and $D\subseteq V(C)$, there exists $d\in D$
such that $(u,d)\in E(G)$. Without loss of generality let $d\in D_{L}$. Let
$d^{\prime}\in D_{R}$ (and note that $(d,d^{\prime})\in E(G)$). Then
$(u,d^{\prime})\not\in E(G)$ as otherwise $u\in N(D_{L})\cap N(D_{R})$, which
is a contradiction as such vertices do not exist (from Line 5-7). Then
$P^{*}=(y_{1},y_{2},u,d,d^{\prime})$ is an induced $P_{5}$ in $G$, which is a
contradiction. ∎

From Claim 3.2 if a connected component $Z$ of $G-N[D]$ is not a module, then
$V(Z)\subseteq X$. Since $X\subseteq N(C)$, $S$ is also an induced subgraph of
$G$ after the execution of Line 8-10.

[Line 11] Let $R=N(C)\setminus N(D)$, i.e., $R$ are the remaining vertices of
$N(C)$ that are not in $N(D)$ (note that $R$ are precisely the vertices of $X$
from the previous discussion that are not deleted at Line 8-10). We now show
that there exists a small dominating set of $G[R\cup V(C)]$.

######  Claim 3.3.

$G[R\cup V(C)]$ has a dominating set $\widetilde{D}$ of size at most $6$ such
that $D\subseteq\widetilde{D}$ and $|\widetilde{D}\setminus D|\leq 3$.

###### Proof.

Since $G[R\cup V(C)]$ is a connected and $P_{5}$-free graph, from Proposition
2.1, there exists a dominating set of $G[R\cup V(C)]$ which is either a clique
or an induced $P_{3}$. If $D$ itself is a dominating set of $G[R\cup V(C)]$,
then the claim trivially follows. Otherwise, we consider a dominating clique
or a dominating induced $P_{3}$, $D^{\prime}$ of $G[R\cup V(C)]$ of minimum
possible size. If $D^{\prime}$ induces a $P_{3}$ then,
$\widetilde{D}=D^{\prime}\cup D$ satisfies the requirement of the claim. Now
we consider the case when $D^{\prime}$ is a clique. Using $D^{\prime}$ we will
construct a dominating set of $G[R\cup V(C)]$ with at most $6$ vertices,
containing the vertices from $D$. Intuitively speaking, apart from $D$ (whose
size is at most $3$) we will add vertices from $D^{\prime}\cap V(C)$ and at
most one more vertex. We remark that as $D^{\prime}$ is a clique and $C$ is a
bipartite graph, $|D^{\prime}\cap V(C)|\leq 2$.

Let $R_{1},\ldots,R_{p}$ be the connected components of $G[R]$. Since
$D^{\prime}$ is a clique, $D^{\prime}$ intersects at most one $R_{i}$, i.e.,
there exists an $i\in[p]$, such that $D^{\prime}\cap V(R_{j})=\emptyset$, for
all $j\in[p]\setminus\\{i\\}$. Therefore the vertices of
$\bigcup_{j\in[p]\setminus\\{i\\}}V(R_{i})$ are dominated by the vertices of
$D^{\prime}\cap V(C)$. If $D^{\prime}\cap V(R_{i})=\emptyset$, then notice
that $D^{\prime}\subseteq V(C)$, where $|D^{\prime}|\leq 2$, and thus
$\widetilde{D}=D^{\prime}\cup D$ satisfies the requirement of the claim. Now
suppose that $D^{\prime}\cap V(R_{i})\neq\emptyset$, and consider a vertex
$x\in D^{\prime}\cap V(R_{i})$. Recall that $x\in N(C)$ and $R_{i}$ is a
module in $G$. Thus, there exists a vertex $v^{\prime}\in V(C)\cap N(x)$, and
moreover, we have $V(R_{i})\subseteq N(v^{\prime})$. Note that $D$ dominates
each vertex in $C$, $v^{\prime}$ dominates each vertex in $R_{i}$, and
$D^{\prime}\cap V(C)$ dominates each vertex in
$\bigcup_{j\in[p]\setminus\\{i\\}}V(R_{i})$. Thus,
$\widetilde{D}=D\cup\\{v^{\prime}\\}\cup(D^{\prime}\cap V(C))$ dominates each
vertex in $G[R\cup V(C)]$ and $|D^{\prime}\cap V(C)|\leq 2$. This concludes
the proof. ∎

Now consider the execution of the for-loop at Line 11 when
$\widetilde{D}=D^{\prime}\cup D$ is a dominating set for $G[R\cup C]$.

[Line 12] Our objective is to argue that the set $C^{*}_{D,D^{\prime}}$ at
Line 12 is equal to $N[C]$. To obtain the above, it is enough to show that
$N[\widetilde{D}]=N[C]$. To this end, we first obtain that $N[C]\subseteq
N[\widetilde{D}]$. Recall that, after removing the vertices from $X$ at Line
8, $N[C]=R\cup V(C)\cup N(D)$. As $\widetilde{D}=D\cup D^{\prime}$ is a
dominating set for $G[R\cup V(C)]$, we have $R\cup V(C)\subseteq
N[\widetilde{D}]$. Moreover, as $D\subseteq\widetilde{D}$, we have
$N(D)\subseteq N[\widetilde{D}]$. Thus we can conclude that $N[C]\subseteq
N[\widetilde{D}]$. We will next argue that $N[\widetilde{D}]\subseteq N[C]$.
Recall that from Claim 3.1, $E(R,Y)=\emptyset$. Thus, for any vertex $v\in
D^{\prime}\setminus V(C)$, $N(v)\subseteq N[C]$. In the above, when $v\in
D^{\prime}\setminus V(C)$, without loss of generality we can suppose that
$v\in R\subseteq N(C)$, as $\widetilde{D}=D\cup D^{\prime}$ is a dominating
set for $G[R\cup V(C)]$. Thus, for each $v\in D^{\prime}\setminus V(C)$,
$N[v]\subseteq N[C]$. Also, $D\subseteq V(C)$, and thus, $N[D]\subseteq N[C]$.
Hence it follows that $N[\widetilde{D}]\subseteq N[C]$. Thus we obtain our
claim that, $N[\widetilde{D}]=N[C]$.

[Lines 13-15] Since $C^{*}_{D,D^{\prime}}=N[C]$, if there exists $u\in
C^{*}_{D,D^{\prime}}$ such that $u$ has a neighbor outside
$C^{*}_{D,D^{\prime}}$, then $u\in N(C)$ and hence $u\not\in S$. Thus $S$
induces a bipartite subgraph even in the graph obtained by deleting such
vertices. Notice that after execution of these steps, $N[C]$ is a connected
component of $G$, as removing a vertex from $N(C)$ cannot disconnect the graph
$N[C]$.

[Lines 16-18] Recall that $D$ is a dominating set of $C$ and $C_{L}\uplus
C_{R}$ is a bipartition of $C$, where $C_{L}\subseteq N(D_{R})$ and
$C_{R}\subseteq N(D_{L})$. Also, from Line 5-7, $N(D_{L})\cap
N(D_{R})=\emptyset$. Let $I_{L}$ (resp. $I_{R}$) be the maximum weight
independent set in $G[N[D_{R}]]$ (resp. $G[N[D_{L}]]$) computed at these
steps. Then $\textnormal{{w}}(I_{L})\geq\textnormal{{w}}(C_{L})$ (resp.
$\textnormal{{w}}(I_{R})\geq\textnormal{{w}}(C_{R})$) because $C_{L}$ (resp.
$C_{R}$) is an independent set in $G[N[D_{R}]]$ (resp. $G[N[D_{L}]]$). Thus,
$\textnormal{{w}}(C_{D,D^{\prime}})\geq\textnormal{{w}}(V(C))$.

Let $S^{\prime}=(S\setminus V(C))\cup C_{D,D^{\prime}}$. Then
$\textnormal{{w}}(S^{\prime})\geq\textnormal{{w}}(S)$. Also $G[S^{\prime}]$ is
bipartite because $G[C_{D,D^{\prime}}]$ is bipartite and $E(S\setminus
V(C),C_{D,D^{\prime}})=\emptyset$ because $N[C]$ is a connected component of
(the reduced graph) $G$. Additionally $S^{\prime}$ has more connected
components in $\mathcal{C}$ compared to $S$, which contradicts the choice of
$S$. ∎

The proof of Lemma 1 follows from Observation 2 and Lemma 3.

##  4 Reduction to Maximum Weight Independent Set on $P_{5}$-free Graphs and
Proof of Theorem 1

In this section we show how, using Lemma 1, we can reduce, in polynomial time,
the problem of finding a maximum weight induced bipartite subgraph on
$P_{5}$-free graphs, to the problem of finding a maximum weight independent
set on $P_{5}$-free graphs. Recall that Lokshtanov et al. [LVV14] gave a
polynomial-time algorithm for the latter problem. Their result, together with
the reduction in this section proves Theorem 1.

Recall that $(G,\textnormal{{w}})$ is an instance of OCT where $G$ is a
$P_{5}$-free graph. Let $\mathcal{C}$ be the family of vertex subsets of $G$
obtained from Lemma 1 on input $(G,\textnormal{{w}})$. Let
$\widetilde{\mathcal{C}}\subseteq 2^{V(G)}$ be the family containing the
vertex set of each connected component in the graph induced by each set in the
family $\mathcal{C}$. We say that two sets
$C_{1},C_{2}\in\widetilde{\mathcal{C}}$ touch each other, if either
$V(C_{1})\cap V(C_{2})\neq\emptyset$ or $E(C_{1},C_{2})\neq\emptyset$. The
following lemma reduces the task of finding a maximum weight bipartite
subgraph in $G$ to that of finding a pairwise non-touching collection of sets
in $\mathcal{C^{\prime}}$ of maximum total weight.

######  Lemma 4.

$(G,\textnormal{{w}})$ has an induced bipartite subgraph of weight (defined by
w) $W$ if and only if there exists
$\mathcal{C}^{\prime}\subseteq\widetilde{\mathcal{C}}$ such that no two sets
in $\mathcal{C}^{\prime}$ touch each other and
$\sum_{C\in\mathcal{C}^{\prime}}\textnormal{{w}}(C)=W$.

###### Proof.

From Lemma 1, there exists $S\subseteq V(G)$ such that $G[S]$ is bipartite,
the weight of $S$ (with respect to w) is maximum, and all the connected
components of $G[S]$ are contained in $\widetilde{\mathcal{C}}$. Therefore $S$
corresponds to a pairwise non-touching sub-collection of
$\widetilde{\mathcal{C}}$ of total weight equal to $\textnormal{{w}}(S)$. For
the other direction, since every set in $\widetilde{\mathcal{C}}$ is connected
and bipartite, we conclude that the union of the sets in any sub-collection of
$\widetilde{\mathcal{C}}$, that contains no two sets that touch each other,
forms an induced bipartite subgraph of $G$. ∎

Let $G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}}$ be an auxiliary graph
whose vertex set corresponds to sets in $\widetilde{\mathcal{C}}$ and there is
an edge between two vertices of
$G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}}$ if and only if the
corresponding sets touch other. Formally,
$V(G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}})=\\{v_{C}:C\in\widetilde{\mathcal{C}}\\}$
and for any $v_{C},v_{C^{\prime}}\in
V(G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}})$, there exists
$(v_{C},v_{C^{\prime}})\in
E(G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}})$ if and only if $C$ and
$C^{\prime}$ touch each other. Let
$\textnormal{{w}}^{\textnormal{{blob}}}:V(G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}})\to\mathbb{Q}$
be defined as follows:
$\textnormal{{w}}^{\textnormal{{blob}}}(v_{C})=\sum_{u\in
C}\textnormal{{w}}(u)$. In the vocabulary of Gartland et al. [GLP+21],
$G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}}$ is an induced subgraph of
_the blob graph of $G$_, and they observe that the blob graph (and thus its
every induced subgraph) of a $P_{5}$-free graph is $P_{5}$-free.

######  Proposition 4.1 (Theorem $4.1$, [GLP+21]).

If $G$ is $P_{5}$-free, then
$G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}}$ is also $P_{5}$-free.

The following lemma is an immediate consequence of Lemma 4.

######  Lemma 5.

$(G,\textnormal{{w}})$ has an induced bipartite subgraph of weight (with
respect to the weight function w) $W$ if and only if
$G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}}$ has an independent set of
weight $W$, with respect to the weight function
$\textnormal{{w}}^{\textnormal{{blob}}}$.

From Proposition 4.1, if $G$ is $P_{5}$-free, then
$G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}}$ is also $P_{5}$-free. So
by Lemma 5, the problem actually reduces to finding a maximum weight
independent set in a $P_{5}$-free graph, which can be done by [LVV14]. Now we
are ready to prove our main result, i.e., Theorem 1.

###### Proof of Theorem 1.

Let $(G,\textnormal{{w}})$ be an instance of OCT. Construct an instance
$(G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}},\textnormal{{w}}^{\textnormal{{blob}}})$
as described earlier. Note that the number of vertices of
$G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}}$ is
$|\widetilde{\mathcal{C}}|$, which is at most $|\mathcal{C}|$ times the
maximum number of connected components of any subgraph induced by an element
of $\mathcal{C}$. Since $|\mathcal{C}|=\mathcal{O}(n^{6})$ by Lemma 1, the
number of vertices of $G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}}$ is
$\mathcal{O}(n^{7})$. Also the construction of this graph takes time
polynomial in $n$.

Thus, by Lemma 5, the problem reduces to finding a maximum-weight independent
set in a $P_{5}$-free graph
$G^{\textnormal{{blob}}}_{\widetilde{\mathcal{C}}}$. A maximum-weight
independent set on $P_{5}$-free graphs can be found in polynomial time using
the algorithm of [LVV14] (Proposition 3.1). This concludes the proof of
Theorem 1. ∎

##  5 Conclusion

We gave a polynomial-time algorithm for OCT on $P_{5}$-free graphs. Several
interesting problems in this direction remain open.

  1. 1.

The algorithms for Independent Set on $P_{t}$-free graphs [GL20, PPR21] also
work for counting the number of independent sets of a given size within the
same time bound. Because of the “greedy choice” implicit in the statement of
Lemma 1, our algorithm does not work for counting the number of induced
bipartite subgraphs of a given size. Does a polynomial (or quasi-polynomial)
time algorithm exist for this problem in $P_{5}$-free graphs?

  2. 2.

For every fixed positive integer $k$ we can determine whether $G$ is
$k$-colorable in polynomial time on $P_{5}$-free graphs [HKL+10]. Therefore,
in light of Theorem 1 it makes sense to ask whether for every positive integer
$k$ there exists a polynomial- or quasi-polynomial-time algorithm that takes
as input a graph $G$ and outputs a maximum-size (or maximum-weight) set $S$
such that $G[S]$ is $k$-colorable. The work of Chudnovsky et al. [CKP+21]
provides a subexponential-time algorithm for this problem (and, actually, its
further generalizations).

  3. 3.

Our result completes the classification of all connected graphs $H$ into ones
such that OCT on $H$-free graphs is polynomial time solvable or NP-complete.
Such a classification for all graphs $H$ (connected or not) remains open. Even
more generally, one could hope for a complete classification of the complexity
of OCT on ${\cal F}$-free graphs for every _finite_ set ${\cal F}$.

## References

  * [AI16] Takuya Akiba and Yoichi Iwata.  Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover.  Theor. Comput. Sci., 609:211–225, 2016.
  * [BDF+19] Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma.  Independent feedback vertex set for p${}_{\mbox{5}}$-free graphs.  Algorithmica, 81(4):1342–1369, 2019.
  * [BK85] Andreas Brandstädt and Dieter Kratsch.  On the restriction of some NP-complete graph problems to permutation graphs.  In Lothar Budach, editor, Fundamentals of Computation Theory, pages 53–62, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg.
  * [BS+99] Andreas Brandstädt, Jeremy P Spinrad, et al.  Graph classes: a survey.  Number 3. Siam, 1999.
  * [BT90] Gábor Bacsó and Zs Tuza.  Dominating cliques in ${P}_{5}$-free graphs.  Periodica Mathematica Hungarica, 21(4):303–308, 1990.
  * [BXTV13] Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle.  Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems.  Theoretical Computer Science, 511:66–76, 2013.  Exact and Parameterized Computation.
  * [CHJ+18] Nina Chiarelli, Tatiana R. Hartinger, Matthew Johnson, Martin Milanič, and Daniël Paulusma.  Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity.  Theoretical Computer Science, 705:75–83, 2018.
  * [CKP+21] Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rząėwski, and Sophie Spirkl.  Finding large $H$-colorable subgraphs in hereditary graph classes.  SIAM J. Discret. Math., 35(4):2357–2386, 2021.
  * [CPS19] Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt.  Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271).  Dagstuhl Reports, 9(6):125–142, 2019.
  * [DFJ+20] Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski.  On cycle transversals and their connected variants in the absence of a small linear forest.  Algorithmica, 82:2841–2866, 2020.
  * [Die12] Reinhard Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [DR+16] H.N. De Ridder et al.  Information system on graph classes and their inclusions.  www.graphclasses.org, 2016.
  * [FHRV07] Samuel Fiorini, Nadia Hardy, Bruce A. Reed, and Adrian Vetta.  Approximate min-max relations for odd cycles in planar graphs.  Math. Program., 110(1):71–91, 2007.
  * [Gal67] Tibor Gallai.  Transitiv orientierbare graphen.  Acta Mathematica Hungarica, 18(1-2):25–66, 1967.
  * [GL20] Peter Gartland and Daniel Lokshtanov.  Independent set on $\mathrm{P}_{k}$-free graphs in quasi-polynomial time.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 613–624, 2020.
  * [GLP+21] Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski.  Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 330–341. Association for Computing Machinery, 2021.
  * [GW98] Michel X. Goemans and David P. Williamson.  Primal-dual approximation algorithms for feedback problems in planar graphs.  Comb., 18(1):37–59, 1998.
  * [HKL+10] Chính T. Hoàng, Marcin Kaminski, Vadim V. Lozin, Joe Sawada, and Xiao Shu.  Deciding _k_ -colorability of _P_ ${}_{\mbox{5}}$-free graphs in polynomial time.  Algorithmica, 57(1):74–81, 2010.
  * [Hüf09] Falk Hüffner.  Algorithm engineering for optimal graph bipartization.  J. Graph Algorithms Appl., 13(2):77–98, 2009.
  * [IOY14] Yoichi Iwata, Keigo Oka, and Yuichi Yoshida.  Linear-time FPT algorithms via network flow.  In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1749–1761. SIAM, 2014.
  * [JBDP21] Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk.  Close relatives (of feedback vertex set), revisited.  In 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-10, 2021, Lisbon, Portugal, volume 214 of LIPIcs, pages 21:1–21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [JK11] Bart M. P. Jansen and Stefan Kratsch.  On polynomial kernels for structural parameterizations of odd cycle transversal.  In Dániel Marx and Peter Rossmanith, editors, Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers, volume 7112 of Lecture Notes in Computer Science, pages 132–144. Springer, 2011.
  * [KMRS20] Sudeshna Kolay, Pranabendu Misra, M. S. Ramanujan, and Saket Saurabh.  Faster graph bipartization.  J. Comput. Syst. Sci., 109:45–55, 2020.
  * [KR02] Subhash Khot and Venkatesh Raman.  Parameterized complexity of finding subgraphs with hereditary properties.  Theor. Comput. Sci., 289(2):997–1008, 2002.
  * [KR10] Ken-ichi Kawarabayashi and Bruce A. Reed.  An (almost) linear time algorithm for odd cyles transversal.  In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 365–378. SIAM, 2010.
  * [KSS12] Daniel Král’, Jean-Sébastien Sereni, and Ladislav Stacho.  Min-max relations for odd cycles in planar graphs.  SIAM J. Discret. Math., 26(3):884–895, 2012.
  * [KW14] Stefan Kratsch and Magnus Wahlström.  Compression via matroids: A randomized polynomial kernel for odd cycle transversal.  ACM Trans. Algorithms, 10(4):20:1–20:15, 2014.
  * [LNR+14] Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh.  Faster parameterized algorithms using linear programming.  ACM Trans. Algorithms, 11(2):15:1–15:31, 2014.
  * [LSS09] Daniel Lokshtanov, Saket Saurabh, and Somnath Sikdar.  Simpler parameterized algorithm for OCT.  In Combinatorial Algorithms, 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28-July 2, 2009, Revised Selected Papers, volume 5874 of Lecture Notes in Computer Science, pages 380–384. Springer, 2009.
  * [LSW12] Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlström.  Subexponential parameterized odd cycle transversal on planar graphs.  In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, volume 18 of LIPIcs, pages 424–434. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012.
  * [LVV14] Daniel Lokshtanov, Martin Vatshelle, and Yngve Villanger.  Independent set in _P_ ${}_{\mbox{5}}$-free graphs in polynomial time.  In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 570–581. SIAM, 2014.
  * [LY80] John M. Lewis and Mihalis Yannakakis.  The node-deletion problem for hereditary properties is NP-complete.  Journal of Computer and System Sciences, 20(2):219–230, 1980.
  * [OR20] Karolina Okrasa and Paweł Rzążewski.  Subexponential algorithms for variants of the homomorphism problem in string graphs.  Journal of Computer and System Sciences, 109:126–144, 2020.
  * [PPR21] Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski.  Quasi-polynomial-time algorithm for independent set in _P ${}_{\mbox{t}}$_-free graphs via shrinking the space of induced paths.  In Hung Viet Le and Valerie King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 204–209. SIAM, 2021.
  * [RSS07] Venkatesh Raman, Saket Saurabh, and Somnath Sikdar.  Efficient exact algorithms through enumerating maximal independent sets and other techniques.  Theory Comput. Syst., 41(3):563–587, 2007.
  * [RSV04] Bruce A. Reed, Kaleigh Smith, and Adrian Vetta.  Finding odd cycle transversals.  Oper. Res. Lett., 32(4):299–301, 2004.
  * [TM18] Yotaro Takazawa and Shinji Mizuno.  On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem.  CoRR, abs/1807.10277, 2018.


# On periodicity of a meromorphic function when sharing two sets IM

Molla Basir Ahamed  Department of Mathematics, Kalipada Ghosh Tarai
Mahavidyalya, West Bengal, 734014, India<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In this paper, we have investigated the sufficient conditions for periodicity
of meromorphic functions and obtained two results directly improving the
result of _Bhoosnurmath-Kabbur_ [4], _Qi-Dou-Yang_ [15] and _Zhang_ [18]. Let
$\mathcal{S}_{1}=\left\\{z:\displaystyle\int_{0}^{z-a}(t-a)^{n}(t-b)^{4}dt+1=0\right\\}$
and $\mathcal{S}_{2}=\bigg{\\{}a,b\bigg{\\}}$, where $n\geqslant 4(n\geqslant
3)$ be an integer._Let $f(z)$ be a non-constant meromorphic (entire) function
satisfying
$\overline{E}_{f(z)}(\mathcal{S}_{j})=\overline{E}_{f(z+c)}(\mathcal{S}_{j}),(j=1,\;2)$
then $f(z)\equiv f(z+c)$._ Some examples have been exhibited to show that, it
is not necessary that meromorphic function should be of finite order and also
to show that the sets considered in the paper simply can’t be replace by
arbitrary sets. At the last section, we have posed an open question for the
further improvement of the results of this paper.

###### Key words and phrases:

Meromorphic function, uniqueness, shared sets, finite order, shift operator.

###### 2010 Mathematics Subject Classification:

Primary 30D35.

##  1\. Introduction, Definitions and Results

We assume that the reader is familiar with the elementary Nevanlinna theory,
see, e.g., [9, 11, 12, 16]. Meromorphic functions are always non-constant,
unless otherwise specified. For such a function $f$ and
$a\in\mathbb{\overline{C}}=:\mathbb{C}\cup\\{\infty\\}$, each $z$ with
$f(z)=a$ will be called $a$-point of $f$. We will use here some standard
definitions and basic notations from this theory. In particular by $N(r,a;f)$
($\overline{N}(r,a;f)$) we denote the counting function (reduced counting
function) of $a$-points of meromorphic functions $f$, $T(r,f)$ is the
Nevanlinna characteristic function of $f$ and $S(r,f)$ is used to denote each
functions which is of smaller order than $T(r,f)$ when $r\rightarrow\infty$.

We also denote $\mathbb{C^{*}}:=\mathbb{C}\smallsetminus\\{0\\}$. As for the
standard notation in the uniqueness theory of meromorphic functions, suppose
that $f$ and $g$ are meromorphic. Denoting $E_{f}(a)$ $(\overline{E}_{f}(a))$,
the set of all $a$-points of $f$ counting multiplicities (ignoring
multiplicities). We say that two meromorphic functions $f$, $g$ share the
value $a$ $CM$ $(IM)$ if $E_{f}(a)=E_{g}(a)$
$(\overline{E}_{f}(a)=\overline{E}_{g}(a))$.

The classical results in the uniqueness theory of meromorphic functions are
the five-point, resp. four-point, theorems due to Nevanlinna [14]: If two
meromorphic functions $f$, $g$ share five distinct values in the extended
complex plane $IM$, then $f\equiv g$. The beauty of this result lies in the
fact that there is no counterpart of this result in the real function theory.
Similarly, if two meromorphic functions $f,\;g$ share four distinct values in
the extended complex plane $CM$, then $f\equiv T\circ g$, where $T$ is a
Möbius transformation.

Clearly these results initiated the study of uniqueness of two meromorphic
functions $f$ and $g$. The study becomes more interesting if the function $g$
is related with $f$.

######  Definition 1.1.

For a non-constant meromorphic function $f$ and any set
$\mathcal{S}\subset\mathbb{\overline{C}}$, we define

$\displaystyle
E_{f}(\mathcal{S})=\displaystyle\bigcup_{a\in\mathcal{S}}\bigg{\\{}(z,p)\in\mathbb{C}\times\mathbb{N}:f(z)=a,\;\text{with
multiplicity}\;p\bigg{\\}},$
$\displaystyle\overline{E}_{f}(\mathcal{S})=\displaystyle\bigcup_{a\in\mathcal{S}}\bigg{\\{}(z,1)\in\mathbb{C}\times\\{1\\}:f(z)=a\bigg{\\}}.$

If $E_{f}(\mathcal{S})=E_{g}(\mathcal{S})$
($\overline{E}_{f}(\mathcal{S})=\overline{E}_{g}(\mathcal{S})$) then we simply
say $f$ and $g$ share $\mathcal{S}$ Counting Multiplicities(CM) (Ignoring
Multiplicities(IM)).

Evidently, if $\mathcal{S}$ contains one element only, then it coincides with
the usual definition of $CM(IM)$ sharing of values.

######  Definition 1.2.

For a non-constant meromorphic function $g$ and $a\in\mathbb{C}$, we define
$\overline{N}_{(2}\left(r,\displaystyle\frac{1}{g-a}\right)$ the reduced
counting function of those $a$-points of $g$ of multiplicities $\geqslant 2$.

In $1976$, _Gross_ [10] precipitated the research instigating the set sharing
problem with a more general set up made tracks various direction of research
for the uniqueness theory.

In connection with the question posed by _Gross_ in[10], a sprinkling number
of results have been obtained by many mathematicians [1, 2, 3, 7, 17, 19]
concerning the uniqueness of meromorphic functions sharing two sets. But in
most of the preceding results, in the direction, one set has always been kept
fixed as the set of poles of a meromorphic function.

Recently set sharing corresponding to a function and its shift or difference
operator have been given priority by the researchers than that of the
introductory one.

In what follows, $c$ always means a non-zero constant. For a non-constant
meromorphic function, we define its shift and difference operator respectively
by $f(z+c)$ and $\Delta_{c}f=f(z+c)-f(z)$.

Now-a-days among the researchers [4, 5, 6, 15, 18], an increasing amount of
interest has been found to find the possible relationship between a
meromorphic function $f(z)$ and its shift $f(z+c)$ or its difference
$\Delta_{c}f$.

At the earlier stage, several authors were devoted to find uniqueness problems
between two meromorphic functions $f$ and $g$ sharing two sets. But in this
particular direction, the first inspection for uniqueness of a meromorphic
function and its shift was due to _Zhang_ [18].

In 2010, _Zhang_ [18] obtained the following results.

######  Theorem A.

[18] Let $m\geqslant 2$, $n\geqslant 2m+4$ with $n$ and $n-m$ having no common
factors. Let $a$ and $b$ be two non-zero constant such that the equation
$w^{n}+aw^{n-m}+b=0$ has no multiple roots. Let
$\mathcal{S}_{1}=\\{w:w^{n}+aw^{n-m}+b=0\\}$ and
$\mathcal{S}_{2}=\\{\infty\\}$. Suppose that $f(z)$ is a non-constant
meromorphic function of finite order. Then
$E_{f(z)}(\mathcal{S}_{j})=E_{f(z+c)}(\mathcal{S}_{j})$ $(j=1,\;2)$ imply that
$f(z)\equiv f(z+c)$.

######  Remark 1.1.

For meromorphic function, note that $\\#(\mathcal{S}_{1})=9$ when the nature
of sharing is $CM$.

######  Theorem B.

[18] Let $n\geqslant 5$ be an integer and let $a$, $b$ be two non-zero
constants such that the equation $w^{n}+aw^{n-1}+b=0$ has no multiple roots.
Denote $\mathcal{S}_{1}=\\{w:w^{n}+aw^{n-1}+b=0\\}$. Suppose that $f$ is a
non-constant entire function of finite order. Then
$E_{f(z)}(\mathcal{S}_{1})=E_{f(z+c)}(\mathcal{S}_{1})$ implies $f(z)\equiv
f(z+c)$.

######  Remark 1.2.

For entire function, note that $\\#(\mathcal{S}_{1})=5$, when the nature of
sharing is $CM$.

Thus we see that _Zhang_ obtained the results for meromorphic function with
the cardinality of main range set as $9$ and for entire function as $5$.

Later, _Qi-Dou-Yang_ [15] studied the case for $m=1$ in _Theorem A_ and with
the aid of some extra supposition and got $\\#(\mathcal{S}_{1})=6$ when the
nture of sharing is $CM$.

Afterworlds, _Bhoosnurmath-Kabbur_ [4] improved _Theorem A_ by reducing the
lower bound of the cardinality of range set in a little different way and
obtained the following result.

######  Theorem C.

[4] Let $n\geqslant 8$ be an integer and $c(\neq 0,\;1)$ is a constant such
that the equation
$P(w)=\displaystyle\frac{(n-1)(n-2)}{2}w^{n}-n(n-2)w^{n-1}+\frac{n(n-1)}{2}z^{n-2}-c$.
Let us suppose that $S_{1}=\\{w:P(w)=0\\}$ and $S_{2}=\\{\infty\\}$. Suppose
that $f(z)$ is a non-constant meromorphic function of finite order. Then
$E_{f(z)}(\mathcal{S}_{j})=E_{f(z+c)}(\mathcal{S}_{j})$ $(j=1,\;2)$ imply that
$f(z)\equiv f(z+c)$.

######  Remark 1.3.

For meromorphic function, we see that $\\#(\mathcal{S}_{1})=8$ when the nature
of sharing is $CM$.

The worth noticing fact is that, the lower bound of the cardinality of the
main range set for the meromorphic function has always been fixed to $8$
without the help of any extra supposition.

So for the improvement of all the above mentioned results it quite natural to
investigate in this direction. _Theorems A, B, C_ really motivates oneself for
further study in this direction by solving the following question.

######  Question 1.1.

Is it possible to diminish further the lower bound of the cardinalities of the
main range sets in _Theorem A_ , _B_ and _C_ ?

We also note that no attempts have so far been made by any researchers, till
now to the best of our knowledge, to relax the nature of sharing the sets. So
the following question is inevitable.

######  Question 1.2.

Can we relax the nature of sharing the sets from $CM$ to $IM$ in _Theorem A_ ,
_B_ and _C_ ?

Now it would be interesting to know what happens if we replace the set of
poles $\\{\infty\\}$ by new set in _Theorems A, B, C_.

In all the above mentioned results, the respective authors have considered
meromorphic function with _finite ordered_ and got their results. So a natural
investigation query is that: Are _Theorems A, B, C_ not valid for infinite
ordered meromorphic function ?

The following examples show that _Theorems A, B, C_ are true for infinite
ordered meromorphic functions also.

######  Example 1.1.

Let $f(z)=\displaystyle\exp\left(1+\sin\left(\frac{2\pi z}{c}\right)\right)$.
Clearly $f(z)$ and $f(z+c)$ share the corresponding sets $\mathcal{S}_{1}$ in
_Theorems A, B, C_ and also the set $\mathcal{S}_{2}$ and hence holds the
conclusion also.

######  Example 1.2.

Let $f(z)=\displaystyle\exp\left(1+\exp\left(\displaystyle\frac{2\pi
iz}{c}\right)\right)$.

One can construct such examples plenty in numbers. Therefore, one natural
question arises as follows:

######  Question 1.3.

Can we get a corresponding results like _Theorem A, B, C_ by omitting the term
_finite ordered_ ?

Answering all the questions affirmatively is the main motivation of writing
this paper. In this paper, we have significantly diminished the cardinality of
the main range set by modifying the set of poles by a new one. We have
successfully relaxed the nature of sharing also.

Throughout the paper, for an integer $n\geqslant 4$, we will denote by

$\displaystyle\mathcal{P}(z)=\displaystyle\int_{0}^{z-a}(t-a)^{n}(t-b)^{4}dt+1,\;\;\text{where}\;\;a,b\in\mathbb{C}\;\;\text{with}\;\;a\neq
b.$

Following are the two main result of this paper.

######  Theorem 1.1.

Let $\mathcal{S}_{1}=\left\\{z:\mathcal{P}(z)=0\right\\}$ and
$\mathcal{S}_{2}=\bigg{\\{}a,b\bigg{\\}}$, where $a\in\mathbb{C^{*}}$,
$n\geqslant 4$ be an integer. Let $f(z)$ be a non-constant meromorphic
function satisfying
$\overline{E}_{f(z)}(\mathcal{S}_{j})=\overline{E}_{f(z+c)}(\mathcal{S}_{j}),$
$(j=1,\;2)$ then $f(z)\equiv f(z+c)$.

######  Remark 1.4.

For non-entire meromorphic function, one may observe that
$\\#(\mathcal{S}_{1})=9$ when the nature of sharing is $IM$.

######  Theorem 1.2.

Let $\mathcal{S}_{1}=\left\\{z:\mathcal{P}(z)=0\right\\}$ and
$\mathcal{S}_{2}=\bigg{\\{}a,b\bigg{\\}}$, where $a\in\mathbb{C^{*}}$,
$n\geqslant 2$ be an integer. Let $f(z)$ be a non-constant entire function
satisfying
$\overline{E}_{f(z)}(\mathcal{S}_{j})=\overline{E}_{f(z+c)}(\mathcal{S}_{j}),$
$(j=1,\;2)$ then $f(z)\equiv f(z+c)$.

######  Remark 1.5.

For entire function, we see that $\\#(\mathcal{S}_{1})=7$ when the nature of
sharing is $IM$.

The following examples satisfy _Theorems 1.1_ and _1.2_ for “entire” as well
as “ meromorphic” functions.

######  Example 1.3.

Let us suppose that
$f(z)=\displaystyle\left(\displaystyle\frac{\tan\left(\displaystyle\frac{\pi
z}{c}\right)+\alpha}{\tan\left(\displaystyle\frac{\pi
z}{c}\right)-\beta}\right)+\displaystyle\frac{\cos\left(\displaystyle\frac{2\pi
z}{c}\right)+\gamma}{\sin\left(\displaystyle\frac{2\pi z}{c}\right)-\delta}$,
where $\alpha,\;\beta,\;\gamma,\;\delta,\;c\in\mathbb{C^{*}}$. It is clear
that
$\overline{E}_{f(z)}(\mathcal{S}_{j})=\overline{E}_{f(z+c)}(\mathcal{S}_{j}),$
$(j=1,\;2)$ in _Theorem 1.1_ and note that $f(z)\equiv f(z+c)$.

######  Example 1.4.

Let $f(z)=\displaystyle\frac{\alpha+\beta\displaystyle\sin^{2}\left(\frac{\pi
z}{c}\right)}{\gamma-\delta\displaystyle\cos^{2}\left(\frac{\pi
z}{c}\right)},$ where $p$ be an even positive integer,
$\alpha,\;\beta,\;\gamma,\;\delta,\;c\in\mathbb{C^{*}}$. It is clear that
$\overline{E}_{f(z)}(\mathcal{S}_{j})=\overline{E}_{f(z+c)}(\mathcal{S}_{j}),$
$(j=1,\;2)$ in _Theorem 1.1_ and note that $f(z)\equiv f(z+c)$.

######  Example 1.5.

Let $f(z)=ae^{pz}+b\displaystyle\cos^{2}\left(\frac{\pi z}{c}\right),$ where
$p$ be an even positive integer, $a,\;,b\;,c\in\mathbb{C^{*}}$ with
$e^{c}=-1$. It is clear that
$\overline{E}_{f(z)}(\mathcal{S}_{j})=\overline{E}_{f(z+c)}(\mathcal{S}_{j}),$
$(j=1,\;2)$ in _Theorem 1.2_ and note that $f(z)\equiv f(z+c)$.

The next examples shows that the set considered in _Theorem 1.1_ for “entire”
and _Theorem 1.2_ for “meromorphic” functions respectively can not be replaced
by arbitrary sets.

######  Example 1.6.

Let us suppose that $\mathcal{S}_{1}=\\{\zeta:\zeta^{9}-1=0\\}$ and
$\mathcal{S}_{2}=\\{0,\infty\\}$. Let
$f(z)=\displaystyle\frac{ae^{z}}{b-d\sin^{2}\left(\displaystyle\frac{\pi
z}{c}\right)}$. It is clear that
$\overline{E}_{f(z)}(\mathcal{S}_{j})=\overline{E}_{f(z+c)}(\mathcal{S}_{j}),$
$(j=1,\;2)$ in _Theorem 1.1_ with $e^{c}=\zeta$ and
$a,\;b,\;c,\;d\in\mathbb{C^{*}}$ and note that $f(z)\not\equiv f(z+c)$.

######  Example 1.7.

Let us suppose that $\mathcal{S}_{1}=\\{\zeta:\zeta^{7}-1=0\\}$ and
$\mathcal{S}_{2}=\\{0,1\\}$. Let
$f(z)=\displaystyle\exp\left(\cos\left(\frac{\pi z}{c}\right)\right)$ or
$\displaystyle\exp\left(\sin\left(\frac{\pi z}{c}\right)\right)$. Then
$f(z+c)=\displaystyle\exp\left(-\cos\left(\frac{\pi z}{c}\right)\right)$ or
$\displaystyle\exp\left(-\sin\left(\frac{\pi z}{c}\right)\right)$
respectively. It is clear that
$\overline{E}_{f(z)}(\mathcal{S}_{j})=\overline{E}_{f(z+c)}(\mathcal{S}_{j}),$
$(j=1,\;2)$ in _Theorem 1.2_ and note that $f(z)\not\equiv f(z+c)$.

######  Example 1.8.

Let
$\mathcal{S}_{1}=\bigg{\\{}-1,\;1,\;-i,\;0,\;i,\;-\displaystyle\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\bigg{\\}}$
and $\mathcal{S}_{2}=\\{-2,\;2\\}$. Let $f(z)=e^{z}$. It is clear that
$\overline{E}_{f(z)}(\mathcal{S}_{j})=\overline{E}_{f(z+c)}(\mathcal{S}_{j}),$
$(j=1,\;2)$ in _Theorem 1.2_ with $e^{c}=-1$, $c\in\mathbb{C^{*}}$ and note
that $f(z)\not\equiv f(z+c)$.

##  2\. Auxiliary sefinitions and Some Lemmas

It was _Fujimoto_ [8], who first discovered a special property of a
polynomial, reasonably called as critical injection property though initially
_Fujimoto_ [8] called it as property (H).

######  Definition 2.1.

Let $\mathcal{P}(w)$ be a non-constant monic polynomial. We call
$\mathcal{P}(w)$ a uniqueness polynomial if $\mathcal{P}(f)\equiv
c\mathcal{P}(g)$ implies $f\equiv g$ for any non-constant meromorphic
functions $f$ and $g$ and any non-zero constant $c$. We also call
$\mathcal{P}(w)$ a uniqueness polynomial in a broad sense if
$\mathcal{P}(f)\equiv\mathcal{P}(g)$ implies $f\equiv g$.

Next we recall here the property (H) and critically injective polynomial.

Let $\mathcal{P}(w)$ be a monic polynomial without multiple zero whose
derivative has mutually distinct $k$-zeros $e_{1},e_{2},\ldots,e_{k}$ with the
multiplicities $q_{1},q_{2},\ldots,q_{k}$ respectively.

Now, the property $\mathcal{P}(e_{l})\neq\mathcal{P}(e_{m})$ for $1\leqslant
l<m\leqslant k$ is a known as property (H) and a polynomial $\mathcal{P}(w)$
satisfying this property is called critically injective polynomial.

Given meromorphic functions $f(z)$ and $f(z+c)$ we associate $\mathcal{F}$,
$\mathcal{G}$ by

(2.1) $\mathcal{F}=\mathcal{P}(f),\;\;\mathcal{G}=\mathcal{P}(f(z+c)),$

to $\mathcal{F}$, $\mathcal{G}$ we associate $\mathcal{H}$ and $\Phi$ by the
following formulas

(2.2) $\displaystyle\mathcal{H}$ $\displaystyle=$
$\displaystyle\frac{\left(\displaystyle\frac{1}{\mathcal{F}}\right)^{\prime\prime}}{\left(\displaystyle\frac{1}{\mathcal{F}}\right)^{\prime}}-\frac{\left(\displaystyle\frac{1}{\mathcal{G}}\right)^{\prime\prime}}{\left(\displaystyle\frac{1}{\mathcal{G}}\right)^{\prime}}=\left(\frac{\;\;\mathcal{F}^{\prime\prime}}{\mathcal{F}^{\prime}}-\frac{2\mathcal{F}^{\prime}}{\mathcal{F}}\right)-\left(\frac{\;\;\mathcal{G}^{\prime\prime}}{\mathcal{G}^{\prime}}-\frac{2\mathcal{G}^{\prime}}{\mathcal{G}}\right),$
(2.3)
$\displaystyle\Phi=\frac{\mathcal{F}^{\prime}}{\mathcal{F}}-\frac{\mathcal{G}^{\prime}}{\mathcal{G}}.$

Before proceeding to the actual proofs, we recall a few lemmas that take an
important role in the reasoning.

######  Lemma 2.1.

[13] Let $g$ be a non-constant meromorphic function and let

$\displaystyle\mathcal{R^{\\#}}(g)=\displaystyle\frac{\displaystyle\sum_{i=1}^{n}a_{i}g^{i}}{\displaystyle\sum_{j=1}^{m}b_{j}g^{j}},$

be an irreducible rational function in $g$ with constant coefficients
$\\{a_{i}\\}$, $\\{b_{j}\\}$, where $a_{n}\neq 0$ and $b_{m}\neq 0$. Then

$\displaystyle T(r,\mathcal{R^{\\#}}(g))=\max\\{n,m\\}\;T(r,g)+S(r,g).$

######  Lemma 2.2.

[8] Let $\mathcal{P}(w)$ be a polynomial satisfying the property _(H)_. Then,
$\mathcal{P}(w)$ is a uniqueness polynomial in a broad sense if and only if

(2.4) $\displaystyle\sum_{1\leqslant l<m\leqslant
k}q_{{}_{l}}q_{{}_{m}}>\sum_{l=1}^{k}q_{{}_{l}}.$

It can be easily verified that for the case $k\geqslant 4$, the condition
(2.4) is always satisfied. Moreover, (2.4) holds when
$\max\\{q_{1},q_{2},q_{3}\\}\geqslant 2$ for the case $k=3$ and when
$\min\\{q_{1},q_{2}\\}\geqslant 2$ and $q_{1}+q_{2}\geqslant 5$ for the case
$k=2$.

##  3\. Proofs of the theorems

In this section, we give the proofs of our main results.

###### Proof of Theorem 1.1.

let $f(z)$ and $f(z+c)$ be any two non-constant meromorphic functions. It is
clear that

$\displaystyle\mathcal{F}^{\prime}=(f(z)-a)^{n}(f(z)-b)^{4}f^{\prime}(z)\;\;\text{and}\;\;\mathcal{G}^{\prime}=(f(z+c)-a)^{n}(f(z+c)-b)^{4}f^{\prime}(z+c).$

We now discuss the following two cases:

Case 1. There exists a $\lambda>1$, $I\subset\mathbb{R}^{+}$ with measure of
$I$ as $+\infty$ such that

$\displaystyle
2\overline{N}\left(r,\frac{1}{f(z)-a}\right)+2\overline{N}\left(r,\frac{1}{f(z)-b}\right)$
$\displaystyle\geqslant$
$\displaystyle\lambda\bigg{\\{}T(r,f(z))+T(r,f(z+c))\bigg{\\}}+S(r,f(z))+S(r,f(z+c)),\;\;(r\rightarrow+\infty,r\in
I).$

Let $\Phi$ is defined as in (2.3). Our aim is to show that $\Phi=0$. Let if
possible $\Phi\not\equiv 0$. Then since $n\geqslant 4$, so from the
construction of $\Phi$, we get

(3.2) $\displaystyle
4\overline{N}\left(r,\frac{1}{f(z)-a}\right)+4\overline{N}\left(r,\frac{1}{f(z)-b}\right)\leqslant
N\left(r,\frac{1}{\Phi}\right).$

The possible poles of $\phi$ occur at the following points: (i) poles of
$f(z)$, (ii) poles of $f(z+c)$, (iii) all the zeros of $\mathcal{F}$ of
multiplicities $\geqslant 2$ and (iv) all the zeros of $\mathcal{G}$ of
multiplicities $\geqslant 2$.

So we have

(3.3) $\displaystyle
N(r,\Phi)\leqslant\overline{N}(r.f(z))+\overline{N}_{(2}\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}(r.f(z+c))+\overline{N}_{(2}\left(r,\frac{1}{\mathcal{G}}\right).$

By using _First Fundamental Theorem_ and (3.2), (3.3), we get

$\displaystyle
4\overline{N}\left(r,\frac{1}{f(z)-a}\right)+4\overline{N}\left(r,\frac{1}{f(z)-b}\right)$
$\displaystyle\leqslant$ $\displaystyle N\left(r,\frac{1}{\Phi}\right)$
$\displaystyle\leqslant$ $\displaystyle N(r,\Phi)$ $\displaystyle\leqslant$
$\displaystyle\overline{N}(r.f(z))+\overline{N}_{(2}\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}(r.f(z+c))+\overline{N}_{(2}\left(r,\frac{1}{\mathcal{G}}\right)$
$\displaystyle+S(r,f(z))+S(r,f(z+c)).$

Again since
$\overline{E}_{f(z)}(\mathcal{S}_{2})=\overline{E}_{f(z+c)}(\mathcal{S}_{2})$,
so we must have

$\displaystyle\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)$
$\displaystyle=$
$\displaystyle\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)+\overline{N}\left(r,\frac{1}{f(z+c)-b}\right).$

Now adding
$\overline{N}\left(r,\displaystyle\frac{1}{\mathcal{F}}\right)+\overline{N}\left(r,\displaystyle\frac{1}{\mathcal{G}}\right)$
on both sides of (3), we get

$\displaystyle
4\overline{N}\left(r,\frac{1}{f(z)-a}\right)+4\overline{N}\left(r,\frac{1}{f(z)-b}\right)+\overline{N}\left(r,\displaystyle\frac{1}{\mathcal{F}}\right)+\overline{N}\left(r,\displaystyle\frac{1}{\mathcal{G}}\right)$
$\displaystyle\leqslant$
$\displaystyle\overline{N}(r.f(z))+N\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}(r.f(z+c))+N\left(r,\frac{1}{\mathcal{G}}\right)$
$\displaystyle+S(r,f(z))+S(r,f(z+c)).$

Next using (3) in (3), we get

$\displaystyle\bigg{\\{}\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)\bigg{\\}}+2\bigg{\\{}\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)\bigg{\\}}$
$\displaystyle+\bigg{\\{}\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)+\overline{N}\left(r,\frac{1}{f(z+c)-b}\right)\bigg{\\}}+\overline{N}\left(r,\displaystyle\frac{1}{\mathcal{F}}\right)+\overline{N}\left(r,\displaystyle\frac{1}{\mathcal{G}}\right)$
$\displaystyle\leqslant$
$\displaystyle\overline{N}(r.f(z))+N\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}(r.f(z+c))+N\left(r,\frac{1}{\mathcal{G}}\right)+S(r,f(z))$
$\displaystyle+S(r,f(z+c)).$

By applying _Second Fundamental Theorem_ , we get

$\displaystyle(n+5)\bigg{\\{}T(r,f(z))+T(r,f(z+c))\bigg{\\}}$
$\displaystyle\leqslant$
$\displaystyle\overline{N}\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)+\overline{N}\left(r,\frac{1}{\mathcal{G}}\right)$
$\displaystyle+\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)+\overline{N}\left(r,\frac{1}{f(z+c)-b}\right)+S(r,f(z))+S(r,f(z+c)).$

Adding

$\displaystyle
2\overline{N}\left(r,\frac{1}{f(z)-a}\right)+2\overline{N}\left(r,\frac{1}{f(z)-b}\right)$

both sides in (3) and using (3), we get

$\displaystyle(n+5)\bigg{\\{}T(r,f(z))+T(r,f(z+c))\bigg{\\}}+2\overline{N}\left(r,\frac{1}{f(z)-a}\right)+2\overline{N}\left(r,\frac{1}{f(z)-b}\right)$
$\displaystyle\leqslant$ $\displaystyle
N\left(r,\frac{1}{\mathcal{F}}\right)+N\left(r,\frac{1}{\mathcal{G}}\right)+\overline{N}(r,f(z))+\overline{N}(r,f(z+c))+S(r,f(z))+S(r,f(z+c))$
$\displaystyle\leqslant$
$\displaystyle(n+6)\bigg{\\{}T(r,f(z))+T(r,f(z+c))\bigg{\\}}.$

i.e.,

$\displaystyle
2\overline{N}\left(r,\frac{1}{f(z)-a}\right)+2\overline{N}\left(r,\frac{1}{f(z)-b}\right)\leqslant\bigg{\\{}T(r,f(z))+T(r,f(z+c))\bigg{\\}},$

which is not possible for $\lambda>1$ in view of (3).

Thus, we get $\Phi\equiv 0$. i.e., $\mathcal{F}\equiv\mathcal{AG}$, for
$\mathcal{A}\in\mathbb{C}\smallsetminus\\{0\\}$. Using _Lemma 2.1_, we have

(3.9) $\displaystyle T(r,f(z))=T(r,f(z+c))+S(r,f(z)).$

Subcase 1.1. Let $\mathcal{A}\neq 1$.

So from the relation $\mathcal{F}\equiv\mathcal{AG}$, we get

(3.10) $\displaystyle\mathcal{F}-\mathcal{A}\equiv\mathcal{A}(\mathcal{G}-1).$

A simple calculation shows that the polynomial $\mathcal{P}(z)-\mathcal{A}$
has all simple distinct roots and let them be $\sigma_{j}$
$(j=1,2,\ldots,n+5)$ and all $\sigma_{j}\neq a,\;b$. Also we note that the
polynomial $\mathcal{P}(z)-1$ has roots as $a$ of multiplicity $n+1$ and rest
are $\delta_{j}$ $(j=1,2,3,4)$.

Thus we see from (3.10) that

$\displaystyle\sum_{j=1}^{n+5}\overline{N}\left(r,\frac{1}{f(z)-\sigma_{j}}\right)$
$\displaystyle=$
$\displaystyle\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)+\sum_{j=1}^{4}\overline{N}\left(r,\frac{1}{f(z+c)-\delta_{j}}\right).$

Now by using _Second Fundamental Theorem_ and (3.9), we have

$\displaystyle(n+3)T(r,f(z))$ $\displaystyle\leqslant$
$\displaystyle\sum_{j=1}^{n+5}\overline{N}\left(r,\frac{1}{f(z)-\sigma_{j}}\right)+S(r,f(z))$
$\displaystyle\leqslant$
$\displaystyle\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)+\sum_{j=1}^{4}\overline{N}\left(r,\frac{1}{f(z+c)-\delta_{j}}\right)+S(r,f(z))$
$\displaystyle\leqslant$ $\displaystyle 5T(r,f(z))+S(r,f(z)),$

which contradicts $n\geqslant 4$.

Subcase 1.2. Let $\mathcal{A}=1$. i.e., we have
$\mathcal{F}\equiv\mathcal{G}$. Thus we get
$\mathcal{P}(f)\equiv\mathcal{P}(f(z+c))$. We see that the polynomial
$\mathcal{P}(z)=\displaystyle\int_{0}^{z-a}(t-a)^{n}(t-b)^{4}dt+1$ satisfies
the condition (H) and (2.4) since
$\mathcal{P}^{\prime}(z)=(z-a)^{n}(z-b)^{4}$, $k=2$, $e_{1}=a$, $e_{2}=b$ and
$q_{1}=n\geqslant 4$, $q_{2}=4$. We next see that
$\min\\{q_{1},q_{2}\\}=\min\\{n,4\\}\geqslant 2$ and $q_{1}+q_{2}=n+4\geqslant
5$. Therefore by _Lemma 2.2_, we see that the polynomial $\mathcal{P}(z)$ is a
uniqueness polynomial in a broad sense. Hence the relation
$\mathcal{P}(f)\equiv\mathcal{P}(f(z+c))$ implies $f(z)\equiv f(z+c)$.
Case 2. There exists $I\subset\mathbb{R}^{+}$ such that measure of $I$ is
$+\infty$ such that

$\displaystyle
2\overline{N}\left(r,\frac{1}{f(z)-a}\right)+2\overline{N}\left(r,\frac{1}{f(z)-b}\right)$
$\displaystyle\leqslant$
$\displaystyle\left(1+\frac{1}{1000}\right)\bigg{\\{}T(r,(z)f)+T(r,f(z+c))\bigg{\\}}+S(r,(z)f)+S(r,f(z+c).$

We claim that $\mathcal{H}\equiv 0$. Suppose that $\mathcal{H}\not\equiv 0$.
Next in view of the definition $\mathcal{H}$, we see that

(3.13)
$\displaystyle\overline{N}^{E}_{1)}\left(r,\frac{1}{\mathcal{F}}\right)=\overline{N}^{E}_{1)}\left(r,\frac{1}{\mathcal{G}}\right)\leqslant
N\left(r,\frac{1}{H}\right).$

Next we see that the possible poles of $\mathcal{H}$ occur at the following
points: (i) poles of $f(z)$, (ii) poles of $f(z+c)$, (iii) zeros of $f(z)$,
(iv) $1$-points of $f(z)$, (v) all those zeros of $f^{\prime}(z)$ which are
not the zeros of $f(z)(f(z)-1)$ and (vi) all those zeros of $f^{\prime}(z+c)$
which are not the zeros of $f(z+c)(f(z+c)-1)$. Thus we get

(3.14) $\displaystyle
N(r,\mathcal{H})\leqslant\overline{N}(r,f(z))+\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)+\overline{N}(r,f(z+c))$
$\displaystyle+\overline{N}_{0}(r,0;f^{\prime}(z))+\overline{N}_{0}(r,0;f^{\prime}(z+c)),$

where $\overline{N}_{0}\left(r,\displaystyle\frac{1}{f^{\prime}(z)}\right)$ is
the reduced counting function of all those zeros of $f^{\prime}(z)$ which are
not the zeros of $(f(z)-a)(f(z)-b)$. Similarly
$\overline{N}_{0}\left(r,\displaystyle\frac{1}{f^{\prime}(z+c)}\right)$ is
defined.

Therefore using _First Fundamental Theorem_ , we get

$\displaystyle\overline{N}^{E}_{1)}\left(r,\frac{1}{\mathcal{F}}\right)$
$\displaystyle\leqslant$ $\displaystyle N\left(r,\frac{1}{\mathcal{H}}\right)$
$\displaystyle\leqslant$ $\displaystyle N(r,\mathcal{H})$
$\displaystyle\leqslant$
$\displaystyle\overline{N}(r,f(z))+\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)+\overline{N}(r,f(z+c))$
$\displaystyle+\overline{N}_{0}(r,0;f^{\prime}(z))+\overline{N}_{0}(r,0;f^{\prime}(z+c)).$

We also note that

$\displaystyle\overline{N}_{(2}\left(r,\frac{1}{\mathcal{F}}\right)\leqslant\overline{N}_{0}\left(r,\frac{1}{f^{\prime}(z)}\right),\;\;\overline{N}_{(2}\left(r,\frac{1}{\mathcal{G}}\right)\leqslant\overline{N}_{0}\left(r,\frac{1}{f^{\prime}(z+c)}\right).$

Next we define
$\Psi(z)=\displaystyle\frac{f^{\prime}(z)}{[f(z)-a][(f(z)-b]}\frac{f^{\prime}(z+c)}{[f(z+c)-a][f(z+c)-b}$.

From the definition of $\Psi$ and by using _First Fundamental Theorem_ and
(3), we get

$\displaystyle
N_{0}\left(r,\frac{1}{f^{\prime}(z)}\right)+N_{0}\left(r,\frac{1}{f^{\prime}(z+c)}\right)$
$\displaystyle\leqslant$
$\displaystyle\overline{N}\left(r,\frac{1}{\Psi}\right)$
$\displaystyle\leqslant$ $\displaystyle\overline{N}(r,\Psi)$
$\displaystyle\leqslant$
$\displaystyle\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)+\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)$
$\displaystyle+\overline{N}\left(r,\frac{1}{f(z+c)-b}\right)+S(r,f(z))+S(r,f(z+c))$
$\displaystyle\leqslant$ $\displaystyle
2\overline{N}\left(r,\frac{1}{f(z)-a}\right)+2\overline{N}\left(r,\frac{1}{f(z)-b}\right)+S(r,f(z))+S(r,f(z+c)).$

Adding

$\displaystyle\overline{N}_{(2}\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}_{(2}\left(r,\frac{1}{\mathcal{G}}\right)+\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)$

both sides of (3), we get

$\displaystyle\overline{N}^{E}_{1)}\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}_{(2}\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}_{(2}\left(r,\frac{1}{\mathcal{G}}\right)+\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)$
$\displaystyle\leqslant$
$\displaystyle\overline{N}(r,f(z))+2\overline{N}\left(r,\frac{1}{f(z)-a}\right)+2\overline{N}\left(r,\frac{1}{f(z)-b}\right)+\overline{N}(r,f(z+c))$
$\displaystyle+2\overline{N}_{0}\left(r,\frac{1}{f^{\prime}(z)}\right)+2\overline{N}_{0}\left(r,\frac{1}{f^{\prime}(z+c)}\right).$

i.e.,

$\displaystyle\overline{N}\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{f(z)-b}\right)$
$\displaystyle\leqslant$
$\displaystyle\overline{N}(r,f(z))+6\overline{N}\left(r,\frac{1}{f(z)-a}\right)+6\overline{N}\left(r,\frac{1}{f(z)-b}\right)+\overline{N}(r,f(z+c))$
$\displaystyle+S(r,f(z))+S(r,f(z+c)).$

Similarly, we get

$\displaystyle\overline{N}\left(r,\frac{1}{\mathcal{G}}\right)+\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)+\overline{N}\left(r,\frac{1}{f(z+c)-b}\right)$
$\displaystyle\leqslant$
$\displaystyle\overline{N}(r,f(z+c))+6\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)+6\overline{N}\left(r,\frac{1}{f(z+c)-b}\right)+\overline{N}(r,f(z))$
$\displaystyle+S(r,f(z))+S(r,f(z+c)).$

Now by applying _Second Fundamental Theorem_ and (3), (3) and (3), we get

$\displaystyle(n+5)\bigg{\\{}T(r,f(z))+T(r,f(z+c))\bigg{\\}}$
$\displaystyle\leqslant$
$\displaystyle\overline{N}\left(r,\frac{1}{\mathcal{F}}\right)+\overline{N}(r,f(z))+\overline{N}\left(r,\frac{1}{f(z)-a}\right)+\overline{N}\left(r,\frac{1}{\mathcal{G}}\right)+\overline{N}(r,f(z+c))$
$\displaystyle+\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)+S(r,f(z))+S(r,f(z+c))$
$\displaystyle\leqslant$ $\displaystyle
2\overline{N}(r,f(z))+2\overline{N}(r,f(z+c))+6\overline{N}\left(r,\frac{1}{f(z)-a}\right)+6\overline{N}\left(r,\frac{1}{f(z+c)-a}\right)$
$\displaystyle+6\overline{N}\left(r,\frac{1}{f(z)-b}\right)+6\overline{N}\left(r,\frac{1}{f(z+c)-b}\right)+S(r,f(z))+S(r,f(z+c))$
$\displaystyle\leqslant$
$\displaystyle\left(8+\frac{6}{1000}\right)\bigg{\\{}T(r,f(z))+T(r,f(z+c))\bigg{\\}}++S(r,f(z))+S(r,f(z+c)),$

which contradicts $n\geqslant 4$.

Therefore, we have $\mathcal{H}\equiv 0$. Thus we get

(3.20)
$\displaystyle\frac{1}{\mathcal{F}}\equiv\frac{\mathcal{A}}{\mathcal{G}}+\mathcal{B},$

where $\mathcal{A}(\neq 0),\mathcal{B}\in\mathbb{C}$. In view of _Lemma 2.1_,
we see from (3.20) that

(3.21) $\displaystyle T(r,f(z))=T(r,f(z+c))+S(r,f(z)).$

Subcase 2.1. Let $\mathcal{B}\neq 0$. Thus we must have

$\displaystyle\overline{N}(r,f(z))=\overline{N}(r,\mathcal{F})=\overline{N}\left(r,\frac{1}{\mathcal{G}+\displaystyle\frac{\mathcal{A}}{\mathcal{B}}}\right)$
$\displaystyle\geqslant$ $\displaystyle 3T(r,f(z+c))+S(r,f(z+c)),$

which is absurd in view of (3.21).
Subcase 2.2. So we have $\mathcal{B}=0$. Therefore (3.20) reduces to
$\mathcal{G}=\mathcal{AF}$. Next proceeding exactly same way as done in
_Subcase 1.1_ , we get $f(z)\equiv f(z+c)$. ∎

###### Proof of Theorem 1.2.

Since $f(z)$ is a non-constant entire function, so we must have
$\overline{N}(r,f(z))=0$ and hence $\overline{N}(r,f(z+c))=0$. Now keeping
this in mind, the rest of the proof follows the proof of _Theorem 1.1_.

∎

##  4\. An Open question

######  Question 4.1.

What is the best possible cardinality of two set sharing problem for the
uniqueness of a meromorphic function and its shift operator?

## References

  * [1] A. Banerjee, _Uniqueness of meromorphic functions sharing two sets with finite weight_ , Portugal. Math. J., 65(1)(2008), 81–-93.
  * [2] A. Banerjee, _Uniqueness of meromorphic functions sharing two sets with finite weight II_ , Tamkang. Math. J., 41(4)(2010), 379-–392.
  * [3] S. S. Bhoosnurmath and R. S. Dyavanal, Uniqueness of meromorphic functions sharing a set, Bull. Math. Anal. Appl., 3(3)(2011), 200–208.
  * [4] S. S. Bhoosnurmath and S. R. Kabbur, Value distribution and uniqueness theorems for difference of entire and meromorphic functions, Int. J. Anal. Appl., 2(2)(2013), 124–136.
  * [5] B. Chen and Z. Chen, Meromorphic functions sharing two sets with its difference operator, Bull. Malays. Math. Soc., 35(3) (2012), 765-–774.
  * [6] B. Chen, Z. Chen and S. Li, Uniqueness of difference operators of meromorphic functions, J. Inequal. Appl., 48, (2012), 1–19. (doi:10.1186/1029-242X-2012-48)
  * [7] M. Fang and I. Lahiri, _Unique range set for certain meromorphic functions,_ Indian J. Math., 45(2)(2003), 141–150.
  * [8] H. Fujimoto, On uniqueness polynomials for meromorphic functions , Nagoya Math. J., 170 (2003), 33–46.
  * [9] A. Goldberg, I. Ostrovskii, _Value Distribution of Meromorphic Functions_ , Transl. Math. Monogr., vol. 236, American Mathematical Society, Providence, RI, 2008, translated from the 1970 Russian original by Mikhail Ostrovskii, with an appendix by Alexandre Eremenko and James K. Langley.
  * [10] F. Gross, _Factorization of meromorphic functions and some open problems_ , Proc. Conf. Univ. Kentucky, Leixngton, Ky(1976); Complex Analysis, Lecture Notes in Math., 599(1977), 51–69, Springer Verlag.
  * [11] W. K. Hayman, Meromorphic functions, The Clarendon Press, Oxford (1964).
  * [12] I. Laine, _Nevanlinna Theory and Complex Differential Equations_ , Walter de Gruyter, Berlin, 1993.
  * [13] A. Z. Mokhon’ko, On the Nevanlinna characteristics of some meromorphic functions, Theo. Funct. Funct. Anal. Appl., Izd-vo Khar’kovsk Un-ta, 14(1971), 83-–87.
  * [14] R. Nevanlinna, _Le théorème de Picard–Borel et la théorie des fonctions méromorphes, Gauthiers–Villars_ , Paris, 1929.
  * [15] X. G. Qi, J. Dou and L. Z. Yang, Uniqueness and value distribution for difference operator of meromorphic function, Adv. Diff. Equn., 32 (2012), 1–9. (doi.org/10.1186/1687-1847-2012-32).
  * [16] C. C. Yang, H. X. Yi, Uniqueness Theory of Meromorphic Functions, Math. Appl., vol. 557, Kluwer Academic Publishers Group, Dordrecht, 2003.
  * [17] H. X. Yi and W. C. Lin, _Uniqueness of meromorphic functions and a question of Gross_ , Kyungpook Math. J., 46(2006), 437–444.
  * [18] J. L. Zhang, Value distribution and sets of difference of meromorphic functions, J. Math. Anal. Appl., 367 (2)(2010), 401–408.
  * [19] J. Zhang and Y. Xu, _Meromorphic functions sharing two sets_ , Appl. Math. Lett., 21(2008), 471–476.