\section{Introduction}
Let $G=(V,E)$ be a graph. A subset $C$ is called a vertex cover if every edge of $G$ has an endpoint in $C$. A subset $I$ of $G$ is called an independent set if every pair of distinct vertices of $I$ are not adjacent in $G$. It is well known that $C$ is a vertex cover if and only if $V-C$ is an independent set.

Let $vc(G)$ be the size of a minimum vertex cover and let the independence number $\alpha(G)=n-vc(G)$ be the size of a largest independent set in $G$.

A vertex cover is minimal if it does not contain any distinct vertex cover of $G$. An independent set is maximal if it is not properly contained in any other independent set of $G$.
A graph $G$ is called well covered if all minimal vertex covers of $G$ have the same size $vc(G)$. That is, if $vc(G)=vc^+(G)$, where $vc^+(G)$ is the size of a maximum minimal vertex cover. Clearly, $vc(G)\leq vc^+(G)$ for every graph $G$.
Alternatively, a graph $G$ is well covered if all maximal independent sets of $G$ have the same size $\alpha(G)$.
The concept of well covered graph was introduced by \cite{plummer70}.

Well covered graphs are interesting because the greedy algorithm for producing a maximal independent set (resp. a minimal vertex cover) always produces a maximum independent set (resp. a minimum vertex cover). Recall that determining the independence number and the minimum vertex cover of a general graph are NP-hard problems.
Unfortunately, the problem of deciding if a graph is well covered is coNP-complete. This was independently proved by \cite{chvatal93} and by \cite{stewart92}. The problem remains coNP-complete even when the input graph is $K_{1,4}$-free (see \cite{caro96}).

Several papers investigate well coveredness in graph classes in order to obtain structural characterizations and polynomial time algorithms that recognize if a graph of such classes is well covered. See for example \cite{caro97,dean94,fradkin09,finbow09,prisner96,plummer93,randerath06,tankus97}.

We first consider some classes of graphs that have been characterized in terms of special properties of the unique primeval decomposition tree associated to each graph of the class. The primeval decomposition tree of any graph can be computed in time linear in the number of vertices and edges (see \cite{jamison95}) and therefore it is the natural framework for finding polynomial time algorithms of many problems. \cite{klein13} investigated the well coveredness of many classes of graphs with few $P_4$'s, such as cographs, $P_4$-reducible, $P_4$-sparse, extended $P_4$-reducible, extended $P_4$-sparse, $P_4$-extendible, $P_4$-lite and $P_4$-tidy.
In this paper, we extend results of 2013 by \cite{klein13} for two superclasses of those graph classes: extended $P_4$-laden graphs and $(q,q-4)$-graphs.
We obtain linear time algorithms to decide well coveredness for such graph classes. The algorithm for $(q,q-4)$-graphs is FPT parameterized by $q$.

We also obtain $O^*(2^{vc})$-time and $O^*(1.4656^{vc^+})$-time FPT algorithms to decide well coveredness, parameterized by $vc(G)$ and $vc^+(G)$, respectively, improving results of 2015 by \cite{boria15}.
Moreover, using crown decomposition, we show that such problems admit kernels having linear number of vertices. Contrasting with the coW[2]-hardness of recognizing well covered graphs by \cite{sula-cocoa16} when $\alpha(G)=n-vc(G)$ is the parameter, we obtain an FPT algorithm to decide well coveredness when $\alpha(G)$ and the degeneracy of the input graph $G$ are aggregate parameters, implying the fixed-parameter tractability, with respect to $\alpha(G)$, of graphs having bounded genus (such as planar graphs) and graphs with bounded maximum degree.

\section{The size of a minimum vertex cover as parameter}

We say that the running time of an FPT algorithm is $O^*(f(k))$, if it can be performed in $O(f(k)\cdot n^c)$-time, for some constant $c$.

In 2015, Boria et al. (see Theorem 5 of \cite{boria15}) proved that the maximum minimal vertex cover problem is FPT parameterized by $vc(G)$ (the vertex cover number). They obtained an $O^*(2.8284^{vc})$-time FPT algorithm to compute the maximum minimal vertex cover, which can be used to decide well coveredness of a graph. \cite{sula-cocoa16} investigated the well coveredness problem and proved that it is FPT parameterized by $vc(G)$, by obtaining an FPT algorithm with time $O^*(2^{nd})=O^*(2^{vc+2^{vc}})$, where $nd(G)$ is the neighborhood diversity of $G$.

In the following, we improve these results and show that it is possible to enumerate all minimal vertex covers in time $O(2^{vc}\cdot(m+n))$.

\begin{theorem}\label{teo-fpt}
It is possible to enumerate in time $O(2^{vc}\cdot(m+n))$ all minimal vertex covers of a graph. Consequently, there exists an $O^*(2^{vc})$-time FPT algorithm to decide  well coveredness parameterized by $vc=vc(G)$.
\end{theorem}

\begin{proof}
Let $C$ be a minimum vertex cover of $G$. Then all edges have an endpoint in $C$. Therefore, for every partition of $C$ in two sets $A$ and $B$ ($A\cup B=C$, $A\cap B=\emptyset$), $A\cup (N(B)\setminus B)$ is a vertex cover of $G$ if there are no edges with both endpoints in $B$.

Moreover, for every minimal vertex cover $C'$ of $G$, $A=C\cap C'$ and $B=C\setminus C'$ form a partition of $C$ such that $C'=A\cup(N(B)\setminus B)$, since $C'\setminus C\subseteq N(B)$ (because $C'$ is a vertex cover and is minimal).

Thus, we can enumerate all minimal vertex covers of $G$ by checking for every partition $(A,B)$ of $C$ if $A\cup (N(B)\setminus B)$ is a minimal vertex cover of $G$.
See Figure \ref{fig.particoes} for an example with a graph $G$, a minimum vertex cover $C$ and three different partitions $(A,B)$ of $C$. Only in the third partition, $A\cup(N(B)\setminus B)$ is a minimal vertex cover. In the first  partition, $A\cup(N(B)\setminus B)$ is not minimal and, in the second partition,  $A\cup(N(B)\setminus B)$ is not a vertex cover.
Notice that verifying if a set is a minimal vertex cover can be done in time $O(m+n)$. Since there are $2^{|C|}$ partitions of $C$, $|C|=vc(G)$ and it is possible to obtain a minimum vertex cover $C$ in time $O(2^{vc}\cdot(m+n))$, we are done.
\end{proof}

\begin{figure}\centering\scalebox{0.7}{
\begin{tikzpicture}[auto]
\tikzstyle{vertex}=[draw,circle,fill=white!25,minimum size=8pt,inner sep=1pt]
\tikzstyle{cvertex}=[draw,circle,fill=black!50,minimum size=8pt,inner sep=1pt]
\node[cvertex] (c1) at (2+6,2+4) {};
\node[cvertex] (c2) at (3+6,2+4) {};
\node[cvertex] (c3) at (4+6,2+4) {};
\node[cvertex] (c4) at (5+6,2+4) {};
\node[cvertex] (c5) at (6+6,2+4) {};
\node[vertex] (n1) at (2+6,0+4) {};
\node[vertex] (n2) at (3+6,0+4) {};
\node[vertex] (n3) at (4+6,0+4) {};
\node[vertex] (n4) at (5+6,0+4) {};
\node[vertex] (n5) at (6+6,0+4) {};

\path[-]
(c1) edge (c2) edge (n1) edge (n2)
(c2) edge (n2)
(c3) edge (c2) edge (c4) edge (n3)
(c4) edge (n4)
(c5) edge (n4) edge (n5);

\draw[-] (1.5+6,1.5+4) to (1.5+6,2.5+4);
\draw[-] (1.5+6,2.5+4) to (6.5+6,2.5+4);
\draw[-] (6.5+6,2.5+4) to (6.5+6,1.5+4);
\draw[-] (6.5+6,1.5+4) to (1.5+6,1.5+4);

\node () at (7+6,2+4) {$C$};
\node () at (0+6,1.5+4) {$G$};

\node[cvertex] (c1) at (2,2) {};
\node[cvertex] (c2) at (3,2) {};
\node[cvertex] (c3) at (4,2) {};
\node[cvertex] (c4) at (5,2) {};
\node[vertex]  (c5) at (6,2) {};
\node[vertex]  (n1) at (2,0) {};
\node[vertex]  (n2) at (3,0) {};
\node[vertex]  (n3) at (4,0) {};
\node[cvertex] (n4) at (5,0) {};
\node[cvertex] (n5) at (6,0) {};

\path[-]
(c1) edge (c2) edge (n1) edge (n2)
(c2) edge (n2)
(c3) edge (c2) edge (c4) edge (n3)
(c4) edge (n4)
(c5) edge (n4) edge (n5);

\draw[-] (1.5,1.5) to (1.5,2.5);
\draw[-] (1.5,2.5) to (6.5,2.5);
\draw[-] (6.5,2.5) to (6.5,1.5);
\draw[-] (6.5,1.5) to (1.5,1.5);
\draw[-] (5.5,1.5) to (5.5,2.5);

\node () at (2,2.7) {$A$};
\node () at (6,2.7) {$B$};
\node () at (5.7,-0.5) {$N(B)\setminus B$};

\node[vertex] (c1) at (2+6,2) {};
\node[vertex] (c2) at (3+6,2) {};
\node[cvertex] (c3) at (4+6,2) {};
\node[cvertex] (c4) at (5+6,2) {};
\node[cvertex] (c5) at (6+6,2) {};
\node[cvertex] (n1) at (2+6,0) {};
\node[cvertex] (n2) at (3+6,0) {};
\node[vertex] (n3) at (4+6,0) {};
\node[vertex] (n4) at (5+6,0) {};
\node[vertex] (n5) at (6+6,0) {};

\path[-]
(c1) edge (c2) edge (n1) edge (n2)
(c2) edge (n2)
(c3) edge (c2) edge (c4) edge (n3)
(c4) edge (n4)
(c5) edge (n4) edge (n5);

\draw[-] (1.5+6,1.5) to (1.5+6,2.5);
\draw[-] (1.5+6,2.5) to (6.5+6,2.5);
\draw[-] (6.5+6,2.5) to (6.5+6,1.5);
\draw[-] (6.5+6,1.5) to (1.5+6,1.5);
\draw[-] (3.5+6,1.5) to (3.5+6,2.5);

\node () at (2+6,2.7) {$B$};
\node () at (6+6,2.7) {$A$};
\node () at (2.7+6,-0.5) {$N(B)\setminus B$};

\node[vertex]  (c1) at (2+12,2) {};
\node[cvertex] (c2) at (3+12,2) {};
\node[cvertex] (c3) at (4+12,2) {};
\node[cvertex] (c4) at (5+12,2) {};
\node[cvertex] (c5) at (6+12,2) {};
\node[cvertex] (n1) at (2+12,0) {};
\node[cvertex] (n2) at (3+12,0) {};
\node[vertex]  (n3) at (4+12,0) {};
\node[vertex]  (n4) at (5+12,0) {};
\node[vertex]  (n5) at (6+12,0) {};

\path[-]
(c1) edge (c2) edge (n1) edge (n2)
(c2) edge (n2)
(c3) edge (c2) edge (c4) edge (n3)
(c4) edge (n4)
(c5) edge (n4) edge (n5);

\draw[-] (1.5+12,1.5) to (1.5+12,2.5);
\draw[-] (1.5+12,2.5) to (6.5+12,2.5);
\draw[-] (6.5+12,2.5) to (6.5+12,1.5);
\draw[-] (6.5+12,1.5) to (1.5+12,1.5);
\draw[-] (2.5+12,1.5) to (2.5+12,2.5);

\node () at (2+12,2.7) {$B$};
\node () at (6+12,2.7) {$A$};
\node () at (2.7+12,-0.5) {$N(B)\setminus B$};

\end{tikzpicture}}
\caption{Graph $G$ with a minimum vertex cover $C$ and three different partitions $(A,B)$ of $C$. Only in the third partition, $A\cup(N(B)\setminus B)$ is a minimal vertex cover.}
\label{fig.particoes}
\end{figure}

\vspace{0.2cm}

\subsection{Polynomial kernel}

Crown decomposition is a general kernelization technique that can be used
to obtain kernels for many problems (see \cite{cygan2015parameterized}).

\begin{definition} (Crown decomposition)
A crown decomposition of a graph $G$ is a parti\-tioning of $V(G)$ into three parts $C$ (Crown), $H$ (Head) and $R$ (Remainder), such that:
\begin{itemize}
\item $C$ is nonempty;
\item $C$ is an independent set;
\item There are no edges between vertices of $C$ and $R$. That is, $H$ separates $C$ and $R$;
\item Let $E$ be the set of edges between vertices of $C$ and $H$. Then $E$ contains a matching of size $|H|$. In other words, $G$ contains a matching of $H$ into $C$.
\end{itemize}
\end{definition}

The following lemma is the basis for kernelization using crown
decomposition (see \cite{cygan2015parameterized}).

\begin{lemma}~\label{crown lemma} (Crown lemma)
Let $k$ be a positive integer and let $G$ be a graph without isolated vertices and with at least $3k + 1$ vertices. There is a polynomial-time algorithm that either
\begin{itemize}
\item finds a matching of size $k + 1$ in $G$; or
\item finds a crown decomposition of $G$.
\end{itemize}
\end{lemma}

Now, by using Crown lemma, we will present a kernelization algorithm for recognizing well covered graphs, where the vertex cover number is the parameter.
For simplicity, let $k$ be the size of a  minimum vertex cover of $G$, i.e.,  $k=vc(G)$.

\begin{corollary}\label{cor_wc}
Let $G$ be a graph without isolated vertices whose vertex cover number equals $k$, and with at least $3k + 1$ vertices. There is a polynomial-time algorithm that
finds a crown decomposition of $G$ such that $|H|\leq k$.
\end{corollary}

\begin{proof}
By Lemma~\ref{crown lemma} , there is a polynomial-time algorithm that either finds a matching of size $k + 1$ in $G$; or finds a crown decomposition of $G$.
As the size of a maximum matching of a graph is a lower bound to its vertex cover number, $G$ has no matching of size $k + 1$.

By definition, in a crown decomposition of $G$ into $C$, $H$ and $R$, there is a matching of $H$ into $C$. As $C$ is an independent set, and there is no edge between $C$ and $R$, it is easy to see that there exists a minimum vertex cover of $G$ that contains $H$. Thus, $|H|\leq k$.
\end{proof}

\begin{lemma}\label{partitions_wc}
Let $G$ be a graph without isolated vertices and let $C$, $H$ and $R$ be a crown decomposition of $G$. If $G$ is well covered then $G[R]$ and $G[C\cup H]$ are well covered.
\end{lemma}

\begin{proof}
Suppose that $G$ is well covered and $G[R]$ is not well covered. Then, $G[R]$ has two maximal independent sets $I_1$, $I_2$ such that $|I_1|\neq |I_2|$. As $C$ is an independent set that dominates $H$, it follows that $I_1\cup C$ and $I_2\cup C$ are two maximal independent set of $G$ having different cardinalities, contradicting the fact that $G$ is well covered.

Now, suppose that $G$ is well covered and $G[C\cup H]$ is not well covered. Then, $G[C\cup H]$ has a maximal independent set $I$ such that $|I|\neq |C|$. Clearly $I\setminus C\neq \emptyset$. Since $G[C\cup H]$ has a matching $M$ of $H$ into $C$, we know that each edge of $M$ has at most one vertex in $I$. Thus, $|I|< |C|$.
Let $R^*$ be the set of vertices in $R$ with no neighbors in $I$. Let $S_{R}$ and $S_{R^*}$ be a maximum independent set of $G[R]$ and $G[R^*]$, respectively. Note that $|S_{R^*}|\leq |S_R|$, then $S_R \cup C$ and $S_{R^*}\cup I$ are two maximal independent set of $G$ having different cardinalities, contradicting the fact that $G$ is well covered.
\end{proof}

\begin{lemma}\label{same_size}
Let $G$ be a graph without isolated vertices and let $C$, $H$ and $R$ be a crown decomposition of $G$ such that $R=\emptyset$. If $G$ is well covered then $|C|=$$|H|$.
\end{lemma}

\begin{proof}
It is well-known that there is a minimum vertex cover of $G$ that contains $H$ (see~\cite{cygan2015parameterized}). As $R=\emptyset$ then $H$ is a minimum vertex cover of $G$. By definition,  in a crown decomposition of $G$ into $C$, $H$ and $R$, there is a matching $M$ of $H$ into $C$. Suppose that there is an $M$-unsaturated vertex $w$$\notin V(M)$ ($w\in C$). The vertex $w$ has a neighbor in $H$, otherwise $w$ is an isolated vertex. Let $v$ be a neighbor of $w$ and let $K$ be a minimal vertex cover of $G$ such that $v\notin K$. Note that $N(v)\subseteq K$. For any vertex $x\in H$ (including $v$) such that $x\notin K$, there is a vertex $x^c \in C$ such that $(x,x^c) \in M$, which implies that $x^c\in K$. Thus, $K$ has size at least $|H|$. Since $w$ is $M$-unsaturated and it is also a vertex in $K$, then $K$ is a minimal vertex cover of $G$ of size greater than $|H|$, contradicting the fact that $G$ is well covered.
\end{proof}

\begin{corollary}\label{crown_wc}
Let $G$ be a well covered graph without isolated vertices whose vertex cover number equals $k$,  and with at least $3k + 1$ vertices. There is a polynomial-time algorithm that finds a crown decomposition of $G$ such that
\begin{itemize}
\item  $|C|=|H|\leq k$; and
\item $G[C\cup H]$ and $G[R]$ are well covered.
\item $G[R]$ has no isolated vertex.
\end{itemize}
\end{corollary}

\begin{proof}
By Corollary~\ref{cor_wc} there is a polynomial-time algorithm that finds a crown decomposition of $G$ such that $|H|\leq k$. By Lemma~\ref{partitions_wc} we know that $G[C\cup H]$ and $G[R]$ are well covered. Let $C'=C$, $H'=H$ and $R'=\emptyset$ be a crown decomposition of $G[C\cup H]$. By Lemma~\ref{same_size} follows that $|C|=|H|$.

Now, it remains to show that $G[R]$ has no isolated vertex.

Suppose that $G$ is well covered and $G[R]$ has an isolated vertex $\ell$. Any maximal independent set of $G[R]$ contains $\ell$. Let $S$ be a maximum independent set of $G[R]$. It is easy to see that $S\cup C$ is a maximum independent set of $G$. As $\ell$ is an isolated vertex in $G[R]$ and $G$ has no isolated vertex, then $\ell$ has a neighbor $u$ in $H$. Taking a maximal independent set $S_1$ of $G[C\cup H]$ that contains $u$, and a maximal independent $S_2$ of $G[R\setminus N(u)]$, it follows that $S_1\cup S_2$ is a maximal independent set of $G$. Note that $|S_1|=|C|$, because $G[C\cup H]$ is well covered, but $S_2$ has fewer vertices than $S$, since it does not contain $\ell$. Then, $G$ is not well covered.
\end{proof}

Now, we show a kernel having at most $5k$ vertices to the problem of determining whether $G$ is well covered.

\begin{theorem}\label{linearkernel}
Let $G$ be a graph without isolated vertices whose vertex cover number equals $k$. It holds that either
\begin{itemize}
\item $G$ is not well covered; or
\item $G$ has at most $5k$ vertices.
\end{itemize}
\end{theorem}
\begin{proof}
Suppose that $G$ is well covered and has at least $3k+1$ vertices. By Corollary~\ref{crown_wc} we can decompose $G$ into $C$, $H$ and $R$ such that $|C|+|H|\leq 2k$ and $G[R]$ is a well covered graph without isolated vertices.

Let $C, H, R$ be a crown decomposition of $G$ that maximizes the size of the crown $C$.

As $G[R]$ is a well covered graph without isolated vertices, then either $G[R]$ has at most $3k$ vertices; or $G[R]$ admits a crown decomposition into $C'$, $H'$ and $R'$.

If $G[R]$ has at most $3k$ vertices then $G$ has at most $5k$ vertices.

Otherwise, $G[R]$ admits a crown decomposition into $C'$, $H'$ and $R'$ and the following holds:
\begin{itemize}
\item $C \cup C'$ is nonempty;
\item $C \cup C'$ is an independent set, because $C'\subseteq R$.
\item There are no edges between vertices of $C \cup C'$ and $R'$;
\item $G$ contains a matching of $H\cup H'$ into $C \cup C'$.
\end{itemize}
Therefore, $C \cup C'$, $H\cup H'$ and $R'$ is also a crown decomposition of $G$. Since, by definition, $C'$ is nonempty then $C \cup C'$, $H\cup H'$ and $R'$ is a crown decomposition of $G$ with a larger crown. Thus, we have a contradiction.
\end{proof}

\section{The size of a maximum minimal vertex cover as parameter}

Following the results of \cite{boria15}, there is also an FPT algorithm to compute a maximum minimal vertex cover parameterized by $vc^+=vc^+(G)$ (the size of a maximum minimal vertex cover). Its time is $O^*(1.5397^{vc^+})$. In the following, we obtain a faster FPT algorithm with time $O^*(1.4656^{vc^+})$ to decide well-coveredness using the classical FPT algorithm for vertex cover (see \cite{cygan2015parameterized}).

\begin{theorem}\label{teo-fpt2}
Given a graph $G$ and $vc^+(G)$, it is possible to decide whether $G$ is well covered in time $O(1.4656^{vc+} \cdot n^2)$.
\end{theorem}

\begin{proof}
Let $G$ be a graph and let the parameter $k=vc^+(G)$.
The algorithm uses a search tree where each node $h$ has an associated graph $G_h$, a parameter $k_h$ and an associated ``\emph{partial vertex cover}'' $C_h$ in such a way that every edge of $G-G_h$ is covered by $C_h$. In the root $r$, the associated graph $G_r$ is equal to $G$, the parameter $k_r=k$ and $C_r$ is the empty set $\emptyset$. In the following, we define $G_h$ recursively for any non-root node $h$ of the search tree.
We say that a node $\ell$ is a leaf if and only if its associated graph $G_\ell$ has maximum degree at most 2 or its associated parameter $k_\ell=0$.

Let $h$ be a non-leaf node.
Then $G_h$ has a vertex $x_h$ with degree at least 3. Notice that there is no minimal vertex cover containing $N_{G_h}[x_h]$, since removing $x_h$ we also have a vertex cover. Then we have two possibilities: (1) $x_h$ in the vertex cover; or (2) $x_h$ not in the vertex cover and consequently $N_{G_h}(x_h)$ in the vertex cover, if $k_h\geq|N_{G_h}(x_h)|$.
We branch $h$ according to these two possibilities.

In the first child $h_1$, let $C_{h_1}=C_h\cup\{x_h\}$, $k_{h_1}=k_h-1$ and $G_{h_1}$ is obtained from $G_h$ by removing the vertex $x_h$. In words, we include $x_h$ to the partial vertex cover $C_{h_1}$ of $G_{h_1}$, and remove from $G_h$ the vertex $x_h$ to obtain $G_{h_1}$.

If $k_h\geq|N_{G_h}(x_h)|$, the node $h$ has a second child $h_2$ with $C_{h_2}=C_h\cup N_{G_h}(x_h)$, $k_{h_2}=k_h-|N_{G_h}(x_h)|$ and $G_{h_2}$ is obtained from $G_h$ by removing $N_{G_h}[x_h]$. In words, we include $N_{G_h}(x_h)$ to the partial vertex cover $C_{h_2}$ of $G_{h_2}$, and remove $N_{G_h}[x_h]$ from $G_h$ to obtain $G_{h_2}$.

For each leaf $\ell$ with $k_\ell=0$ and $G_\ell$ empty (no edges), we have that $C_\ell$ is a vertex cover of $G$. For each leaf $\ell$ with $k_\ell=0$ and $G_\ell$ non-empty, we have that $C_\ell$ has $k$ vertices and is not a vertex cover of $G$ (in this case, such a leaf is ignored).
For each leaf $\ell$ with $k_\ell>0$, $G_\ell$ has maximum degree at most 2 and then it is a simple graph consisting of paths, cycles or isolated vertices and it is possible to obtain a minimum and a maximum superset of $C_\ell$ which are minimal vertex covers of $G$ in linear time, if they exist. With this, we can obtain a minimum vertex cover (size $vc(G)$) and a maximum minimal vertex cover (size $vc^+(G)$) by looking the vertex covers obtained by the leaves which are minimal. With this, we can decide if $G$ is well covered.

Let $T(k_h)$ be the number of leaves in the subtree with root $h$.
Then $T(k_h)=T(k_{h_1})+T(k_{h_2})$ if $h$ has two children. Otherwise, $T(k_h)=T(k_{h_1})$. Moreover, for each leaf $\ell$, $T(k_\ell)=1$.
Since $|N(x_h)|\geq 3$, then $T(k_h)\leq T(k_h-1)+T(k_h-3)$.
Using induction on $k$, we have that $T(k)\leq 1.4656^{k}$.
Then the search tree has at most $1.4656^{k}$ leaves and consequently at most $2\cdot 1.4656^{k}+1$ nodes, since each node has at most two children. Since every non-leaf node takes time at most $O(n^2)$ and every leaf $\ell$ takes time $O(n^2)$ to decide if $C_\ell$ is a minimal vertex cover, we have that the total time is $O(1.4656^{k}\cdot n^2)$ and we are done.

Now consider a non-leaf node $h$ such that all vertices of $G_h$ have degree at most two.
If $G_h$ is connected, then $G_h$ is either a path or a cycle, and a minimum vertex cover and a maximum minimal vertex cover can be computed in $O(n^2)$ time. If $G_h$ is not connected, then it is a disjoint union of paths and cycles and we have the same time to compute both parameters.
\end{proof}

\begin{corollary}
Let $G$ be a graph without isolated vertices. The problem of determining whether $G$ is well covered admits a kernel having at most $5\cdot vc^+(G)$ vertices.
\end{corollary}
\begin{proof}
It follows from Theorem~\ref{linearkernel} and the fact that $vc^+(G) \geq vc(G)$.
\end{proof}

\section{The size of a maximum independent set as parameter}

The local-treewidth (see \cite{eppstein00}) of a graph $G$ is the function $ltw_G:\mathbb{N}\to\mathbb{N}$ which associates with any $r\in\mathbb{N}$ the maximum treewidth of an $r$-neighborhood in $G$. That is, $ltw_G(r)=\max_{v\in V(G)}\{tw(G[N_r(v)]\}$, where $N_r(v)$ is the set of vertices at distance at most $r$ from $v$. We say that a graph class $\mathcal{C}$ has bounded local-treewidth if there is a function $f_\mathcal{C}:\mathbb{N}\to\mathbb{N}$ such that, for all $G\in\mathcal{C}$ and $r\in\mathbb{N}$, $ltw_G(r)\leq f_\mathcal{C}(r)$.
It is known that graphs with bounded genus or bounded maximum degree have bounded local-treewidth (see  \cite{eppstein00}). In particular, a graph with maximum degree $\Delta$ has $ltw_G(r)\leq\Delta^r$ and a planar graph has $ltw_G(r)\leq 3r-1$ (see \cite{bodlaender98}).

In this section, we consider bounded local-treewidth graphs and $d$-degenerate graphs, both classes include graphs with bounded genus and graphs with bounded maximum degree.

\begin{theorem}
Given a graph $G$ having bounded local-treewidth, the problem of determining whether $G$ is well covered is FPT when parameterized by $\alpha=\alpha(G)$. More precisely, it can be solved in $O(f(\alpha) \cdot n^2)$ time.
\end{theorem}

\begin{proof}
In the following, we express the well coveredness problem in First Order logic.
We use lower case variables $x,y,z,\ldots$ (resp. upper case variables $X,Y,Z,\ldots$) to denote vertices (resp. subsets of vertices) of a graph. The \emph{atomic formulas} are $x=y$, $x\in X$ and $E(x,y)$ which denotes the adjacency relation in a given graph. We say that a logic formula is FO (first order) if it is formed from atomic formulas with Boolean connectives $\wedge,\ \vee,\ \neg,\ \to,\ \leftrightarrow$ and \emph{element quantifications} $\exists x$ and $\forall x$.

Consider the formula $Indep(X)$ which is true if and only if $X$ is an independent set:
\[
  Indep(X)\ :=\ \forall x,y\ (x\in X\wedge y\in X)\to\neg E(x,y)
\]
Also consider the formula $Maximal(X)$ which is true if $X$ is not properly contained in an independent set.
\[
  Maximal(X)\ :=\ \forall y\ \exists x\ (y\not\in X)\to (x\in X)\wedge E(x,y),
\]
where $(y\not\in X):=\neg(y\in X)$.

Given a graph $G$, it is not well covered if and only if $G$ has a maximal independent set $Y$ and a maximum independent set $X'$ with $|X'|\geq|Y|+1$. Thus $X'$ has a subset $X$ with $|X|=|Y|+1$, which is clearly independent.

With this, given a positive integer $k$, let $WellCov_{k}$ be the following first order formula, which is true if and only if the graph $G$ does not have two independent sets $X$ and $Y$ with $|X|=k$, $|Y|=k-1$ and $Y$ being maximal:
\[
WellCov_k\ :=\ \forall x_1,\ldots,x_k\ \forall y_1,\ldots,y_{k-1}\
\left(\bigwedge_{1\leq i<j\leq k} x_i\ne x_j\right)\ \wedge\ Indep(\{x_1,\ldots,x_k\})
\]
\[
\to\ \neg\Big(Indep(\{y_1,\ldots,y_{k-1}\})\ \wedge\ Maximal(\{y_1,\ldots,y_{k-1}\}\Big)
\]

Notice that $WellCov_k$ contains $2k-1$ variables.

Now let $\alpha=\alpha(G)$. As mentioned before, if $G$ is not well covered, then there are independent sets $X$ and $Y$ with $2\leq |X|\leq\alpha$, $|Y|=|X|-1$ and $Y$ being maximal. With this, let $WellCov$ be the following first order formula, which is true if and only if $G$ is well covered:
\[
  WellCov\ :=\ \bigwedge_{2\leq k\leq\alpha}\ WellCov_k.
\]

Then the well covered decision problem is first order expressible. Moreover, $WellCov$ contains at most $\alpha^2$ variables and then the size of the expression $WellCov$ is a function of $\alpha$.
We then can apply the Frick-Grohe Theorem (see Chapter 14 of \cite{downey-fellows13}) to prove that the well coveredness decision problem is FPT with parameter $\alpha(G)$ in time $O(n^2)$ for graphs with bounded local treewidth.
\end{proof}

\vspace{0.5cm}

The last theorem is a general result for bounded local treewidth graphs. We can obtain specific FPT algorithms (parameterized by $\alpha(G)$) for $d$-degenerate graphs, such as planar graphs, bounded genus graphs and bounded maximum degree graphs.
A graph is called $d$-\emph{degenerate} if every induced subgraph has a vertex with degree at most $d$. The \emph{degeneracy} of a graph $G$ is the smallest $d$ such that $G$ is $d$-degenerate.
For example, outerplanar graphs, planar graphs and graphs with bounded maximum degree $\Delta$ have degeneracy at most $2$, $5$ and $\Delta$, respectively.

\begin{theorem}\label{teo-hered}
The problem of determining whether a given graph $G$ is well covered is FPT when parameterized by $\alpha=\alpha(G)$ and the degeneracy of $G$. More precisely, it can be solved in $O((d+1)^\alpha\cdot(m+n))$ time.
\end{theorem}

\begin{proof}
Let $G$ be a $d$-degenerate graph.
The algorithm uses a search tree $T$ with height $\alpha=\alpha(G)$ where each node $h$ of $T$ has an associated graph $G_h$. The associated graph of the root $r$ of $T$ is the original graph $G_r=G$. A leaf is a node such that its height is $\alpha$ or its associated graph is empty.

Let $h$ be a non-leaf node with associated graph $G_h$. We branch $h$ according to a vertex $v$ with minimum degree in the associated graph of $h$. Let $N_{G_h}[v]=\{u_1,\ldots,u_\ell\}$, where $\ell=|N_{G_h}[v]|\leq d+1$. With this, the node $h$ will have $\ell+1$ child nodes $h_1,h_2,\ldots,h_\ell$ in the search tree. In the child node $h_i$ ($1\leq i\leq \ell$), let $G_{h_i}=G_h$ initially and remove $N_{G_h}[u_i]$ from the associated graph $G_{h_i}$, which is also $d$-degenerate.

If there are two leaf nodes with different heights, return NO (since $G$ has a maximal independent set which is not maximum and then $G$ is not well covered). Otherwise, return YES.
Notice that the tree height is at most $\alpha(G)$ and each node has at most $d+1$ child nodes. Therefore, the search tree has at most $(d+1)^\alpha$ nodes and the total time is $O((d+1)^\alpha\cdot(m+n))$, since every node takes time $O(m+n)$.
\end{proof}

\vspace{0.5cm}

With this, we obtain the following corollary for graphs with bounded genus.

\begin{corollary}
Given a graph $G$ with bounded genus, the problem of determining whether $G$ is well covered can be solved in $O(7^\alpha\cdot(m+n))$ time.
\end{corollary}

\begin{proof}
Observe that if $G$ has genus equals $0$ then $G$ is a planar graph, thus $G$ is 5-degenerate and it is done by Theorem \ref{teo-hered}.
Now, assume that the genus $g$ of $G$ is bounded by a constant $c\geq 1$. Since $G$ has bounded genus $g$, we can assume that $n\geq 12g$, otherwise we can verify well coveredness in constant time.

Let $G$ be a graph embedded in a surface of genus $g$ without crossing edges (for example, toroidal graphs have $g=1$). From the Euler's formula for surfaces of genus $g$, we have that $m=n+f-2+2g$, where $f$ is the number of faces of $G$.  Moreover, we can assume that all faces of $G$ are triangles (otherwise we can increase the number of edges) and then every edge is part of two faces: $3f=2m$. Thus, $m=n+(2/3)m-2+2g$ and then $m=3n+6g-6$. As $n\geq 12g$, it follows that $m \leq (3.5)n-6$. Since the sum of vertex degrees is $2m\leq 7n-12$, then $G$ has a vertex of degree less than $7$.
As bounded genus is a hereditary property, it holds that each subgraph of $G$ either has at most $12g$ vertices, or has a vertex of degree at most six. Therefore, by applying similar ideas in the proof of Theorem \ref{teo-hered}, we can determine whether $G$ is well covered in $O(7^\alpha\cdot(m+n))$ time.
\end{proof}

\section{Well coveredness of graphs with few $P_4$'s}

In this section, we obtain linear time algorithms for extended $P_4$-laden graphs and $(q,q-4)$-graphs.
A \emph{cograph} is a graph with no induced $P_4$ (see \cite{corneil81}).
A graph $G$ is \emph{$P_4$-sparse} if every set of five vertices in $G$ induces at most one $P_4$ (see \cite{olariu92}).
A graph $G$ is $(q,q-4)$ for some integer $q\geq 4$ if every subset with at most $q$ vertices induces at most $q-4$ $P_4$'s (see \cite{olariu01}).
Cographs and $P_4$-sparse graphs are exactly the $(4,0)$-graphs and the $(5,1)$-graphs.
\cite{olariu01} obtained polynomial time algorithms for several optimization problems in $(q,q-4)$-graphs.
A graph is extended $P_4$-laden if every induced subgraph with at most six vertices contains at most two induced $P_4$'s or is $\{2K_2, C_4\}$-free.
This graph class was introduced by \cite{giak96}.

A motivation to develop algorithms for extended $P_4$-laden graphs and $(q,q-4)$-graphs lies on the fact that they are on the top of a widely studied hierarchy of classes containing many graphs with few $P_4$'s, including cographs, $P_4$-sparse, $P_4$-lite, $P_4$-laden and $P_4$-tidy graphs. See Figure \ref{figura1}.
\cite{klein13} obtained linear time algorithms to determine well coveredness for $P_4$-tidy graphs.

\begin{figure}
\centering
\scalebox{1}{
\begin{tikzpicture}[auto]
\tikzstyle{set1}=[draw,rectangle,fill=black!00,minimum size=9pt,inner sep=5pt]
\tikzstyle{set2}=[draw,rectangle,fill=black!10,minimum size=9pt,inner sep=5pt]

\node[set1] (extladen) at (4,7.5) {Extended $P_4$-laden};
\node[set1] (qq4) at (9,7.5) {$(q,q-4)$-graph};

\node[set2] (tidy) at (2,6) {$P_4$-tidy};
\node[set1] (laden) at (6,6) {$P_4$-laden};
\node[set1] (q73) at (9,6) {$(7,3)$-graph};

\node[set2] (extendible) at (0,4.5) {$P_4$-extendible};
\node[set2] (extsparse) at (4,4.5) {Extended $P_4$-sparse};
\node[set2] (lite) at (8,4.5) {$P_4$-lite};

\node[set2] (extred) at (2,3) {Extended $P_4$-reducible};
\node[set2] (sparse) at (6,3) {$P_4$-sparse};

\node[set2] (red) at (4,1.5) {$P_4$-reducible};

\node[set2] (cograph) at (4,0) {Cograph};

\path[-]
(red) edge (cograph) edge (extred) edge (sparse)
(extsparse) edge (extred) edge (sparse) edge (tidy)
(tidy) edge (extendible) edge (extladen) edge (lite)
(laden) edge (lite) edge (extladen)
(q73) edge (lite) edge (qq4)
(lite) edge (sparse)
(extred) edge (extendible);

\node () at (10,6.8) {$q>7$};

\end{tikzpicture}
}
\caption{Hierarchy of graphs with few $P_4$'s. In gray, the classes investigated by \cite{klein13}.}
\label{figura1}
\end{figure}

Given graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$, the \emph{union of $G_1$ and $G_2$} is the graph $G_1\cup G_2=(V_1\cup V_2,E_1\cup E_2)$ and the \emph{join of $G_1$ and $G_2$} is the graph $G_1\vee G_2=(V_1\cup V_2,E_1\cup E_2\cup\{uv: u\in V_1, v\in V_2\})$.

A \emph{pseudo-split} is a graph whose vertex set has a partition $(R,C,S)$ such that $C$ induces a clique, $S$ induces an independent set, every vertex of $R$ is adjacent to every vertex of $C$ and non-adjacent to every vertex of $S$, every vertex of $C$ has a neighbor in $S$ and every vertex of $S$ has a non-neighbor in $C$. Notice that the complement of a pseudo-split is also a pseudo-split.

A \emph{spider} is a pseudo-split with partition $(R,C,S)$ such that $C=\{c_1,\ldots,c_k\}$ and $S=\{s_1,\ldots,s_k\}$ for $k\geq 2$ and either $s_i$ is adjacent to $c_j$ if and only if $i=j$ (a thin spider), or $s_i$ is adjacent to $c_j$ if and only if $i\not=j$ (a thick spider).
Notice that the complement of a thin spider is a thick spider, and vice-versa.
A \emph{quasi-spider} is obtained from a spider by substituting a vertex of $C\cup S$ by a $K_2$ or a $\overline{K_2}$.

A graph $G$ is {\it $p$-connected} if, for every bipartition of the vertex set, there is a crossing $P_4$ (that is, an induced $P_4$ with vertices in both parts of the bipartition). A {\it p-component} of $G$ is a maximal $p$-connected subgraph.
A graph $H$ is {\it separable} if its vertex set can be partitioned in two graphs $(H_1,H_2)$ such that every induced $P_4$ $wxyz$ with vertices of $H_1$ and $H_2$ satisfies $x,y\in V(H_1)$ and $w,z\in V(H_2)$. We write $H\to(H_1,H_2)$.
It was proved that, if $G$ and $\overline{G}$ are connected and $G$ is not $p$-connected, then $G$ has a separable $p$-component $H\to(H_1,H_2)$ such that every vertex of $G-H$ is adjacent to every vertex of $H_1$ and non-adjacent to every vertex of $H_2$ (see \cite{jamison95}).

\cite{giak96} proved that every $p$-connected extended $P_4$-laden graph is pseudo-split or quasi-spider $(R,C,S)$ with $R=\emptyset$, or is isomorphic to $C_5$, $P_5$ or $\overline{P_5}$. The following theorem suggests a natural decomposition for extended $P_4$-laden graphs, which can be obtained in linear time.

\begin{theorem}[\cite{giak96}]\label{teo-giak96}
A graph $G$ is extended $P_4$-laden if and only if exactly one of the following conditions is satisfied:
\begin{itemize}
\item $G$ is the disjoint union or the join of two extended $P_4$-laden graphs;
\item $G$ is pseudo-split or quasi-spider $(R,C,S)$ such that $G[R]$ is extended $P_4$-laden;
\item $G$ is isomorphic to $C_5$, $P_5$ or $\overline{P_5}$;
\item $G$ has at most one vertex.
\end{itemize}
\end{theorem}

For every $q\geq 4$, the $(q,q-4)$-graphs are self-complementary and have a nice structural decomposition in terms of union and join operations, spider graphs and separable p-components.
\cite{olariu98} proved that every $p$-connected $(q,q-4)$-graph is a spider $(R,C,S)$ with $R=\emptyset$ or has less than $q$ vertices.

\begin{theorem}[\cite{olariu98}]\label{teo-primeval}
Let $q\geq 4$.
If $G$ is a $(q,q-4)$-graph, then one of the following holds:
\begin{itemize}
\item $G=G_1\cup G_2$ is the union of two $(q,q-4)$-graphs $G_1$ and $G_2$;
\item $G=G_1\vee G_2$ is the join of two $(q,q-4)$-graphs $G_1$ and $G_2$;
\item $G$ is a spider $(R,C,S)$ such that $G[R]$ is a $(q,q-4)$-graph.
\item $G$ contains a separable $p$-component $H\to(H_1,H_2)$ with $|V(H)|<q$ such that $G-H$ is a $(q,q-4)$-graph and every vertex of $G-H$ is adjacent to every vertex of $H_1$ and not adjacent to any vertex of $H_2$;
\item $G$ has less than $q$ vertices.
\end{itemize}
\end{theorem}

This decomposition can be obtained in linear time (see \cite{olariu98}).
Linear time algorithms are obtained by \cite{olariu01} for several optimization problems in $(q,q-4)$-graphs using this decomposition.

\cite{klein13} characterized well coveredness for the union and join operations.

\begin{theorem}[Theorems 6 and 7 of \cite{klein13}]\label{lem-union-join}
Let $G_1$ and $G_2$ be two graphs.
Then $G_1\cup G_2$ is well covered if and only if $G_1$ and $G_2$ are well covered.
Moreover, $G_1\vee G_2$ is well covered if and only if $G_1$ and $G_2$ are well covered and $\alpha(G_1)=\alpha(G_2)$.
\end{theorem}

\vspace{0.5cm}

In the following, we characterize well coveredness for pseudo-split graphs.
It is worth mentioning that \cite{sula-cocoa16} obtained a characterization for well-covered split graphs which is similar to the following, but different, since pseudo-split graphs have the part $R$ which must be considered.

\begin{lemma}\label{lem-pseudosplit}
Let $G$ be a pseudo-split graph with partition $(R,C,S)$. Then $G$ is well covered if and only if $R=\emptyset$ and every vertex of $C$ has exactly one neighbor in $S$.
\end{lemma}

\begin{proof}
Recall that $C$ induces a clique, $S$ induces an independent set and every vertex of $C$ has a neighbor in $S$.
Suppose that $R\ne\emptyset$. Then, for every vertex $r\in R$, $S\cup\{r\}$ is an independent set of $G$ with $|S|+1$ vertices. Moreover, for any vertex $c\in C$, we have that $S\cup\{c\}\setminus N(c)$ is a maximal independent set of $G$ with at most $|S|$ vertices. Thus $G$ is not well covered.

Now assume that $R=\emptyset$.
Let $I$ be a maximal independent set of $G$. Clearly $|I\cap C|\leq 1$ since $C$ induces a clique. Suppose that $I\cap C=\emptyset$. Then $I=S$ (because $I$ is maximal) and consequently $|I|=|S|$. Now suppose that $|I\cap C|=1$ and let $c\in I\cap C$. Then $S\setminus N(c)\subseteq I$ (because $I$ is maximal), and consequently $|I|$ is the number of non-neighbors of $c$ in $S$ plus one. Then $G$ is well covered if and only if $c$ has exactly one neighbor in $S$ for every $c\in C$.
Since they are the only possible maximal independent sets, we are done.
\end{proof}

In the following, we characterize well coveredness for quasi-spiders.

\begin{lemma}\label{lem-spider}
Let $G$ be a quasi spider with partition $(R,C,S)$. Then $G$ is well covered if and only if $R=\emptyset$ and $G$ is a thin spider with a vertex possibly substituted by a $K_2$.
\end{lemma}

\begin{proof}
Recall that $C$ induces a clique, $S$ induces an independent set and every vertex of $R$ is adjacent to each vertex of $C$ and non-adjacent to each vertex of $S$. Let $C=\{c_1,\ldots,c_k\}$ and $S=\{s_1,\ldots,s_k\}$ for $k\geq 2$.

From Lemma \ref{lem-pseudosplit}, we have that a thin spider is well covered if and only if $R=\emptyset$. The same is valid if a vertex of $C\cup S$ is substituted by a $K_2$.
However, if a vertex of $C\cup S$ is substituted by a $\overline{K_2}$, then we obtain two independent sets with sizes $k$ and $k+1$, and consequently $G$ is not well covered.

From Lemma \ref{lem-pseudosplit}, we have that a thick spider is well covered if and only if $R=\emptyset$ and $k=2$, and consequently $G$ is also a thin spider  with $R=\emptyset$.
Moreover, the same is valid if any vertex of $C\cup S$ is substituted by a $K_2$ or a $\overline{K_2}$.
\end{proof}

\vspace{0.5cm}

In the following, we determine well coveredness for separable p-components $H$ with less than $q$ vertices.

\begin{lemma}\label{lem-pcomp}
Let $q\geq 4$ be a fixed integer and $G$ be a graph with a separable $p$-component $H$ with separation $H\to(H_1,H_2)$ with less than $q$ vertices such that $G-H\ne\emptyset$, every vertex of $G-H$ is adjacent to all vertices of $H_1$ and non-adjacent to all vertices of $H_2$. Then $G$ is well covered if and only if $G-H$ and $H_2$ are well covered and every maximal independent set of $H$ with a vertex of $H_1$ has exactly $\alpha(G-H)+\alpha(H_2)$ vertices.
\end{lemma}

\begin{proof}
At first, notice that, from any maximal independent sets $I$ of $G-H$ and $I_2$ of $H_2$, we obtain a maximal independent set $I\cup I_2$ of $G$.
Thus, if either $G-H$ or $H_2$ is not well covered, then $G$ is not well covered.
Moreover, any maximal independent set of $H$ with a vertex of $H_1$ is also a maximal independent set of $G$, since every vertex of $H_1$ is adjacent to all vertices in $G-H$. Thus, if there is a maximal independent set $I_1$ of $H$ containing a vertex of $H_1$ with $|I_1|\ne\alpha(G-H)+\alpha(H_2)$, then $G$ is not well covered.
Finally, notice that any maximal independent set of $G$ with a vertex in $G-H$ is obtained from a maximal independent set of $G-H$ and a maximal independent set of $H_2$, and we are done.
\end{proof}

\begin{theorem}
Let $G$ be a graph. If $G$ is a $(q,q-4)$-graph, we can determine well coveredness in linear time $O(2^qq^2\cdot(m+n))$.
If $G$ is extended $P_4$-laden, we can determine well coveredness in linear time.
\end{theorem}

\begin{proof}
Taking a primeval decomposition $\mathcal{T}$ of $G$, it is easy to see that one can construct a bottom-up dynamic programming according to the following rules:

\begin{enumerate}
\item if $G$ is isomorphic to $C_5$ or $\overline{P_5}$ then $G$ is well covered;
\item if $G$ is isomorphic to $P_5$ then it is not well covered;
\item If $G=G_1\cup G_2$ is the union of two $(q,q-4)$-graphs or two extended $P_4$-laden graphs, then $G$ is well covered if and only if $G_1$ and $G_2$ are well covered; (see Theorem \ref{lem-union-join})
\item if $G=G_1\vee G_2$ is the join of two $(q,q-4)$-graphs or two extended $P_4$-laden graphs, then $G$ is well covered if and only if $G_1$ and $G_2$ are well covered and $\alpha(G_1)=\alpha(G_2)$;
\item If $G$ is pseudo-split or quasi-spider, we are done by Lemmas \ref{lem-pseudosplit} and \ref{lem-spider};
\item if $G$ is a $(q,q-4)$-graph and has a separable p-connected component $H$, then we have from Lemma \ref{lem-pcomp} that well coveredness can be decided by verifying well coveredness for $H_2$ and checking all maximal independent sets of $H$ containing a vertex of $H_1$.
\end{enumerate}

Note that we can apply a linear-time preprocessing in order to check the well coveredness of every leaf node of $\mathcal{T}$. After that, in a bottom-up dynamic programming according to a post-order of $\mathcal{T}$, the well coveredness of nodes representing cases 1,2,3 and 4 can be checked in constant time. For a node representing case 5, to check if $R=\emptyset$ can be done in constant time, and if so, this node is a leaf. Finally, for nodes representing case 6, the well coveredness of $H_2$ can be tested in time $O(2^qq^2)$, since there are at most $2^q$ sets in $H_2$ and each one can be tested in time $O(q^2)$. We have the same time for maximal independent sets of $H$ containing a vertex of $H_1$.
\end{proof}

\acknowledgements
This research was supported by Faperj [CNE 09/2016] and [JCNE 03/2017], Funcap [4543945/2016] Pronem, CNPq Universal [425297/2016-0] and [437841/2018-9], and CAPES [88887.143992/2017-00] DAAD Probral.

\nocite{*}
\bibliographystyle{abbrvnat}


\section{Introduction}

Let $F(x,y)\in\Z[x,y]$ be an irreducible binary form of degree $\geq 3$
and let $a\in\Z\setminus \{0\}$.
There is an extensive literature of {\bf Thue equations} of type
\[
F(x,y)=a\;\;{\rm in}\;\;x,y\in\Z.
\]
In 1909 A. Thue \cite{thue} proved that these equations admit only finitely many solutions.
In 1967 A. Baker \cite{baker} gave effective upper bounds for the solutions.
Later on authors constructed numerical methods to reduce the bounds and
to explicitly calculate the solutions, see \cite{book} for a summary.

Let $M$ be an algebraic number field with ring of integers $\Z_M$.
Let $F(x,y)\in\Z_M[x,y]$ be  an irreducible binary form of degree
$n\geq 3$ and let $\mu\in\Z_M\setminus \{0\}$. As a generalization of Thue equations
consider {\bf relative Thue equations} of type
\[
F(x,y)=\mu\;\;{\rm in}\;\;x,y\in\Z_M.
\]

Using Baker's method S. V. Kotov and V. G. Sprindzuk \cite{ks} were first
to give effective upper
bounds for the solutions of relative Thue equations.
Their theorem has been extended by several authors.
Applying Baker's method, reduction and enumeration algorithms I. Ga\'al and M. Pohst \cite{gp}
gave an efficient algorithm for solving relative Thue equations (see also \cite{book}).

\vspace{0.5cm}

Let $M$ be an imaginary quadratic number field.
Assuming in addition that the roots of $F(x,1)$ are all real,
in the present paper we give an efficient algorithm to reduce
the resolution of {\bf relative Thue inequalities} of the type
\[
|F(x,y)|\leq K \;\;{\rm in}\;\;x,y\in\Z_M
\]
to the resolution of (absolute) {\bf Thue inequalities} of the type
\[
|F(x,y)|\leq k \;\;{\rm in}\;\;x,y\in\Z.
\]
To find the solutions of the above absolute Thue inequality
one can use Kash \cite{kash} or Magma \cite{magma} which admit
efficient algorithms for solving (absolute) Thue equations
$F(x,y)=k'$ for $k'\in\Z$ with $|k'|\leq k$.
For an efficient method for calculating "small" solutions of
Thue inequalities we refer to \cite{thueineq}.

Our method is illustrated with an explicit example.

\section{The main result}

Let $F(x,y)$ be a binary form of degree $n\geq 3$ with rational integer coefficients.
Assume that $f(x)=F(x,1)$ has leading coefficient 1 and distinct real roots $\alpha_1,\ldots,\alpha_n$.
Let $0<\varepsilon<1,\;\; 0<\eta<1$ and let $K\geq 1$. Set

\begin{eqnarray*}
&A={\displaystyle\min_{i\not=j}|\alpha_i-\alpha_j|},\;\;
&B={\displaystyle\min_i\prod_{j\not=i} |\alpha_j-\alpha_i|},
\\
&C={\displaystyle \max\left\{\frac{K}{(1-\varepsilon)^{n-1}B},1\right\}},&
\\
&C_1={\displaystyle\max\left\{\frac{K^{1/n}}{\varepsilon A},\;
(2C)^{1/(n-2)}\right\}},\;\;
&C_2={\displaystyle\max\left\{\frac{K^{1/n}}{\varepsilon A},\;
C^{1/(n-2)}\right\}},
\\
&D={\displaystyle\left(\frac{K}{\eta(1-\varepsilon)^{n-1}AB}\right)^{1/n}},\;
&E={\displaystyle\frac{(1+\eta)^{n-1}K}{(1-\varepsilon)^{n-1}}}.
\end{eqnarray*}

\vspace{1cm}

\noindent
Let $m>1$ be a squarefree positive integer, and set $M=\Q(i\sqrt{m})$.
Consider the relative Thue inequality
\begin{equation}
|F(x,y)|\leq K \;\; {\rm in}\;\; x,y\in\Z_M.
\label{1}
\end{equation}

\vspace{1cm}

\noindent
If $m\equiv 3\; (\bmod \; 4)$, then $x,y\in\Z_M$ can be written as
\[
x=x_1+x_2\frac{1+i\sqrt{m}}{2}=\frac{(2x_1+x_2)+x_2i\sqrt{m}}{2},
\]
\[
y=y_1+y_2\frac{1+i\sqrt{m}}{2}=\frac{(2y_1+y_2)+y_2i\sqrt{m}}{2}
\]
with $x_1,x_2,y_1,y_2\in\Z$.

\noindent
If $m\equiv 1,2\; (\bmod \; 4)$, then $x,y\in\Z_M$ can be written as
\[
x=x_1+x_2i\sqrt{m},\;\; y=y_1+y_2i\sqrt{m}
\]
with $x_1,x_2,y_1,y_2\in\Z$.

\vspace{1cm}

\begin{theorem}
\label{th1}
Let $(x,y)\in\Z_M^2$ be a solution of (\ref{1}).
Assume that
\begin{eqnarray}
|y|> C_1 & \;\; {\rm if} \;\; &m\equiv 3\; (\bmod \; 4),\label{f1} \\
|y|> C_2 & \;\; {\rm if} \;\; &m\equiv 1,2\; (\bmod \; 4). \label{f2}
\end{eqnarray}
Then
\begin{equation}
x_2y_1=x_1y_2.
\label{xy}
\end{equation}

\vspace{0.5cm}
\noindent
I. Further, if $m\equiv 3\; (\bmod \; 4)$, then the following holds:

\vspace{0.5cm}
\noindent
IA1. If  $2y_1+y_2=0$, then  $2x_1+x_2=0$ and
\begin{equation}
|F(x_2,y_2)|\leq \displaystyle{\frac{2^nK}{(\sqrt{m})^n}}.
\label{IA1}
\end{equation}
IA2. If  $|2y_1+y_2|\geq 2D$,  then
\begin{equation}
|F(2x_1+x_2,2y_1+y_2)|\leq 2^n E.
\label{IA2}\\
\end{equation}
IB1. If $y_2=0$ then $x_2=0$ and
\begin{equation}
|F(x_1,y_1)|\leq K.
\label{IB1}
\end{equation}
IB2. If $|y_2|\geq \displaystyle{\frac{2}{\sqrt{m}} D}$, then
\begin{equation}
|F(x_2,y_2)|\leq \frac{2^n}{(\sqrt{m})^n} E.
\label{IB2}
\end{equation}

\vspace{0.8cm}
\noindent
II. If $m\equiv 1,2\; (\bmod \; 4)$, then the following holds:

\vspace{0.5cm}
\noindent
IIA1. If $y_1=0$ then $x_1=0$ and
\begin{equation}
|F(x_2,y_2)|\leq \displaystyle{\frac{K}{(\sqrt{m})^n}}.
\label{IIA1}
\end{equation}
IIA2.  If   $|y_1|\geq D$,  then
\begin{equation}
|F(x_1,y_1)|\leq E.
\label{IIA2}
\end{equation}
IIB1. If $y_2=0$ then $x_2=0$ and
\begin{equation}
|F(x_1,y_1)|\leq K.
\label{IIB1}
\end{equation}
IIB2. If $|y_2|\geq \displaystyle{\frac{D}{\sqrt{m}}}$, then
\begin{equation}
|F(x_2,y_2)|\leq \frac{E}{(\sqrt{m})^n}.
\label{IIB2}
\end{equation}
\end{theorem}

\vspace{0.5cm}

\noindent
Our result is a far reaching generalization of an idea of \cite{complex6}.

\vspace{1cm}

\section{Proof of the main result}

In the proof of Theorem \ref{th1} we shall use the following Lemma.

\begin{lemma}
\label{lemma1}
Let $x,y\in\Z,y\not=0$. Assume that
\[
\left|\alpha_{i_0}-\frac{x}{y}\right|\leq \frac{d}{|y|^n}
\]
for some $i_0\; (1\leq i_0\leq n)$ and $d>0$. If
\[
 |y|\geq \left(\frac{d}{\eta A}  \right)^{1/n},
\]
then
\[
\;\;
|F(x,y)|\leq d(1+\eta)^{n-1}\prod_{j\not={i_0}} |\alpha_j-\alpha_{i_0}|.
\]
\end{lemma}

\vspace{1cm}

\noindent
{\bf Proof of Lemma \ref{lemma1}}\\
By our assumption, we have
\[
\left|\alpha_j-\frac{x}{y}\right|\leq |\alpha_j-\alpha_{i_0}|+\left|\alpha_{i_0}-\frac{x}{y}\right|
\leq (1+\eta) |\alpha_j-\alpha_{i_0}|
\]
for $j\not={i_0}$. Therefore
\[
\prod_{j=1}^n \left|\alpha_j-\frac{x}{y}\right|=
\left|\alpha_{i_0}-\frac{x}{y}\right| \cdot \prod_{j\not ={i_0}}^n \left|\alpha_j-\frac{x}{y}\right|\leq
\frac{d}{|y|^n}\cdot (1+\eta)^{n-1}\cdot \prod_{j\not={i_0}} |\alpha_j-\alpha_{i_0}|,
\]
which implies our assertion. \hfill $\Box$

\vspace{1cm}

\noindent
{\bf Proof of Theorem \ref{th1}.}\\

Let $(x,y)\in\Z_M^2$ be an arbitrary solution of (\ref{1}) with $y\neq 0$.
Let $\beta_j=x-\alpha_j y,\; j=1,\ldots,n$, then the inequality (\ref{1}) can be written as
\begin{equation}
|\beta_1\cdots\beta_n|\leq K.
\label{e}
\end{equation}
Let ${i_0}$ be the index with
\[
|\beta_{i_0}|=\min_j |\beta_j|.
\]
Then $|\beta_{i_0}|\leq K^{\frac{1}{n}}$ and together with
 (\ref{f1}) and (\ref{f2}) we get
\[
|\beta_j|\geq |\beta_j-\beta_{i_0}|-|\beta_{i_0}|\geq |\alpha_j-\alpha_{i_0}|\cdot |y|-K^{\frac{1}{n}}
\geq (1-\varepsilon) \cdot |\alpha_j-\alpha_{i_0}|\cdot |y|
\]
for $j\not={i_0}$.
From the previous inequality and (\ref{e}), we have
\begin{equation}
|\beta_{i_0}|\leq \frac{K}{\prod_{j\not={i_0}}|\beta_j|}\leq \frac{c}{|y|^{n-1}}
\label{betai}
\end{equation}
with
\[
c=\frac{K}{(1-\varepsilon)^{n-1}\prod_{j\not={i_0}}|\alpha_j-\alpha_{i_0}|}.
\]
By (\ref{betai}) we obtain
\[
\left|\alpha_{i_0}-\frac{x\overline{y}}{|y|^2}\right|=\left|\alpha_{i_0}-\frac{x}{y}\right|\leq \frac{c}{|y|^{n}},
\]
hence
\[
\left|\alpha_{i_0}|y|^2-x\overline{y}\right|\leq \frac{c}{|y|^{n-2}},
\]
which implies
\[
|{\rm Im} (x\overline{y})|\leq \frac{c}{|y|^{n-2}}.
\]
Note that $\frac{c}{|y|^{n-2}}<\frac{1}{2}$ and $\frac{c}{|y|^{n-2}}<1$ for
$m\equiv 3\; (\bmod \; 4)$ and $m\equiv 1,2\; (\bmod \; 4)$,
respectively, according to (\ref{f1}) and (\ref{f2}).
Therefore
$|{\rm Im} (x\overline{y})|=\frac{1}{2}|x_2y_1-x_1y_2|\sqrt{m}<\frac{1}{2}$
and \\
$|{\rm Im} (x\overline{y})|=|x_2y_1-x_1y_2|\sqrt{m}<1$
for
$m\equiv 3\; (\bmod \; 4)$ and $m\equiv 1,2\; (\bmod \; 4)$, respectively.
Hence in both cases we have (\ref{xy}).

\vspace{0.5cm}

\noindent
I. Let $m\equiv 3\; (\bmod \; 4)$.

\noindent
IA. The inequality (\ref{betai}) implies
$|{\rm Re}(\beta_{i_0})|\leq \frac{c}{|y|^{n-1}}$, i.e.
\begin{equation}
|(2x_1+x_2)-\alpha_{i_0}(2y_1+y_2)|\leq \frac{2c}{|y|^{n-1}}.
\label{h1}
\end{equation}

\noindent
IA1. If $2y_1+y_2=0$, then (\ref{h1}) yields $2x_1+x_2=0$,
and the inequality (\ref{1}) has the form
\[
\left|F\left(\frac{x_2i\sqrt{m}}{2},\frac{y_2i\sqrt{m}}{2}\right)\right|\leq K
\]
whence we get (\ref{IA1}).

\noindent
IA2. If $2y_1+y_2\not=0$, then
\[
|(2x_1+x_2)-\alpha_{i_0}(2y_1+y_2)|\leq \frac{2c}{|y|^{n-1}}
=\frac{2c}{\displaystyle{\left|\frac{(2y_1+y_2)+y_2i\sqrt{m}}{2}\right|^{n-1}}}
\leq \frac{2^nc}{|2y_1+y_2|^{n-1}}.
\]
Since we have assumed
\[
|2y_1+y_2|\geq \left(\frac{2^nc}{\eta A}\right)^{1/n},
\]
Lemma \ref{lemma1} implies
\[
|F(2x_1+x_2,2y_1+y_2)|\leq 2^nc(1+\eta)^{n-1}\prod_{j\not={i_0}}|\alpha_j-\alpha_{i_0}|
\]
whence we get (\ref{IA2}).

\noindent
IB. By the inequality (\ref{betai}), we have
$|{\rm Im}(\beta_{i_0})|\leq \frac{c}{|y|^{n-1}}$, i.e.
\begin{equation}
\sqrt{m}|x_2-\alpha_{i_0}y_2|\leq \frac{2c}{|y|^{n-1}}.
\label{h2}
\end{equation}

\noindent
IB1. If $y_2=0$, then (\ref{h2}) implies $x_2=0$
and the inequality (\ref{1}) has the form
\[
\left|F\left(\frac{2x_1}{2},\frac{2y_1}{2}\right)\right|\leq K
\]
whence we get (\ref{IB1}).

\noindent
IB2. If $y_2\not=0$, then
\[
|x_2-\alpha_{i_0}y_2|\leq \frac{2c}{\sqrt{m}|y|^{n-1}}
=\frac{2c}{\sqrt{m}\displaystyle{\left|\frac{(2y_1+y_2)+y_2i\sqrt{m}}{2}\right|^{n-1}}}
\leq \frac{2^nc}{(\sqrt{m})^{n}|y_2|^{n-1}}.
\]
Since
\[
|y_2|\geq \left(\frac{2^nc}{(\sqrt{m})^n\eta A}\right)^{1/n},
\]
Lemma \ref{lemma1} implies
\[
|F(x_2,y_2)|\leq
\frac{2^nc}{(\sqrt{m})^n}(1+\eta)^{n-1}\prod_{j\not={i_0}}|\alpha_j-\alpha_{i_0}|
\]
which implies (\ref{IB2}).

\vspace{1cm}

\noindent
II. Let $m\equiv 1,2\; (\bmod \; 4)$.

\noindent
IIA.  The inequality (\ref{betai}) implies
$|{\rm Re}(\beta_{i_0})|\leq \frac{c}{|y|^{n-1}}$, i.e.
\begin{equation}
|x_1-\alpha_{i_0}y_1|\leq \frac{c}{|y|^{n-1}}.
\label{k1}
\end{equation}

\noindent
IIA1. If $y_1=0$, then (\ref{k1}) yields $x_1=0$ and
the inequality (\ref{1}) has the form
\[
|F(i\sqrt{m}x_2,i\sqrt{m}y_2)|\leq K,
\]
whence we get (\ref{IIA1}).

\noindent
IIA2. If $y_1\not=0$, then
\[
|x_1-\alpha_{i_0}y_1|\leq \frac{c}{|y|^{n-1}}
=\frac{c}{|y_1+i\sqrt{m}y_2|^{n-1}}
\leq \frac{c}{|y_1|^{n-1}}.
\]
Since we have assumed
\[
|y_1|\geq \left(\frac{c}{\eta A}\right)^{1/n},
\]
Lemma \ref{lemma1} implies
\[
|F(x_1,y_1)|\leq c(1+\eta)^{n-1}\prod_{j\not={i_0}}|\alpha_j-\alpha_{i_0}|
\]
whence we get (\ref{IIA2}).

\noindent
IIB. By the inequality (\ref{betai}) we have
$|{\rm Im}(\beta_{i_0})|\leq \frac{c}{|y|^{n-1}}$, i.e.
\begin{equation}
\sqrt{m}|x_2-\alpha_{i_0}y_2|\leq \frac{c}{|y|^{n-1}}.
\label{k2}
\end{equation}

\noindent
IIB1. If $y_2=0$, then (\ref{k2}) implies  $x_2=0$
and the inequality (\ref{1}) has the form
\[
|F(x_1,y_1)|\leq K
\]
which is just our assertion (\ref{IIB1}).

\noindent
IIB2. If $y_2\not=0$, then
\[
|x_2-\alpha_{i_0}y_2|\leq \frac{c}{\sqrt{m}|y|^{n-1}}
=\frac{c}{|y_1+i\sqrt{m}y_2|^{n-1}}
\leq \frac{c}{(\sqrt{m})^{n}|y_2|^{n-1}}.
\]
Since
\[
|y_2|\geq \left(\frac{c}{(\sqrt{m})^n\eta A}\right)^{1/n},
\]
Lemma \ref{lemma1} implies
\[
|F(x_2,y_2)|
\leq\frac{c}{(\sqrt{m})^n}(1+\eta)^{n-1}\prod_{j\not={i_0}}|\alpha_j-\alpha_{i_0}|
\]
whence we get (\ref{IIB2}).
\hfill $\Box$

\section{How to apply Theorem \ref{th1}}

In this section we give useful hints for a practical application of Theorem \ref{th1}.\\

\noindent
Using the same notation let us consider again
the relative Thue inequality (\ref{1}).
We describe our algorithm in the case I (for $m\equiv 3 \; (\bmod \; 4)$)
since the case II is completely similar.

\begin{enumerate}
\item
If $|y|\leq C_1$ then we have only finitely many possible
values for $y$ and hence for $y_1,y_2$, as well.
For each possible $y$ and for all integers $\mu\in\Z_M$ with $|\mu|\leq K$
we calculate the roots of the equation $F(x,y)-\mu=0$ in $x$.
For such a root $x$ we calculate the corresponding  $x_1,x_2$.
If $x_1,x_2$ are integers, then
$x\in\Z_M$ and $(x,y)$ is a solutions of (\ref{1}). \\
Alternatively, by
$|\beta_{i_0}|\leq K^{\frac{1}{n}}$ we obtain $|x|\leq K^{\frac{1}{n}}+
\max|\alpha_j|\cdot C_1$. We can simply enumerate and test the finitely many
possible values of $x_1,x_2$ and $y_1,y_2$.
\item
Assume that $|y|>C_1$.
  \begin{enumerate}
  \item
If $|2y_1+y_2|<2D$, then
     \begin{enumerate}
      \item
      If $|y_2|<2D/\sqrt{m}$, then we have only finitely many values for $y_1,y_2$,
			we proceed as in 1.
      \item
			If $|y_2|\geq 2D/\sqrt{m}$, then we use IB2. We solve
      $F(x_2,y_2)=k$ for all $k\in\Z$ with $|k|\leq 2^nE/(\sqrt{m})^n$. We determine the possible
			values of $y_1$ which satisfy $|2y_1+y_2|<2D$.
			We substitute $x_2,y_1,y_2$ into $x_2y_1=x_1y_2$
			to see if there exist corresponding integer $x_1$.
     \end{enumerate}
  \item
	If $|2y_1+y_2|\geq 2D$, then we use IA2. We calculate the solutions
	$X=2x_1+x_2,Y=2y_1+y_2$ of
      $F(X,Y)=k$ for all $k\in\Z$ with $|k|\leq 2^nE$.
	  \begin{enumerate}
      \item
			If $|y_2|<2D/\sqrt{m}$ then there are only finitely many possible values for $y_2$.
			We determine $y_1$ from $Y$.
			Using $X=2x_1+x_2$ we set $x_2=X-2x_1$, substitute $x_2=X-2x_1,y_1,y_2$
			into $x_2y_1=x_1y_2$ and test if there is a corresponding $x_1$ in $\Z$.
		 \item
			If $|y_2|\geq 2D/\sqrt{m}$ we use IB2. We solve
			$F(x_2,y_2)=k$ for $|k|\leq 2^nE/(\sqrt{m})^n$.
			We determine $x_1,y_1$ from $x_2,y_2$ and $X,Y$.
     \end{enumerate}
\end{enumerate}
\end{enumerate}

For solving absolute Thue equations $F(x,y)=k$ for certain values $k\in\Z$
one can efficiently apply Kash \cite{kash} and Magma \cite{magma}.

We remark that an appropriate choice of the parameters $\varepsilon,\eta$
of Thereom \ref{th1}
makes the resolution much easier.
It is worthy to keep $C_1,C_2$ and also $D$ small,
to avoid extensive tests of small
possible solutions. On the other hand, if $E$ is small, then
there are fewer Thue equations (over $\Z$) to be solved.
Of course we can not make all these
constants simultaneously small, therefore we need to make a compromise,
taking into consideration also
the value of $K$ (which also determines the number of
Thue equations to be solved). Usually it is worthy to try several
values of $\varepsilon,\eta$ before we start solving (\ref{1}).

\section{An example}

Let $M=\Q(i\sqrt{5})$, and let
\[
F(x,y)=x^4-9x^3y-21x^2y^2+88xy^3+48y^4
\]
and consider the solutions of
\begin{equation}
|F(x,y)|\leq 20 \;\; {\rm in}\;\; x,y\in\Z_M.
\label{pl}
\end{equation}
The polynomial $F(x,y)$ is irreducible and
the roots of $F(x,1)$ are approximately
\[
-3.4271, -0.49938, 2.7581, 10.1684.
\]
We may set $A=2.9278$, $B=101.7426$. Further, let $\varepsilon=0.1$ and $\eta=0.1$.
We are in case II. Calculating the constants, Theorem \ref{th1} gives:\\
\\
Assume $|y|> 7.2229$. Then:
\begin{eqnarray*}
{\rm IIA1.}&\; {\rm If} \;y_1=0, \;{\rm then}\; x_1=0 \;{\rm and} \;
|F(x_2,y_2)|\leq 0.8000.
\\
{\rm IIA2.}&\; {\rm If} \;|y_1|\geq 0.9796,\; {\rm then}\;
|F(x_1,y_1)|\leq 36.5157.
\\
{\rm IIB1.}&\; {\rm If} \; y_2=0,\;{\rm  then}\; x_2=0\;{\rm  and}\;
|F(x_1,y_1)|\leq 20.
\\
{\rm IIB2.}&\; {\rm If}\; |y_2|\geq 0.4381,\; {\rm then}\;
|F(x_2,y_2)|\leq 1.4606.
\end{eqnarray*}\\

First we consider the values with $|y|\leq C_2=7.2229$.
We have $|x|\leq 20^{\frac{1}{4}}+\max|\alpha_j|\cdot C_2=75.64$.
Enumerating and testing all possible $x=x_1+i\sqrt{5}x_2$ and $y=y_1+i\sqrt{5}y_2$
satisfying these bounds we obtain the solutions
$(x_1,x_2,y_1,y_2)=(0,0,0,0),(1,0,0,0),(2,0,0,0),(1,0,-2,0)$, $(2,0,-4,0)$,
up to sign.

If $y_1=0$ then by IIA1 we have $x_1=0$ and $|F(x_2,y_2)|\leq 0.8$, whence
$|F(x_2,y_2)|=0$, $x_2=0,y_2=0$.

If $y_2=0$ then by IIB1 we have $x_2=0$ and $|F(x_1,y_1)|\leq 20$.
Using Magma we solve $F(x_1,y_1)=k$
for $-20\leq k\leq 20$. We obtain the solutions
$(x_1,y_1)=(0,0),(1,0),(1,-2),(2,0)$, $(2,-4)$, up to sign.
These bring the above solutions $(x_1,x_2,y_1,y_2)$ again.

From now on we assume that $y_1\neq 0$ and $y_2\neq 0$.

If $|y_1|\leq 0.9796$ and $|y_2|\leq 0.4381$ then by IIA2 we have
$|F(x_1,y_1)|\leq 36.5157$ and by IIB2 we have
$|F(x_2,y_2)|\leq 1.4606$.
In addition to the above calculation we solve $F(x_1,y_1)=k$
for $21\leq |k|\leq 36$ but we do not get any further solutions.
Hence the solutions of $|F(x_1,y_1)|\leq 36.5157$ are
$(x_1,y_1)=(0,0),(1,0),(1,-2),(2,0),(2,-4)$, up to sign.
Also the solutions of $|F(x_2,y_2)|\leq 1.4606$ are
$(x_1,y_1)=(0,0),(1,0),(1,-2)$, up to sign.
Testing these possible
$(x_1,x_2,y_1,y_2)$ we do not get any new solutions.

If either $|y_1|< 0.9796$ or $|y_2|< 0.4381$ then $y_1=0$ or $y_2=0$
which cases we have already considered.

Hence all solutions of (\ref{pl}) are
$(x,y)=(0,0),(1,0),(2,0),(1,-2),(2,-4)$,
up to sign.
The calculation takes just a few seconds.


\section{Introduction}

Transition metal dichalcogenide (TMDC) monolayers (MLs)
have emerged as a promising 2D crystal family with several characteristic features.
Their direct band gap and the strong
spin-orbit coupling combined with the lack of inversion symmetry leads to a unique coupling of the spin and valley degrees of freedom.
Due to this distinct feature, elastic scattering of charge carriers is possible
only by simultaneously flipping the spins of two carriers, and this severe restriction leads to small inter-valley scattering rates and therefore
long spin and valley lifetimes. These properties make the TMDCs
promising candidates for future nanoscale electronics.
The role of contacts  of 2D materials is an important
issue for electronics device performance.  Due to the semiconducting nature
of  2D TMDCs, metal contacts are likely to create Schottky barriers. On the one hand, these barriers
can be useful in coping with the impedance mismatch problem \cite{Schmidt2000}, as has been pointed out in the field of spintronics\cite{Fert2001}.
On the other hand, an elimination of Schottky barriers is desirable if the injection current should be maximized.

Several studies have focused on achieving desirable contact properties. Experimentally, the growth of metals on TMDCs have  affected the resulting morphologies; for example,
Pd grows on MoS$_{2} $  as a uniform layer while Au and Ag grow in clusters\cite{doi:10.1021/nn4052138}.
Both experiments\cite{6724660}  and simulations~\cite{Kang2012ACS}  have predicted that Ti as
contact metal to MoS$_{2}$ helps to eliminate the Schottky barrier.
In 2016, Farmanbar and Brocks  calculated  the  contact  between
MoS$ _{2} $ and various metal surfaces, such as  Au, Ag, Cu, and
Ni.  Their results show  that MoS$_{2}$  interacts strongly with
transition metals~\cite{PhysRevB.93.085304}. DFT calculations have shown that the tunnel barrier between Pd and monolayer MoS$ _{2}$  can be reduced to negligible height\cite{Kang2012ACS}. Kang {\it et al.} studied  the
interface  between monolayer MoS$_{2}$ and WSe$_{2}$
and various metals (including  In, Ti, Au, Pd, Mo, and W) by DFT calculations. Their results show that Ti and Mo are the best metals for n-type contacts  on monolayer  MoS$_{2}$,  while Pd was found to be  the best metal for monolayer  WSe$ _{2}$, both metals forming n-type contacts~\cite{PhysRevX.4.031005}.

Most studies examining TMDCs for device applications have
reported on interfaces between TMDC MLs and various non-magnetic metals.
Only few studies have been focused on interfaces between  ferromagnetic metals and TMDC MLs. Experimentally,
magnetic tunnel junctions of Fe/MoS$_{2}$/Fe  have been
investigated  and the results demonstrated that MoS$ _{2}$  became conductive when the MoS$_{2}$  spacer contained only one or two layers~\cite{PhysRevB.90.041401}. Chen {\it et al.} have investigated  properties of  single-layer MoS$_{2}$  with Co electrodes and measured the Schottky barrier height in this system. They found  that by inserting a thin MgO oxide barrier
between the Co electrode and the MoS$_{2}$  flake, the Schottky
barrier height can be reduced~\cite{doi:10.1021/nl4010157}.
Finally, Garandel {\it et al.} have recently studied  the electronic structure of Co/MoS$_{2}$  interfaces and the Schottky barrier height of this  system has been estimated to be $\sim0.32$~eV~\cite{PhysRevB.95.075402}.

It is important to understand the nature of the electronic interface between metals and a TMDCs monolayer. Hence,
in this paper, we employ first principles computations
to study the properties of the interface WS$_{2}$/metal.
Slabs of the hexagonally close-packed (hcp) metals Zr and Co are used to model the (0001) surfaces of Zr bulk or Co bulk, which serve as templates to place the hexagonal layer of WS$_2$.
WS$ _{2}$  has attracted appreciable interest among TMDC monolayers due to  the presence of a high valence band splitting and a high mobility.
We considered Zr and Co as suitable candidates for contact properties. Zr emerges as an ideal candidate with only 1.5\% mismatch to
WS$ _{2} $. Co appears less suitable at first sight due to a large lattice mismatch, but spin-injection from such a high-Curie-temperature
ferromagnetic metal to a single TMDC layer is very important since it would give access to TMDC-based spintronic devices.

\section{Computational details}
All presented calculations are performed in the frame-
work of the spin-polarized Kohn-Sham density functional
theory by using the all-electron full-potential code FHI-aims\cite{FHI-aims}.
The generalized gradient approximation (GGA) in the Perdew-Burke-Ernzerhof (PBE)\cite{PhysRevLett.77.3865}
implementation  is applied as the exchange-correlation functional.
All calculations reported here are done in the scalar-relativistic approximation with the so-called 'tight'  settings for the basis set and on grids in the FHI-aims code.
A convergence criterion of $10^{-5}$eV for the total energy and $10^{-5}$e/{\AA}$^{3}$  for the charge density were employed.
To treat van der Waals (vdW) interactions, we apply the Tkatchenko-Scheffler (TS) method\cite{PhysRevLett.102.073005}, i.e. a density-dependent pairwise interaction is added to the exchange-correlation energy to describe the interfaces Co/WS$_{2}$ and Zr/WS$ _{2}$.
For the Zr or Co metal electrodes, only the interface Zr or Co layer takes part in the vdW interaction, and modified vdW parameters according to the TS scheme for surfaces \cite{Ruiz12} are used. Van der Waals interactions between Co or Zr atoms having a bulk environment are disregarded.

Before constructing  supercells for calculations of WS$ _{2}$ on cobalt, first  the theoretical lattice constants in the hexagonal plane of hcp  bulk cobalt and of a WS$ _{2}$ ML were obtained to be
$a_{\rm Co} = 2.49${\AA}  and $a_{\rm WS_2} = 3.18 ${\AA}, respectively, in satisfactory agreement with the experimental values of 2.49{\AA} and 3.08{\AA} \cite{PhysRevB.60.4397,2053-1583-4-1-015026,doi:10.1063/1.4774090}, respectively.

For the Co metal electrode, we consider two possible orientations of the WS$_2$ layer.
In the first orientation, termed Co/WS$ _{2}R(0^{\circ})$, the lattice vectors of the Co(0001) and the WS$_2$ unit cells are collinear.
The Co/WS$_{2}R(0^{\circ})$  hybrid structure was modeled as a periodic slab by setting the supercell lattice parameter to $a=b=12.485${\AA}, corresponding to $5 \times 5$ primitive cobalt cells and $4 \times 4$ primitive WS$_{2}$ cells.

As an alternative, we consider a supercell in which the misfit strain between Co and WS$_2$ is (almost) compensated only in one crystallographic direction, while there is a relatively large strain in the perpendicular direction.
This situation, termed Co/WS$ _{2}R(90^{\circ})$, is realized if the WS$ _{2} $ monolayer is deposited with a rotation of 90$^{\circ}$ with respect
to the cobalt slab.
We used a $\sqrt{3} \times 4$ supercell of WS$_{2}$ matched to a $2  \times 3\sqrt{3}$ supercell of the Co(0001) surface.
In this situation, a pre-strain in  WS$ _{2} $ is introduced
that is 1.73\% for Co/WS$ _{2}R(0^{\circ})$ and 10.28\% at the Co/WS$ _{2}R(90^{\circ})$ interface.
.pdf

 \begin{figure}[ht]
 \includegraphics[scale=0.42]{fig1.pdf}\\
 \caption{\label{fig:diode}
 Ballistic conductance setup, consisting of the left and right Zr leads and the scattering region (shaded). }
 \end{figure}

The calculated in-plane lattice constant of bulk hcp Zr is $a= 3.23${\AA}, in perfect match with the experimental value of 3.23{\AA} \cite{WILLAIME2003205}.
To model the Zr/WS$ _{2}$ interface, the WS$_{2}(1\times 1)$ unit cell is adjusted to the  $(1  \times 1)$ unit cell of Zr(0001).
In all calculations, the WS$_2$ layer was attached only to one side of the metal slab, and a 15{\AA} vacuum layer was added to prevent artificial interaction due to the periodic boundary conditions perpendicular to the surface.
In the geometry optimizations, a convergence criterion of $10^{-2}$~eV/{\AA}  for
the residual forces was adopted.
The Brillouin zone integrations were performed by using
 meshes of $10\times10\times1$ , $14\times10\times1$  and  $14\times14\times1$ {\bf k}-points for  Co/WS$ _{2}R(0^{\circ})$ ,  Co/WS$ _{2}R(90^{\circ})$ and Zr/WS$ _{2}$, respectively.
Once the atomic structure has been obtained, we  include spin-orbit coupling effects on the
electronic structure via the second-order variational method implemented in FHI-aims \cite{Huhn17}.

For the simulation of the transport characteristics of spintronics devices based on a WS$_2$ sheet, we
used the PWCOND code\cite{PhysRevB.59.2267,PhysRevB.70.045417}  of the {\sc Quantum Espresso} package\cite{PWSCF}, that implements the Landauer-B{\"u}ttiker approach\cite{But86} to quantum transport.
This code allows us to restrict the electronic structure calculation to the valence electrons only, using ultrasoft
pseudo-potentials (US-PPs)\cite{PhysRevB.41.7892} to model the electron-ion interactions.
Transport in heterostructures\cite{Geisler:15a} can be treated by taking a momentum component $k_x$ perpendicular to the transport direction into account and averaging the transmission probabilities,
\begin{equation}
T(E) = \sum_{k_x} w(k_x) T(E,k_x)
\label{eq:T_k}
\end{equation}
where $T(E,k_x)$ is the transmission probability of an electron with energy $E$ and perpendicular momentum $k_x$, and $w(k_x)$ is a weighting factor following from symmetry considerations.
As before, the PBE generalized gradient approximation\cite{PhysRevLett.77.3865} of the exchange-correlation
functional was employed.
The  electronic  wave  functions  were
expanded  in  a  plane-wave  basis  set  with  an  energy  cutoff
of 40~Ry. The vdW interactions were treated by the  Grimme-D2 method\cite{doi:10.1002/jcc.20495}.
In contrast to the adsorption study, we consider a free-standing, single-layer WS$_2$ sheet as building block of an envisaged spintronics device.
The electrical current flows along the zig-zag chains of WS$_2$, taken to define the $z$ direction, while the WS$_2$ sheet is assumed to be infinitely extended in the perpendicular $x$-direction.
To establish electrical contact, the sheet is clamped between Zr electrodes touching the sheet both from above and below, see Fig.~\ref{fig:diode}.
The supercell of the electrode region is constructed from a rectangular cell  of WS$_{2} $ with side length $\sqrt 3 a_{\rm WS_2}$ and $2a_{\rm WS_2}$ containing four W and 8 S atoms attached to Zr(0001) surfaces.
For the free-standing part of the WS$_2$ sheet as well as for the clamped part the lattice constant of WS$_{2} $ ($a_{\rm WS_2} =3.18${\AA}) was used; i.e. the lattice parameter of Zr in the electrode was adjusted to $a_{\rm WS_2}$.
Periodic boundary conditions are assumed in the $x$ and $z$ directions for the calculations of the electronic ground state. The Brillouin zone of the leads and of the center region have been sampled using a 12$\times$1$\times$12  and 12$\times$1$\times$1 Monkhorst-Pack grid, respectively.
For geometry optimizations, the Hellmann-Feynman forces were required to be smaller than $10^{-3}$~Ry/bohr.

\section{RESULTS AND DISCUSSION}

\subsection{Geometry and stability of WS$_{2}$-metal interface}

In order to determine  the stable location of WS$ _{2} $ on Co and Zr slabs,
the binding energy ($E_b$) was calculated as
\begin{align}
E_{b} = E_{\rm{M-WS_2}}- E_{\rm{M}}  - E^{\rm{strain}}_{\rm{WS_2}} \, , \qquad \rm{M=Co,Zr} \, ,
\end{align}
where $E_{\rm M}$ and $E_{\rm WS_2}$ are the total energies
of  the M slab (cobalt, zirconium) and of the WS$_2$ sheet strained to the lattice constant appropriate for each case.
We first determine the equilibrium geometry of  Zr/WS$ _{2}$ and then investigate the stable configuration of WS$ _{2}$  (in both rotational variants) on Co(0001).

\textbf{WS$_{2}$-Zr interface}:
 A five-layer Zr slab unit cell was used in the calculations, where the two bottom layers were fixed to the PBE bulk-optimized positions whereas the three top Zr layers were relaxed. We constructed two structures of Zr/WS$ _{2}$:
 (i)   siteZr-1  configuration,  in which the W atom of the WS$_2$ layer sits above the  Zr atom of the second and forth Zr layer, and  the S layers are in line with the Zr atoms of  the first, third and fifth Zr layer.
 (ii) siteZr-2 configuration, in which the W atom of the WS$_2$ layer is aligned with the Zr atoms of the first, third and fifth layer, and the S atoms are  located above the Zr atoms of the second and fourth Zr layer.
 Optimized geometric structures are shown in Fig.~\ref{Zr}. We found that siteZr-2 is the most favorable configuration.
The equilibrium distances $d_{\rm S-Zr}$  for siteZr-1 and siteZr-2  are  2.64 and  2.57{\AA}, respectively. These  interatomic distances are similar to the bond lengths which have been measured in the bulk zirconium sulfide (ZrS$ _{2} $) crystal with rocksalt structure (2.58{\AA}, Ref.~\onlinecite{ZrS}).
The binding energies E$ _{b} $  follow the ordering  $1.92\mathrm{eV} = E_{b}$[siteZr-2] $ >  E_{b}$ [siteZr-1] $= 1.26$eV; i.e.,
 smaller $d_{\rm S-Zr}$ correlates with a larger binding energy.

\begin{figure}
 \includegraphics[scale=0.6]{fig2.pdf}\\
\caption{\label{Zr}
 Atomic structure of Zr/WS$_{2} $  with two configurations.}
\end{figure}

\textbf{Co/WS$_{2}$  interface}:
In the geometry optimization Co/WS$ _{2}R(0^{\circ})$ and Co/WS$ _{2}R(90^{\circ})$ , the WS$_2$ monolayer
and the top cobalt layer were allowed to relax while the
remaining bottom layers were constrained to their bulk positions.

In order to study the structural and magnetic properties
of  Co/WS$ _{2}R(0^{\circ})$,
we first looked for the stable configuration of  these heterostructures.
In this regard, we gradually move the WS$ _{2}$ parallel to the Co(0001) surface.
Seven atomic configurations of the interface atoms were considered.
After optimizing the structures from these seven initial configurations, we  found  that four  configurations transformed to  the site0-3 structure.
The structures found to be stable  are sketched in Fig.~\ref{str}.
The calculated binding energy as well as other structural parameters of
the investigated configuration of Co/WS$ _{2}R(0^{\circ})$ are listed in Table~\ref{tab:str}.

\begin{table}
\caption{\label{tab:str} Relative total energies $ \triangle E $ (in meV),
calculated binding energy $E_b$ (eV),
average magnetic moment per cobalt atom M ($\mu_B$),
average interface atomic distance ({\AA})
of the three configurations of Co/WS$ _{2}R(0^{\circ})$
}
\begin{ruledtabular}
\begin{tabular}{lccccc}
&&Co/WS$ _{2}R(0^{\circ})$ &&\\
\hline
         &$ \triangle E $& $E_b$ &  M   & $d_{\rm Co-S} $     \\
\hline
site0-1 & 39.2 &-19.72 & 1.654 & 2.34 &   \\
site0-2 & 1.5& -19.76&  1.652 & 2.32 &  \\
 \textbf{site0-3} &\textbf{0.0}    & \textbf{-19.77} & \textbf{1.652}& \textbf{2.31} &  \\
\end{tabular}
\end{ruledtabular}
\end{table}

Our calculations show that site0-3 is the most stable configuration
of Co/WS$ _{2}R(0^{\circ})$.
When the WS$ _{2} $ monolayer is  in contact to cobalt, the equilibrium distances $d_{\rm Co-S}$
range from 2.31 -- 2.34{\AA}. We can see that the smaller $d_{\rm Co-S}$ generally correlates with a larger binding energy and the site0-3 system has strong interface bonding. These  distances are  close to
experimental data obtained for bulk  CoS$ _{2} $  with the pyrite structure (2.32{\AA}, Ref.~\onlinecite{exper}).

\begin{figure}
\includegraphics[scale=0.5]{fig3.pdf}
\caption{\label{str}
 Side and top views of monolayer WS$_{2}$ on the Co(0001) surface with parallel in-plane lattice vectors.}
\end{figure}

To investigate the stable structure of Co/WS$_{2}R(90^{\circ})$, we moved WS$_{2} $ on the Co(0001) surface.
All optimized geometric structures are shown in Fig.~\ref{str90}. We found that
site1-90 is the most favorable configuration (see Table~\ref{tab:str90}). The
differences in binding energy between  site1-90 and the other configurations are of the order of
a few meV.

\begin{figure}
\includegraphics[scale=0.65]{fig4.pdf}
\caption{\label{str90}
 Side and  top views of a $90^{\circ}$ rotated monolayer WS$ _{2} $ on the  Co(0001) surface.}
\end{figure}

\begin{table}
\caption{\label{tab:str90}
Relative total energies $ \triangle E $ (in meV),
calculated binding energy $E_b$ (eV) per unit cell,
average magnetic moment per cobalt atom M ($\mu_B$),
average interface atomic distance ({\AA})
of the different configurations of Co/WS$ _{2}R(90^{\circ})$ .
}
\begin{ruledtabular}
\begin{tabular}{lccccc}
&&Co/WS$ _{2}R(90^{\circ})$ &&\\
\hline
         &$ \triangle E $& $E_b$ &  M   & $d_{\rm Co-S}  $     \\
\hline
\textbf{site90-1} &\textbf{0.0} &\textbf{-5.146} &\textbf{ 1.636} & \textbf{2.342} &   \\
site90-2 & 0.021 & -5.145&  1.636 & 2.343 &  \\
 site90-3 & 4.792    & -5.141 & 1.635& 2.341 &  \\
 site90-4& 0.002   & -5.145 & 1.636& 2.343 &  \\
  site90-5 &  4.863 & -5.140 & 1.635&  2.341 & \\
    site90-6 & 4.884   & -5.140 & 1.635& 2.341 &  \\
     site90-7 & 0.181    & -5.144 & 1.636& 2.343 &  \\
   \end{tabular}
\end{ruledtabular}
\end{table}

\begin{figure}
\includegraphics[width=8cm]{fig5.pdf}
\caption{\label{Fat-band}
Band structure and orbital character of single-layer WS$_2$ and Zr/WS$_2$ interface computed using the PBE and PBE+SOC methods. The thickness of the red lines  is proportional to the orbital weight of the W 5d orbitals in the respective band.}
\end{figure}

\begin{figure*}
\begin{center}
\includegraphics[width=14cm]{fig6.pdf}
\end{center}
\begin{tabular}{lll}
\end{tabular}
\caption{\label{fatCo}
Band structure and orbital character of  Co/WS$ _{2}R(90^{\circ})$ (upper row) and Co/WS$ _{2}R(0^{\circ})$ (lower row) interfaces computed using the PBE and PBE+SOC methods, The labels Maj/Min indicate the majority-spin and minority-spin bands. The thickness of the red lines  is proportional to the orbital weight of the W 5d orbitals in the respective band.}
\end{figure*}

We  investigate the magnetic properties  of the most  stable of  both  Co/WS$_{2}R(0^{\circ})$ and Co/WS$_{2}R(90^{\circ})$. The results indicate that the average  local magnetic moment of a Co atom for Co/WS$ _{2}R(0^{\circ})$ (1.654$\mu_B$/Co)  and  Co/WS$ _{2}R(90^{\circ})$ (1.636$\mu_B$/Co) are  lower than in bulk Co (1.69$\mu_B$/Co) with the hcp structure.
To understand the magnetic moment of each atom in both structures, we considered the Mulliken population analysis  for these systems.
In the interface Co layer, the magnetic moments are generally reduced compared to bulk Co and their values scatter between 1.45 and 1.67~$\mu_B$.
The middle layer almost recovers the magnetic moments of bulk Co, while the Co atoms in the bottom layer of the slab with its free surface reach 1.75$\mu_B$/Co for  both Co/WS$_{2}$ slabs. The covalent bonding between interface Co and S atoms reduces the spin magnetic moment of the Co layer, while the interface S atoms become slightly magnetic (0.025$\mu_B$/S).

Finally, to facilitate a direct comparison  among Zr/WS$ _{2}$, Co/WS$ _{2}R(0^{\circ})$  and Co/WS$ _{2}R(90^{\circ})$,
the binding energy per interface atom was calculated for all three structures.
In all three interfaces, the S atoms are covalently bonded to  Zr and Co, which means that the WS$_{2} $  single layer  is covalently bound to the Co  and Zr slabs and the van der Waals interaction plays only a minor role.
The results show that the zirconium interface has a much stronger binding energy, $E_b = 1.92$~eV/Zr  atom,  with WS$ _{2}$ than cobalt. In Co/WS$ _{2} $, we find that the binding energy between WS$ _{2}$ oriented in the same way as the Co(0001) surface (0.79~eV/Co atom) is higher than for the Co/WS$_{2}R(90^{\circ})$ structure (0.43~eV/Co atom).
This is because the alignment of the two hexagonal lattices of WS$_2$ and Co(0001) allows for better strain accommodation in the Co/WS$_{2}R(0^{\circ})$ interface.

\subsection{Electronic structure of WS$_{2}$-metal interfaces}

The orbital-projected electronic band structure of free-standing WS$_2$
and of the interfacial systems with Zr and Co are investigated  without (PBE) and with (PBE+SOC)
spin-orbit coupling; and the results are presented in Fig.s~\ref{Fat-band} and \ref{fatCo}.
Orbital-projected electronic bands  are displayed only for W atoms because the S, Zr and Co atoms are rather light and we therefore expect  their orbitals  not to be changed significantly under SOC.
The free-standing monolayer WS$_{2} $ is a direct-gap semiconductor with a Kohn-Sham gap of 1.82~eV (1.54~eV when including SOC) located at the $K$ point of the Brillouin zone, in agreement with previous calculations \cite{Zibouche2014,2053-1583-4-1-015026,doi:10.1063/1.4774090}.
As indicated by the red color in Fig.~\ref{Fat-band},  both the valence band maximum (VBM) and the conduction band minimum (CBM) of WS$ _{2}$  are mainly composed of W 5d orbitals.
Taking into account spin-orbit coupling, we observe a large splitting of the VBM (420 meV) at the K point in the first Brillouin zone (see Fig.~\ref{Fat-band}). The splitting for the CBM is 30 meV and thus much  smaller than the VBM splitting, in agreement
with previous studies \cite{Zibouche2014,PhysRevB.94.115131}.
As can be observed in Fig.~\ref{Fat-band}, the band structure of WS$_{2}$ is strongly modified by the interface with Zr.
The semiconducting gap of WS$_{2}$ has disappeared and the Zr atoms introduce occupied bands into the gap which results in the Zr/WS$_{2}$  system displaying metallic behavior.
In particular, an interface state along $\Gamma$ -- M with strong W 5d orbital character is formed that disperses upward and crosses the Fermi level.
The CBM of WS$_2$ is still visible in the projection onto the W 5d orbitals as a parabolic band around the K point located $\sim0.4$eV above the Fermi level.
By comparing the band structure obtained with and without SOC, one notices that the position of the Fermi level and the bands derived from Zr orbitals are almost unaffected. In the W-derived interface state and in the CBM at the $K$ point, a lifting of band degeneracy due to SOC is observed.

To analyze the  band structure  for the Co contact, we performed a similar analysis for the Co/WS$ _{2}R(0^{\circ})$  and Co/WS$ _{2}R(90^{\circ})$  interfaces.
We observe that also the Co interface causes the semiconducting character of free-standing WS$ _{2} $ to disappear. New states cross the Fermi level, both for  the majority and the minority spin electrons (see Fig.~\ref{fatCo}), and consequently the system behaves like a  metal.
In the majority spin band structures of both the Co/WS$ _{2}R(0^{\circ})$  and Co/WS$ _{2}R(90^{\circ})$  interfaces one can observe the fully occupied Co 3d states below $-0.6$ eV.  Some hybridization of these valence band states with the W 5d states is noticeable, but occurs far below the Fermi level.
The contributions of the bands originating from WS$_2$ are most pronounced in
the conduction band of the Co/WS$_{2}R(0^{\circ})$  and Co/WS$_{2}R(90^{\circ})$ interfaces and start at $\sim 0.3$ eV above $E_F$ in the majority spin channel.
In the minority spin band structures of both the Co/WS$ _{2}R(0^{\circ})$  and Co/WS$ _{2}R(90^{\circ})$
a huge number of bands is observed near $E_F$. However, most of these bands are only weakly dispersive and originate from partially occupied Co 3d rather than from W-derived  orbitals. Electronic states with a mixed character start at $\sim 0.5$ eV above $E_F$.
When SOC is included, the distinction between majority and minority spin states is no longer possible, but the combined band structure of both spins is very similar to a superposition of both spin band structures obtained previously without SOC.
In the bands crossing $E_F$, a clear effect of SOC, e.g. SOC-induced avoided band crossings, is not observable.
Also, the magnetic moments of the Co atoms change very little, by less than 1\%.

\subsection{ Schottky barrier at WS$_{2}$-metal interfaces}

\begin{figure}
\begin{tabular}{ll}
 \includegraphics[scale=0.58]{fig7a.pdf} &\\
  \includegraphics[scale=0.58]{fig7b.pdf} &
 \end{tabular}
\caption{\label{SBS}
  Density of states for  WS$_{2}$, Zr/WS$_2$, Co/WS$_{2}R(90^{\circ})$ and  Co/WS$ _{2}R(0^{\circ})$ .
  The energy regions of the conduction and valence band  of free-standing
WS$_{2} $ is indicated by the brown and gray-shaded areas, respectively,
The Schottky barrier $\phi $ is marked by the green arrows.
 The  Fermi level E$ _{F}$  is chosen as the zero of the energy scale.
 The Fermi levels of the free-standing and the contacted systems have been adjusted using the W core levels as reference.}
\end{figure}

To evaluate the  Schottky barrier height (SBH) between the metal and the intrinsic (undoped) semiconductor WS$_2$, the  total DOS  of the M/WS$ _{2}$ (M=Zr,Co) interface displayed in Fig.~\ref{SBS} is compared to the DOS of single-layer, free-standing  WS$_{2}$.
The Schottky barrier $\phi $   can  be  estimated from  the  energy  difference  between  $E_{F}$  of  the  interface system  and  the conduction band minimum (CBM) of WS$ _{2}$ located at the point $K$ in the Brillouin zone.
The 1s core level of W is used as a common reference point for the Fermi levels both in the interface and in pure WS$_2$.
As is seen from the figure, after interfacing WS$_{2} $ with Zr, the Fermi level is located above mid-gap, closer to the CBM, indicating the possibility to inject n-type carriers (electrons) into WS$_2$.
Including the effect of spin-orbit coupling, the Zr contact to the WS$ _{2} $ monolayer shows a SBH of $\sim450$~meV.
Furthermore, the  Co/WS$ _{2}R(0^{\circ})$ contact is found to be an n-type contact, too,  as seen in Fig.~\ref{SBS}. This is in line with recently reported   experiments and calculations for the Co contact with a MoS$_{2} $ monolayer \cite{PhysRevB.95.075402,doi:10.1021/nl4010157}.
The  Schottky barriers are  $\phi  = 620$ and
830~meV  for Co/WS$ _{2}R(0^{\circ})$  and Co/WS$ _{2}R(90^{\circ})$, respectively.
When SOC is neglected, the electronic structure of the interfaces changes very little, but the gap of WS$_2$ and the position of $E_F$ in intrinsic WS$_2$ are affected (cf. Fig.~\ref{Fat-band}). As a result, the SBHs for all metal contacts are increased by 140 meV if SOC is neglected.

\subsection{Quantum transport at WS$_{2}$  and Co/WS$_{2}$ }

Since the CBM and VBM of WS$_2$ are both located a the $K$ point, the WS$_2$ sheet in a nanoscale transistor
should preferentially be oriented in such a way that the current flows along the $\Gamma-K$ direction in the Brillouin zone, i.e. along the atomic zig-zag chains of WS$_2$ in real space.
The knowledge gained from the adsorption studies reported above are used to construct atomistic models of nanoscale spintronics devices.
The most stable configurations of Zr/WS$_{2}$ and Co/WS$_{2}$ follow from the results of the previous section.
 Although Co/WS$_{2}R(0^{\circ})$ is more stable than Co/WS$_{2}R(90^{\circ})$, we used the latter interface geometry to model a stripe of Co deposited on WS$_2$ because this leads to a computationally tractable set-up. A Co stripe with Co/WS$_{2}R(0^{\circ})$ would require a much larger supercell with more than 600 atoms, and such a system is too large for a quantum transport calculation even on a supercomputer.
 For comparison, we also  consider  a smaller system, a Co cluster deposited on WS$_2$.

The electronic conductance is calculated with the PWCOND code using an open
 system consisting of
 (i) a scattering region comprising the WS$_{2}$  monolayer  and a chosen interface to the Zr/WS$ _{2} $ electrodes, and
 (ii) the left and right (in principle semi-infinite) Zr/WS$_{2} $ leads.
The scattering region has to be large enough to avoid the interaction between right and left leads.
In our calculations, the length of this region is  36.70~{\AA}  along the transport direction (twelve unit cells between the electrodes) that included 24{~\AA} free-standing WS$ _{2} $  and 12.70~{\AA} Zr/WS$_{2}$, see Fig.~\ref{fig:diode}.
The leads are described by calculating the complex band structure of a periodic supercell containing four bottom layers and three top layers of Zr on WS$_{2}$.

 \begin{figure}\begin{tabular}{l}
 a)  \hfill \\
 \includegraphics[scale=0.65]{fig8a.pdf} \\
 b)  \hfill \\
 \includegraphics[scale=0.65]{fig8b.pdf}
  \end{tabular}
 \caption{\label{cond}
a) Transmission of the free-standing WS$_2$ sheet between Zr contacts, as shown in Fig.~\ref{fig:diode}, as a function of energy using the PBE (squares) and PBE+SOC (diamonds) methods, together with exponential fits (dashed lines).
b) Transmission as a function of perpendicular momentum $k_x$ at $E_F+0.2$eV. }
 \end{figure}

\begin{figure*}
\begin{center}
\includegraphics[width=17cm]{fig9.pdf}
\end{center}

 \caption{\label{condCo}
 Optimized atomic structure (a,d), transmission as function of the electron energy (b,e), and transmission as function of perpendicular momentum $k_x$ at $E_F+0.2$eV (c,f) for the WS$_{2}$/Co cluster (upper row) and WS$_{2} $/Co stripe gate (lower row). }
   \end{figure*}

First we consider the quantum-mechanical transmission of a clean WS$_2$ sheet clamped between two Zr contacts. For injection into the conduction band of WS$_2$, the electrons must overcome a barrier (for macroscopic devices equal to the Schottky barrier calculated above). This is in line with the transmission $T(E)$ exponentially increasing with electron energy, as shown in Fig.~\ref{cond}a) both for the calculations with and without SOC.
This device works like a diode with an I-V-characteristics described by $T^{-1} \, dT/dE = 35(eV)^{-1}$ for small electron energies.
Following eq.~\ref{eq:T_k}, electrons with all possible momenta $k_x$ perpendicular to the transport  direction contribute to the overall transmission.
With our choice of the supercell, the $K$ point is folded back to the $\bar \Gamma$ point of the supercell; thus we expect the main contribution from electrons with $k_x \approx 0$. This is confirmed by the results of the PBE+SOC calculations, see Fig.~\ref{cond}a).
However, in the calculations neglecting SOC, a sharp rise of $T(E)$ is observed for electrons with an energy of 0.2eV above $E_F$.
Analyzing the transmission as function of $k_x$, we find that this rise is due to maxima at $k_x = \pm 0.04 a_x/\pi$, see Fig.~\ref{cond}b).  We ascribe this observation to quantum-mechanical transmission resonances that depend both on the de Broglie wave length of the transmitted electron in the conductive channel as well as on the finite channel length.
We note that, in the calculations neglecting SOC, states with wave vector $\vec k$ and $-\vec k$ must be equivalent due to time-reversal symmetry.
In the calculations including SOC, transport with wave vector $\vec k$ and $-\vec k$ are no longer equivalent, but correspond to electrons at the inequivalent points $K$ and $K'$ in the Brillouin zone of WS$_2$. This also shows up in the asymmetry of the lower $T(E,k_x)$ curve in Fig.~\ref{cond}b).

Next we are adding a Co cluster
or a  Co stripe  in the center region, as shown in Fig.~\ref{condCo}a) and d), and relax the geometry until we find a stable interface.
The magnetization of Co breaks the time-reversal symmetry in the channel and mixes the $K$ and $K'$ valleys of WS$_2$.
Because of this mixing and the qualitative similarity of the results for $T(E)$ with and without SOC, we consider it sufficient to study the
transmission in the presence of a Co gate electrode without SOC.
In Fig.~\ref{condCo}b) and e), we can see  plots of the spin-dependent transmission for
the WS$_{2}$/Co cluster and the WS$_{2}$/Co stripe.
As an overall trend, the transmission curves are still increasing with energy, as in the case of pure WS$_2$, but show additional structure.
The absolute value of the transmission is lower than in the clean case.
Both observations point to a small additional barrier for the electrons imposed by the proximity of the Co cluster or stripe.
This proximity effect is spin-dependent.
For the WS$_{2} $/Co stripe the majority spin transmission is mostly (in particular for $E>E_F$) smaller than the minority spin transmission, while this trend is reversed for WS$_{2}$/Co cluster.
We attribute these observations to quantum-mechanical interference effects which play a role in nanoscale devices such as the one considered here.
The relation between a change in the channel potential and a change in transmission is, however, a subtle one, since
not only the barrier height, but also the exact geometry and abruptness of the barrier affect the quantum-mechanical transmission amplitude.
Analyzing the transmission as function of $k_x$ for the highest electron energy investigated, $E_F + 0.2$eV, we observe that the transmission resonance found for the pure WS$_2$ sheet has become very sharp by the addition of the Co gate, and displays different maximum transmission in the majority and the minority spin channel, see Fig.~\ref{condCo}c). The effect of a stripe-shaped Co gate is somewhat different: The resonances have nearly equal height in both spin channels, but their maxima as function of $k_x$ are slightly shifted, see Fig.~\ref{condCo}f). These equal heights explain why, nder 'open gate' condition at $E_F + 0.2$eV, both spin channels show nearly equal overall transmission and the spin polarization of the transmitted current tends to vanish.

\section{Conclusion}
In conclusion, we employed first-principles calculations to investigate various components of a future spintronics device based on a single-layer WS$_2$ sheet. Our calculations show that both Zr and Co can be used to form stable contacts on WS$_2$ that allow for injection of carriers into the conduction band. The most stable atomic structure of the interface can be deduced from the calculations, and it is shown that the magnetic moment of the Co surface persists in the presence of WS$_2$. Moreover, quantum-mechanical transport calculations show that a single-layer WS$_2$ sheet clamped between Zr electrodes behaves like a Schottky diode with a sharp I-V-characteristics. A gate electrode of Co can be used to control the spin polarization of the current.
For the nanoscale device studied by us, we find that the spin polarization sensitively depends on the geometrical shape of the gate and on the energy of the electrons. As a direction for future work, one could attempt a generalization of these findings to larger devices where semiclassical transport theory would be applicable.

\section*{Acknowledgements}
H.K. is grateful to the Iranian Ministry of Science, Research and Technology for a travel scholarship.
We gratefully acknowledge the computing time granted by the Center for Computational Sciences and Simulation (CCSS) of the University of Duisburg-Essen and provided on the supercomputer magnitUDE (DFG Grant No. INST 20876/209-1 FUGG and INST 20876/243-1 FUGG) at the Zentrum f{\"u}r Informations-und Mediendienste (ZIM).