\section{Introduction}
The thermal evolution of an interstellar cloud with primordial composition is deeply driven by the
collisional and radiative processes occuring in the medium. In order to be properly described, it is
essential not only to correctly model the dynamics but also to provide a complete description of the
time
variation of the gas temperature. To address this need, it is firstly required to identify the
possible
cooling mechanisms in the intergalactic medium (IGM); secondly, the models seek for functions that can
be
easily adopted in the models to reproduce each of the heating/cooling channels. In the context of IGM
simulations and low metallicity interstellar medium (ISM) several works have been produced adopting
this
workflow\citep[e.g.,][]{black1981,shapiro_hydrogen1987,cen_hydrodynamic1992,glover2007,glover2008,glover2009,glover2015}; the
same holds in the case of early Universe chemistry \citep{galli2013}, where the system is mainly consisting
on hydrogen and helium.
Mechanical ways of energy exchange are found in shocks and turbulence \cite[e.g.,][]{johnson_cooling2006,kazandjian2016,kazandjian2016b,vasiliev2017a}. The most
relevant coolants at low
temperatures are metals and molecules, both in gas phase and as dust in the intergalacting and in the
interstellar medium. According to the radiation field in which the gas and the dust is embedded,
heating mechanisms should be also taken into account in the thermal balance (e.g., \cite{vasiliev2017b}).
On cosmological scales, the presence of even small
traces of metals can determine a
different fate in terms of masses of the first stars because of the line cooling \citep[e.g.,][]
{bromm2003,yoshida2007}; gravitational instabilities are expected in the case of increasing
metallicity content \citep{tanaka_gravitational2014}, together with thermal instabilities
\citep{omukai_thermal_inst_2015}. Indeed, the original gravitationally collapsing cloud can fragment
or keep
accreting according to the thermal conditions present in the gas \citep{omukai2000,latif2016}. At the
limit,
the presence of coolant agents (both atomic and molecular) and a radiation field which has an
intensity
below the critical value can allow for the formation of supermassive black holes via direct accretion
\citep[e.g.,][]
{haiman_h1996,sugimura2016}. In the absence of heavier elements like carbon and oxygen (and the
consequent
possibility to form molecules like CO) the only way to cool the gas down to temperatures below few
hundreds
Kelvin is through rovibrational transitions of H$_2$ and its isotopic variants, the latter allowing to
cool
the gas even at temperatures below 100~K. For this reason, the description of the energy transfer
associated
with the H$_2$ line cooling deserves to be rigorously described, also by adopting the most complete
data for each of the possible collisional partners. Specifically, in this paper, the case of the
inelastic
collisions of H$_2$ with atomic hydrogen is studied, explicitely introducing the reactive channel.
The work is organized as follows: in Section~\ref{methods} the basic concepts of the collisional
pathways in
the H$_3$ system are provided, together with the quantum mechanical methods adopted in the calculation
of
the cross-sections and the equation for the calculation of the cooling function. The kinetic model adopted and the chemical pathways included are also described;
in Section~ \ref{multivariate}, the results are reported. Moreover, a regression analysis of the data obtained for the cooling function is performed
to derive a multivariate dependence of the cooling function on the gas temperature and density.

\section{Methods and equations.}
\label{methods}

In order to describe the time evolution of the level population for a $N$-levels system, the rate
equation for each level should be provided. In the high density regime, the levels are distributed
according to
Maxwell-Boltzmann (e.g., \cite{coppola2011_radiative}).  This hypothesis is in general not valid and
the level population
can be found by explicitely solving the rate equations which derive from the chemical processes
introduced in the kinetics.
In order to find the level population, two general approaches are usually adopted: on one hand, the
time evolution of the levels population $\mathbf{x}$ can be
found by solving the resulting system of ODEs
\cite{coppola2011a,coppola2011b}; otherwise, it can be assumed that the level population is in steady-state
\cite{martin1996,tine1998,coppola2012}. The calculations reported in this paper have been performed
using
the second assumption, that corresponds to imposing that the time derivative of the rate equations is equal to 0:
\begin{equation}
\frac{dx_i}{dt} = 0, ~~ \forall i.
\label{steady}
\end{equation}
At each temperature and density, the whole problem of finding the steady-state population
can be translated into a linear system formalism. Let $\mathbf{M}$ be the matrix
that, when multiplied by the column vector of the population densities $\mathbf{n}$, results in the right
hand side of the system of ordinary differential equations; the rate equations can be written then as \citep{tine1998}:
\begin{equation}
\frac{d\mathbf{n}}{dt} = \mathbf{M} \cdot \mathbf{n}\\
\label{odes}
\end{equation}
Then, the level population derives from the chemical channels that most effectively redistribute them among the rovibrational manifold; the choice of such channels
depends on the system of interest. The case reported in this paper corresponds to the typical freeze-out abundances that can be found in the early Universe
chemistry. The
H$_2$ collisional partners included are H, He and H$^+$; moreover, the formation and destruction pathways for the molecular hydrogen are the associative detachment
of H and H$^-$ and the dissociative attachment of H$_2$, respectively. Radiative transition are inserted and the data by \cite{simbotin1998} have been adopted. The
relative abundances of He and H$^+$ respect to H are 10$^{-1}$ and 2$\times10^{-4}$. The reaction rates
included for the formation and destruction channels of H$_2$ have been taken from \cite{coppola2011a} and \cite{coppola2007}. The collisional data with He are
fully available for the whole H$_2$ rovibrational manifold \citep[F. Esposito, private communication and][]{esposito2017}. The collisional data for the system H
$_2$-H$^+$ have been included using the fits provided by \cite{gerlich1990}; transitions up to ($v=0, j=8$) are therein reported. Finally, the reactive H$_2$-H
collisions have been included; details on the adopted data are described in the following. According to the reactive data provided for H$_2$-H, the number of
levels included in the present calculations is 55, that corresponds to ($v=3, j=18$).

\subsection{Updates collisional data: H$_2$--H reaction rates.}
The modeling of accurate cooling functions relies on the calculations of H$_2$-H collisional rate coefficients. Such calculations are challenging since two
 processes are in competition during collisions between H$_2$ and H:\\
-the inelastic process:
$$
\mathrm{H}_2(v,j) + \mathrm{H}' \to \mathrm{H}_2\mathrm{(v',j') + H'}
\label{process1}
$$\\
-the exchange process:
$$
\mathrm{H}_2(v,j) + \mathrm{H}' \to  \mathrm{H'H(v',j') + H}
\label{process2}
$$
where $v$ and $j$ designates the vibrational and rotational level of H$_2$, respectively. This is explained by the reactive nature of the H$_3$ system. The
obtention of accurate collisional data requires to consider simultaneously both processes during the calculations. In particular, the ortho--para-H$_2$ conversion
can only occur through the hydrogen exchange channel.

Ro-vibrational relaxation of H$_2$ by H have been extensively studied using quasi-classical trajectory calculations \cite[][and references therein]{Mandy:93}.
Unfortunately, the inability of quasi-classical trajectory treatments to conserve the vibrational zero-point energy renders this method unreliable near reaction
thresholds. Alternatively, Flower and co-workers \citep{Wrathmall07,Wrathmall07b} computed ro-vibrational rate coefficients for temperatures ranging from 100 to
6000~K using a quantum close coupling approach neglecting the reactive channels arguing that reactivity is negligible for temperatures up to 6000~K. They did not
consider the ortho--para-H$_2$ conversion process and neglect the vibrational relaxation that occur through the exchange process that is expected to be important
even at low temperatures.

Hence, there were still a lack of highly accurate collisional data until we recently presented quantum mechanical calculations of cross sections for the
collisional excitation of H$_2$ by H including the reactive channels \citep{Lique:12:2,Lique:14,lique:15} using the state-of-the-art PES of \cite{Mielke:02}.
We refer the reader to these papers for full details on the scattering calculations. In summary, calculations were performed using the almost exact close coupling
approach. New collisional data were obtained for the ro-vibrational relaxation of highly excited H$_2$ (with internal excitation up to $\simeq$ 22000~K) for
temperatures ranging from 100 to 5000~K. The theoretical results were checked against available experimental data and a good agreement was found for both ro-
vibrational relaxation \citep{lique:15} and ortho--para-H$_2$ conversion process \citep{Lique:12:2}.

The new results significantly differ from previous data widely used in astrophysical models \citep{Wrathmall07,Wrathmall07b}. Important deviations are observed at
low temperatures for ro-vibrational transitions whereas, for pure rotational transitions, the mean deviations occur at high temperatures. These differences are
principally due to the inclusion of the reactive channels in the scattering calculations.

\subsection{Cooling function}
\label{cooling}
The calculation of the cooling function requires information about the level population, computed at each gas temperature, and on the energy gaps and Einstein
coefficients between the levels included in the model. In particular, for a generic molecule $mol$, the cooling function in defined as:
\begin{equation}
n_{mol} \Lambda = \sum_j \sum_{i<j} n_j A_{ji}\beta_{ji}(E_j - E_i)
\label{cooling_function_expression}
\end{equation}
with $\Lambda$ in erg s$^{-1}$, n$_{mol}$ the density of the molecule, $n_j$ the density for the $j^{th}$
level and $\beta_{ji}$ is the escape probability of the emitted photon. The assumption under which the
calculations here presented are performed is that the medium is
optically thin; in this case, all the emitted photons can escape from the medium without being re-absorbed
and in Eq.~\ref{cooling_function_expression} the term $\beta_{ji}$ is equal to 1. The calculation of the
cooling function has been performed using the code \texttt{FRIGUS}
developed
by \cite{kazandjian2019}. No assumptions have been adopted on the level population between ortho- and
para-H$_2$, that have been explicitely calculated according to the steady-state approximation and detailed
balance between radiative and collisional rates. Stimulated process are included in
\texttt{FRIGUS} where a Planckian radiation field has been implemented by default to mimic the cosmic
microwave background at a certain redshift $z$; however, the calculations reported in this work have been
performed for a radiation temperature equal to zero. The
Einstein coefficients have been calculated by \cite{simbotin1998}; the energy levels used have been taken
from the \href{https://www.physast.uga.edu/ugamop/mainh2.html}{UGA - Molecular Opacity Project Database}
and the collisional reaction rates adopted are the ones computed by \cite{lique:15}.

\section{Results}
\label{multivariate}

\subsection{Cooling function}
In Fig.~\ref{cf} the cooling function obtained adopting the updated collisional reaction rates by
\cite{lique:15} is reported as a function of the kinetic temperature for several values of the gas density
(black continuous curves, from the low to the high density limit, corresponding to the lower and upper curves, respectively).
The dependence from the density follows what shown by \cite{lipovka2005} for HD: the curves tend to converge
for high values of density to
the LTE cooling function, i.e. to the cooling function that can be obtained by assuming that the level
population is described by a Maxwell-Boltzmann distribution for the energy levels. This case corresponds to
a gas in which the fractional abundances of internal rovibrational levels is thermalized, while in the more
general case this situation is not necessarly satisfied.

\begin{figure}
\includegraphics[width = 0.5\textwidth]{1.eps}
\caption{Cooling functions at different densities adopting the new data \citep{Lique:12:2,Lique:14,lique:15}
and the software \texttt{FRIGUS} (black continuous curves). From bottom to top, the
corresponding
densities are:
10$^{2}$ m$^{-3}$, 10$^{3}$ m$^{-3}$, 10$^{4}$ m$^{-3}$, 10$^{5}$ m$^{-3}$, 10$^{6}$ m$^{-3}$, 10$^{7}$ m$^{-3}$, 10$^{8}$ m$^{-3}$, 10$^{9}$ m$^{-3}$, 10$^{10}$ m$^{-3}$, 10$^{11}$ m
$^{-3}$, 10$^{12}$ m$^{-3}$, 10$^{13}$ m$^{-3}$, 10$^{14}$ m$^{-3}$
As
a comparison, the fit provided by Glover \& Abel~2008 is also shown (blue dashed curve). The dash-dotted curves correspond to
the fit provided in the present paper; see text for details.}
\label{cf}
\end{figure}

\begin{figure}
\includegraphics[width = 0.5\textwidth]{2.eps}
\caption{3D rendering of the cooling function at different densities and kinetic temperatures using \texttt{FRIGUS} (Kazandjian \& Coppola 2019). SI units are used.}
\label{3d}
\end{figure}
In the same figure, the most recent fit for H$_2$/H
cooling by \cite{glover2008} is also reported, which is based on the data by \cite{Wrathmall07}.
At low temperatures T$\sim 100~K$,
deviations up to an order of magnitude can be appreciated.
Together with the different collisional data implemented,
such a difference may be explained assuming that their fit
has been performed assuming an ortho-to-para ratio 3:1.
In the absence of a full state-to-state description of the kinetics of rovibrational levels, assuming an ortho-to-para
is the only way to proceed in the calculations. Moreover, collisional processes with other atomic or
molecular partners may allow to reach the statistical ortho-to-para in a faster way, allowing to confidently use the 3:1
value in the simulations. For example, it is well
known that collision with protons are very effective in the ortho-to-para conversion of H$_2$, as reported by
\cite{gerlich1990} and recently confirmed by \cite{grozdanov2014}. However, as
also acknowledged in the introduction of the work by \cite{glover2008}, deviations from the 3:1 ortho-to-
para ratio are expected at low temperatures, as explicitely captured by performing the calculations using
\texttt{FRIGUS}). The ideal procedure would then prescribe to solve the kinetics of rovibrational level of H$_2$ in each particular case and to compute the actual level population and cooling {\it on-the-fly}.

In Fig.~\ref{3d} a 3D-rendering of the cooling functions surface is reported with a colour code to
distinguish more easily the values of the independent variables and the cooling functions themselves.

\subsection{Fit}
\label{section_fit}
In order to allow for a faster usage of the calculated cooling function at several kinetic temperatures and densities, we provide the users with a fitted expressions for the cooling functions; the same expression used by \cite{lipovka2005} in the case of HD is used:
\begin{equation}
log10(\Lambda) = \sum_{l, m = 0}^4 D_{lm} (log_{10}{T})^l (log_{10}{n})^m
\end{equation}
where the numerical values of the logarithms are taken expressing the temperature in Kelvin and the
density in cgs units; the resulting cooling function $\Lambda$ has units erg $\times$ s$^{-1}$. The
parameters are provided in Table~\ref{fit_parameters}. In Fig.~\ref{cf} the comparison between the
computed data (black full) and the fit (green dashed curves) is also reported, showing very small
errors (the largest being $\sim$10$^{-3}$).

\begin{table*}
\centering
  \begin{tabular}{@{}cccccc@{}}
  \hline
  \hline
        &   m = 0          & m = 1            & m = 2          & m = 3          & m = 4     \\
  \hline
  l = 0 & -1.07761178e+02 & +8.50704285e+00  & -3.08850636e-01 & -3.97357274e-01 & +3.65589231e-02\\
  l = 1 & +1.17901741e+02  & -1.09489742e+01 &  +2.51708582e-01 & +5.47452438e-01 & -4.89055533e-02\\
  l = 2 & -6.61721218e+01 &+5.95232129e+00   & -1.10639748e-01  &-2.92423859e-01  &+2.57375696e-02 \\
  l = 3 &+1.67152116e+01   &-1.43513388e+00  & +2.84953800e-02 &+7.02040444e-02  &-6.18478233e-03 \\
  l = 4 & -1.55475014e+00 &+1.29639563e-01   &-3.13943372e-03   & -6.36261310e-03 &+5.65797161e-04 \\
 \hline
 \hline
\label{fits}
\end{tabular}
\caption{Parameters for the cooling function fit as reported in Sec.~\ref{section_fit}; $\Lambda$ has units erg $\times$ s$^{-1}$. These parameters are valid in the density range [10$^2$-10$^{14}$]~m$^{-3}$ and temperature range [100-4000]~K.}
\label{fit_parameters}
\end{table*}

\section{Conclusions}
\label{conclusions}
Thanks to available updated cross-sections for the inelastic processes H$_2(v,j)$+H $\rightarrow$ H$_2(v',j')$+H \citep{lique:15} and the state-to-state software
\texttt{FRIGUS} \citep{kazandjian2019}, a new cooling function depending both on gas temperature and density has been evaluated, which include the rovibrational
levels up to ($v=3, j=18$). The inclusion of reactive channels increased the cooling effect at high temperatures, together with a larger set of included
rovibrational levels in the energy exchange evaluation

For facilitating the usage of these results, a multivariate analysis is performed and the resulting fit is reported together with the parameters in Sec.~
\ref{section_fit}.  The computation has been performed for radiation temperature equal to zero, to compare the results with previous calculations; however, if
needed, the software \texttt{FRIGUS} can be used to recover the cooling function at different radiation temperature (i.e. different epochs in the case of
simulations describing early Universe chemistry or early star formation).

\section{acknowledgments*}
C.M.C greatly acknowledges Regione Puglia for the project ``Intervento cofinanziato dal Fondo di
Sviluppo e Coesione 2007-2013 – APQ Ricerca Regione Puglia - Programma regionale a sostegno della
specializzazione intelligente e della sostenibilit\`a sociale ed ambientale - FutureInResearch''.
C.M.C. also acknowledges Daniele Galli who strongly encouraged the calculations reported in this work.

\bibliographystyle{mn2e}


\section{Introduction}
Seismic data contain noise that must be removed to avoid reducing final image quality. In marine data, this includes cable and swell noise. Traditional methods of noise attenuation include FX deconvolution \citep{gulunay1986fxdecon} and median filtering \citep{liu20081d}. These methods rely on the signal component of the data being coherent and the noise component being incoherent, so a gather domain in which this is true must be chosen. Although generally effective, these methods require human intervention to choose parameters, such as window sizes, and may require multiple iterations in different gather domains. This causes them to have high labor and computational cost.

In order to reduce the duration of seismic data acquisition, simultaneous source or blended acquisition may be used. This occurs when another shot is initiated while arrivals from the previous shot are still being recorded, leading to interference. Removing the interference from shot records separates the data for each shot, allowing processing to continue using regular processing methods. This process is called deblending, and the interference is referred to as blending noise. Deblending methods typically rely on the blending noise being incoherent in domains other than common shot gathers, due to randomness in shot initiation times, while the desired signal remains coherent. Denoising methods may thus be used to remove the blending noise \citep{huo2012simultaneous}. Alternatively, an inversion approach may be used to explicitly separate the data into different shot records that are coherent \citep{moore2008simultaneous}. The inversion approach is usually even more computationally expensive than the denoising methods, and, furthermore, requires knowledge of the initiation time of each shot. The latter issue poses a difficulty in applying the method on old datasets or to remove interference from other nearby surveys being performed simultaneously, where these times may not be available.

Machine learning, in the form of deep neural networks, has recently been used to achieve state of the art results in image denoising tasks \citep{zhang2017beyond}. It is capable of achieving better denoising performance at a lower computational cost than traditional denoising methods, while also requiring less human interaction. The network is trained to identify noise by presenting it with examples of noisy data and the corresponding noise or noise-free data.

Several recent applications of deep learning in seismic data denoising \citep[e.g., ][]{jin2018seismic,liu2018random,yu2018deep,zhang2019random}, and deblending \citep{baardman2019classification,slang2019using}, demonstrate that the benefits of this approach observed in image denoising transfer to seismic data.

Previous seismic applications of deep learning tend to begin training from randomly initialized weights, leading to long training times despite using relatively shallow, custom-designed networks. One could alternatively use deeper networks such as a U-net \citep{ronneberger2015u} that is commonly used in computer vision tasks, and was recently found to be successful for seismic interpolation and denoising by \citet{mandelli2019interpolation}. This not only enables the network to learn more complex operations, potentially leading to better results \citep{simonyan2014very}, but also creates the opportunity to start training from pretrained weights. For popular network architectures that can be used to construct the U-net, such as ResNet34 \citep{he2016deep}, these pretrained weights, trained on tasks such as classifying images in the ImageNet dataset \citep{russakovsky2015imagenet}, are widely available for download. As the initial layers in the network perform basic operations such as identifying edges, the weights often transfer well to other tasks \citep{yosinski2014transferable}.

Another potential shortcoming of some previous proposals that use deep learning in seismic applications is the failure to exploit the high dimensionality of seismic datasets. Many of these proposals only operate on two dimensional gathers of data, ignoring the information contained in adjacent gathers. Figure \ref{fig:neighbour_data} demonstrates the similarity of adjacent common offset gathers, providing information that could be used to more accurately estimate the signal. This is similar to applications of deep learning for video denoising, where the similarity of adjacent frames is exploited by providing several adjacent frames as input when the model is denoising the central frame \citep{claus2019videnn}.

\plot{neighbour_data}{}{Three adjacent common offset gathers on either side of a central gather exhibit the redundant information contained in higher dimensions of seismic data.}

Finally, several previous proposals were only trained using one dataset. As a result, the network will not have been exposed to all of the variations it may encounter in seismic data, and so its behavior on other datasets is unpredictable. Training using a diverse range of datasets allows the network to experience a wide range of situations and so reduce the risk of overfitting.

Our hypothesis is that a U-net, based on a pretrained ResNet, and provided with information from multiple adjacent gathers, will produce an effective tool for denoising seismic data. Applied to blended data in a gather dimension in which the blending noise is incoherent, it may also be used for deblending. By training it on a diverse training dataset, we believe it will exhibit the ability to generalize well to other datasets not used during training.

\section{Materials and Methods}
\subsection{Network Architecture}
We use a U-net model \citep{ronneberger2015u}, with a ResNet34 architecture as the encoder \citep{he2016deep}, using the implementation in Fast.ai version 1.0.53. The channel dimension is used to provide adjacent common offset gathers as input. ResNet34 expects three input channels. Thus, when the number of adjacent common offset gathers provided on either side of the gather being denoised is not one, we modify the first convolutional layer to have the appropriate kernel shape.

\subsection{Training}

We train the network using synthetic data, which we generate with an acoustic propagator and twenty randomly generated wave speed models. A slice through one of these models is shown in Figure \ref{fig:synthetic_model}. To ensure that the network behaves robustly on unseen data, these wave speed models exhibit more extreme variability than is generally found in reality. We use a Ricker wavelet source with a peak frequency of 35~Hz and a source and receiver spacing of 5~m. Each model is used to create one dataset with 300 towed receivers and 250 shots, with a shot record length of 1.2~s and a time sample interval of 0.001~s. The data are synthetically blended. This is achieved by creating a continuous recording for each dataset, where the shot records from the dataset are added with a time delay between shots. The average time delay and the jitter in the time delay are randomly chosen for each dataset between 0.5 and 1.5~s, and between 0.1 and 0.6~s, respectively. As this time delay is sometimes shorter than the shot record length, the shots may overlap. We then extract overlapping sections of this record corresponding to each shot record, including the blending noise. To increase the ability of the model to recognize other forms of noise, we also add data from real datasets to the synthetic data. This not only adds realistic noise, such as cable and swell noise, but, since the real datasets also contain signal, simulates interference from other nearby surveys. The datasets used are field data from cruises \citet{ew0007}, \citet{ew0207}, and \citet{ew0210}. White Gaussian noise is also added. Example common offset gathers of the input and target synthetic data are shown in Figure \ref{fig:synth_data}. Data from two of the wave speed models are reserved for use as a validation dataset.

\plot{synthetic_model}{}{A vertical slice through one of the synthetic models used to generate training data.}
\plot{synth_data}{}{An example noisy common offset gather and the corresponding noise that are used as the input and target during training.}

We initialize the ResNet portion of the model using pretrained weights. These are the weights obtained by training on the ImageNet dataset. We use the default version of these weights distributed with PyTorch \citep{paszke2017automatic}. As these weights are designed for three input channels (the red, green, and blue channels of ImageNet images), we replace the weights in the first convolution with the sum of the pretrained weights in the channel dimension, divided by the new number of input channels, repeated for each new input channel:
\begin{equation}
        W_{c,x,y} = \frac{\sum_{i=1}^3W^p_{i,x,y}}{N},
\end{equation}
where $W$ are the weights used in the first convolutional layer of the network, $W^p$ are the corresponding pretrained weights, $c$, $x$, and $y$ are the channel, vertical, and horizontal indices, respectively, and $N$ is the new number of input channels. The remaining weights in the network (i.e., those not in the ResNet portion) are randomly initialized.

During training, the noisy data are the inputs, and the corresponding noise (the input minus the signal) is the target. We divide each input and target gather by the standard deviation of the input gather. As the pretrained ResNet weights expect the input to have 224 pixels in both height and width, we randomly extract squares of this size from the data. One such square is extracted from each common offset gather in the dataset per epoch. To further increase the range of inputs that the model is exposed to during training, we apply transformations to the data. These convolve the data in time with a random kernel (simulating the use of different source wavelets), randomly set the stride in the time dimension between one and five (altering the apparent frequency of the data), and randomly choose the stride used to select the adjacent common offset gathers between one and four (exposing the model to different receiver spacings).

We use the 1cycle training method \citep{smith2018disciplined} and the AdamW optimizer \citep{loshchilov2017fixing}, with the mean squared error loss function. We initially only train the weights in the model that were randomly initialized, leaving the pretrained weights fixed. We use a learning rate of 0.01 for five epochs. We then train all of the weights for 350 epochs, using Fast.ai's discriminative learning rate that increases from $1\times 10^{-6}$ to $1\times 10^{-3}$ with increasing depth in the model. A batch size of 32 is used throughout training.

\subsection{Test Datasets}
To test the trained model on a variety of inputs, we select four 2D marine streamer datasets from different regions of the world. These are the North Sea, Venezuela, Norway, and New Zealand (Mobil AVO Viking Graben Line 12, and cruises EW0404 \citep{ew0404}, EW0307 \citep{ew0307}, and EW0001 \citep{ew0001}, respectively).

As none of these datasets use blended acquisition, we synthetically blend the data from the North Sea, using the blending procedure described above, with a time delay between shots of $1.8 \pm 0.2$~s.

To create a common mid-point (CMP) stack image using the North Sea data, we sort the data into CMP gathers, apply normal moveout (NMO) correction, and stack. We use an NMO velocity profile that is constant at 1500~m/s up to 0.5~s, rises to 2000~m/s at 2~s and then remains constant.

The model operates on patches of data with 224 pixels on each side. To apply it to a whole gather, we divide the gather into overlapping patches, apply the model to each, and use the mean value in the overlapping regions. We use a stride of 56 pixels in both time and shot dimensions.

\section{Results}
\subsection{Number of adjacent common offset gathers in input}
We train the network using, as additional channels in the input, varying numbers of adjacent common offset gathers on both sides of the gather that corresponds to the target. Each configuration is trained using the training procedure described above, but with only 10 epochs in the second training stage. The training is repeated 45 times for each configuration, with different random initializations, and the minimum mean squared error loss achieved on the validation dataset is recorded.

The results, displayed in Figure \ref{fig:neighbour_comp}, show that the loss decreases rapidly from 0 to 1 adjacent gathers, indicating that the model uses the information contained in these additional channels effectively. The loss continues to decrease up to 3 adjacent gathers, before increasing slightly and then remaining almost constant up to 8 adjacent gathers.

\plot{neighbour_comp}{}{The best results are obtained when three adjacent common offset gathers on both sides of the gather being denoised are provided in the input.}

Subsequent results use 3 adjacent gathers.

\subsection{Deblending}
We apply the trained network to the blended North Sea data. Figure \ref{fig:vg_gathers} shows the result on one common offset gather. We calculate the mean signal-to-noise ratio using
\begin{equation}
\text{SNR}(data) = \frac{1}{n_s}\sum_{s=1}^{n_s} 10\log_{10}\left(\frac{||\mathit{signal}_s||^2_2}{||\mathit{signal}_s - \mathit{data}_s||^2_2}\right),
\end{equation}
where $\mathit{signal}$ is the unblended dataset, $s$ is the shot index, and $n_s$ is the number of shots in the dataset. Using this metric, the SNR of the input data is -3.6~dB, while that of the output deblended data is 16.5~dB. This is comparable with improvements in SNR reported using other techniques on different datasets, such as \citet{chen2018deblending} reporting an increase in SNR from 1.62~dB to 16.55~dB, and \citet{zu2018hybrid} reporting an increase from 0~dB to 19.18~dB.

\plot{vg_gathers}{}{Common offset gathers before (input) and after deblending, and the unblended data.}
\plot{vg_stacks}{}{CMP stack images produced using the North Sea data, before (input) and after deblending, and using the unblended data. Deblending removes the blending noise artifacts. The underlying signal is reduced, but still visible.}

We create CMP stack images to produce the result shown in Figure \ref{fig:vg_stacks}. The blending artifacts are less severe in the output.

\subsection{Noise removal}
When we apply the model, without any modification, to three noisy datasets from different parts of the world, we obtain the results shown in Figure \ref{fig:other_data}. The model effectively removes the noise. Some signal is also visible in the estimated noise.
\plot{other_data}{}{Noise removal from marine data acquired in Venezuela, Norway, and New Zealand. The output of the network, the estimated noise, is shown on the right, while the estimated signal, shown in the center, is obtained by subtracting the estimated noise from the input. The majority of the noise is removed, but some signal is also lost.}

\section{Discussion}
\paragraph{Increasing loss with number of adjacent gathers} In theory, the loss should not increase as the number of adjacent gathers provided as input to the model increases, as the model may disregard the additional gathers if they do not provide useful information. It is possible that the loss increases in our experiment when more than three adjacent gathers are provided as beyond this point the useful information provided by additional gathers is not sufficient to compensate for the larger number of training epochs that will be required due to the increasing number of weights that need to be trained.

\paragraph{Alternative adjacent gathers} We use adjacent common offset gathers as the additional input channels provided to the network. Alternatives include constructing the additional input channels so that slices of the input in the channel dimension correspond to NMO corrected CMP gathers. In this setup, the blending noise is incoherent in two dimensions of the input, while the signal should be coherent and relatively flat. This may aid the network to remove the blending noise, but results in higher computational cost, and also requires a velocity model to perform the NMO correction.

\paragraph{Signal loss} The apparent signal leakage into the estimated noise, visible when the model is applied to real datasets, is undesirable. Inspection of the results suggests that small variations in amplitude are being identified by the model as noise. This is likely to be due to the model being trained using synthetic data, where such variations are not present. Incorporation of some real data into the training dataset may help to reduce this effect.

\paragraph{Application to land data} Denoising methods that rely on identifying signal by its coherency are less reliable for seismic data acquired on land. This is because static shifts, caused by near-surface variations, and irregular acquisition spacing due to obstacles, may cause the signal to also be incoherent across traces. Applying static corrections and interpolation to regularize the acquisition geometry may thus be necessary before attempting to attenuate the noise.

\paragraph{Black box method} Deep learning-based methods may be regarded as a black box, where it is not possible to explain why particular results were produced or to predict how the methods will respond to new inputs. The compensation for this sacrifice is that the methods are capable of more sophisticated operations than we are able to express in mathematically derived approaches. A median filter is easily understood, but will struggle when the underlying signal is not well approximated by a line and when there are crossing events. In contrast, a neural network can, in theory, learn to recognize these situations and handle them appropriately.

\section{Conclusion}
After being trained once, the method denoised and deblended datasets from different parts of the world that it had not seen previously, with moderate accuracy. The method removed noise effectively, but also removed some signal. The hypothesis is therefore validated for situations where the speed of the method is more important than preserving all of the signal, such as during fast-track processing and quality control.


\section{}

\section{Introduction}\label{intro}
A \emph{convexity} of a graph $G$ is a pair $(V(G),\mathcal{C})$ where $\mathcal{C}$ is a family of subsets of $V(G)$ satisfying all the following conditions: $ \emptyset \in \mathcal{C}$, $V(G)\in \mathcal{C}$, and $\mathcal{C}$ is closed under intersections (i.e., $V_1\cap V_2\in \mathcal{C}$ for each $V_1,V_2\in \mathcal{C}$). Each set of the family $\mathcal{C}$ is called \emph{$\mathcal{C}$-convex}. Distinct convexities of a graph have been widely studied in the last years. Several articles can be found in the literature dealing with algorithmic and complexity issues of parameters related to different kind of convexities. Interesting enough is to compare the behavior of these parameters under different convexities from a computational complexity perspective. For an introduction to the different parameters studied in the literature related to a convexity of a graph, see e.g.~\cite{Douchet1988}.

A family $\{V_1,\ldots,V_p\}$ of $p$ $\mathcal{C}$-convex sets, each of which different from $V(G)$, is a \emph{$\mathcal{C}$-convex $p$-cover} if $V_1\cup\cdots\cup V_p=V(G)$ and a \emph{$\mathcal{C}$-convex $p$-partition} if, in addition, $V_i\cap V_j=\emptyset$ for each $i,j\in\{1,\ldots,p\}$ with $i\neq j$. In this work, we consider two associated decision problems: in one case, the input is just a graph $G$ and, in the other case, the input is a graph $G$ and an integer $p\ge 2$. In both cases, the decision problem is: `Does the graph $G$ have a $\mathcal{C}$-convex $p$-cover (resp.\ $\mathcal{C}$-convex $p$-partition)?'.

All graphs in this work are finite, undirected, without no loops and no multiple edges. Let $G$ be a graph. We denote by $V(G)$ and $E(G)$ the vertex set and the edge set of $G$, respectively. The neighborhood of a vertex $v$ of $G$ is denoted by $N_G(v)$, and $N_G[v]$ stands for the set $N_G(v)\cup\{v\}$. If $X$ is a set, $\vert X\vert$ denotes its cardinality. The \emph{degree} of a vertex $v$ of $G$ is $\vert N_G(v)\vert$. If $S$ is a subset of $V(G)$, then the set of those vertices of $G$ with at least one neighbor in $S$ is denoted by $N_G(S)$, and $N_G[S]$ stands for $N_G(S)\cup S$. The \emph{length} of a path is its number of edges. The \emph{distance} between two vertices $u$ and $v$ of $G$, denoted by $d_G(u,v)$, is the minimum length of a path having $u$ and $v$ as end-vertices. The \emph{diameter} of a graph is the maximum distance between two of its vertices. A path is \emph{induced} if there is no edge joining two nonconsecutive vertices of the path. We denote by $P_3$ the induced path on three vertices. We denote the \emph{complement graph} of $G$ by $\overline G$. Graph $G$ is \emph{co-bipartite} if $\overline G$ is bipartite. For any other graph-theoretic notions not given here, see~\cite{West01}.

Let $\mathcal{P}$ be a set of paths in $G$ and let $S\subseteq V(G)$. If $u$ and $v$ are two vertices of $G$, then the \emph{$\mathcal{P}$-interval} $J_{\mathcal{P}}[u,v]$ is the set of all vertices lying in some path $P\in \mathcal{P}$ having $u$ and $v$ as its end-vertices. Let $J_{\mathcal P}[S]=\bigcup_{u,v\in S}{J_{\mathcal P}[u,v]}$. Let $\mathcal{C}$ be the family of all sets $S$ of vertices of $G$ such that for each path $P\in \mathcal{P}$ whose end-vertices belong to $S$, every vertex of $P$ also belongs to $S$; i.e., $ \mathcal{C}$ consists in those subsets $S$ of $V(G)$ such that $J_{\mathcal{P}}[S]=S$. It is easy to show that $(V(G),\mathcal{C})$ is a convexity of $G$ and $\mathcal{C}$ is called the \emph{path convexity generated by $\mathcal P$}. Some of the most studied path convexities are the \emph{geodesic convexity}, the \emph{monophonic convexity}, the \emph{$P_3$-convexity}, and the \emph{$P_3^*$-convexity}, which are the convexities whose convex sets are generated by the set of all minimum paths, the set of all induced paths, the set of all paths of length three, and the set of all induced paths of length three of the graph, respectively.

A set $S$ of vertices of a graph $G$ is \emph{digitally convex} if, for each vertex $v$ of $G$, $N_G[v]\subseteq N_G[S]$ implies $v\in S$.  The \emph{digital convexity} of a graph $G$ is the pair $(V(G),\mathcal{C})$ where $\mathcal{C}$ is the set of all digitally convex sets of $G$. This convexity was introduced in~\cite{PR-digitalconvexity-1966} as a tool to filter digital images.

The problem of deciding whether $G$ has a $\mathcal{C}$-convex $p$-partition was introduced by Artigas et al.~\cite{paper2}. They proved that the problem is NP-complete for each fixed integer $p\geq 2$, under the geodesic convexity. Centeno et al.~\cite{paper1} proved that the problem is also NP-complete under the $P_3$-convexity if a graph $G$ and an integer $p\geq 2$ are given as input. The problem of deciding whether a graph has a $\mathcal{C}$-convex $p$-cover was introduced in~\cite{paper3} also by Artigas et al. This problem is NP-complete under the geodesic convexity for each fixed integer $p\geq 2$~\cite{paper3,paper4}.

This article is organized as follows. In Section~\ref{sec:digital convexity}, we deal with the problems of covering with convex sets and of partitioning into convex sets a graph under the digital convexity. In Section~\ref{sec:P_3-convexity}, we present results in connection with the problem of partitioning a graph into convex sets under the $P_3$-convexity, as well as the $P_3^*$-convexity, and we also consider the problem of covering a graph with $P_3$-convex sets. In Section~\ref{sec:monophonic}, we address these problems under the monophonic convexity.

\section{Digital convexity}\label{sec:digital convexity}

We will call \emph{d-convex} to any convex set under the digital convexity. Our first result characterizes d-convex sets as the complements of the closed neighborhoods of sets of vertices.

\begin{prop}\label{prop:1}
Let $G$ be a graph, $S \subseteq V(G)$, and $W = V(G)\setminus N_G[S]$. For each vertex $v$ of $G$, $N_G[v]\subseteq N_G[S]$ if and only if $v \notin N_G[W]$.
\end{prop}
\begin{proof} In fact, $N_G[v] \subseteq N_G[S]$ is equivalent to $N_G[v] \cap W = \emptyset$ which, in turn, is equivalent to $v \notin N_G[W]$.
\end{proof}

\begin{lem}\label{lem:complementofclosedneighborhood}
A set of vertices $S$ of a graph $G$ is d-convex if and only if $S=V(G)\setminus N_G[W]$ for some set $W \subseteq V(G)$.
\end{lem}

\begin{proof} Suppose that $S$ is a d-convex set of $G$ and let $W=V(G)\setminus N_G[S]$. We claim that $S=V(G)\setminus N_G[W]$. On the one hand, if $v\in S$, then $N_G[v]\subseteq N_G[S]$ and, by virtue of Proposition~\ref{prop:1}, $v\notin N_G[W]$. On the other hand, if $v\notin N_G[W]$, then, by Proposition~\ref{prop:1}, $N_G[v]\subseteq N_G[S]$ and, since $S$ is d-convex, $v\in S$. We conclude that $S=V(G)\setminus N_G[W]$, as desired.

Conversely, let $W\subseteq V(G)$ and $S=V(G)\setminus N_G[W]$. Let $v\in V(G)$ such that $N_G[v]\subseteq N_G[S]$.
Notice that $N_G[S]\cap W=\emptyset$ (in fact, if there were some vertex $w\in W\cap N_G[S]$, then there would be some vertex $s\in N_G[W]\cap S$, a contradiction). Thus, $N_G[v]\cap W=\emptyset$ or, equivalently, $\{v\}\cap N_G[W]=\emptyset$. Hence, $v\in V(G)\setminus N_G[W]=S$. This proves that $S$ is a d-convex set of $G$.\end{proof}

A \emph{total dominating set} of a graph $G$ is a set $S$ of vertices of $G$ such each vertex of $G$ has at least one neighbor in $S$. Our next result shows that the existence of a covering with few digitally convex sets is equivalent to the existence of sufficiently small total dominating sets in the complement.

\begin{theorem}\label{thm:dominating set}
A graph $G$ has a d-convex $p$-cover if and only if $\overline G$ has a total dominating set of cardinality at most $p$.
\end{theorem}

\begin{proof}
Let $X=\{w_1,w_2,\ldots,w_k\}\subseteq V(G)$ be a total dominating set of $\overline G$ with $k\leq p$. By virtue of Lemma~\ref{lem:complementofclosedneighborhood}, $V_i= V(G)\setminus N_G[w_i]$ is a d-convex set for each $i\in\{1,\ldots,k\}$. We claim that $\{V_1,V_2,\ldots,V_k\}$ is a cover of $V(G)$. Since $X$ is a total dominating set of $\overline G$, for each $v$ in $ V(\overline{G})\ ({}=V(G))$, there exists some $i\in\{1,\ldots,k\}$ such that $v\in N_{\overline G}(w_i)=V(G)\setminus N_G[w_i]=V_i$. Therefore, $V(G)=\bigcup_{i=1}^k V_i$.

Conversely, let $\{V_1,\ldots,V_p\}$ be a d-convex $p$-cover of $G$. Hence, by Lemma \ref{lem:complementofclosedneighborhood}, $V_i=V(G)\setminus N_G[W_i]$ for some $W_i\subseteq V(G)$. Choose a vertex $w_i\in W_i$ for each $i\in\{1,\ldots,p\}$. Notice that it may happen that $w_i=w_j$ even if $i\neq j$. Let $W=\{w_1,\ldots,w_p\}$. By construction, $\vert W\vert\leq p$. As $\{V_1,\ldots,V_p\}$ is a cover of $G$, for each $v\in V(\overline{G})$ there is some $i\in\{1,\ldots,p\}$ such that $v\in V_i=V(G)\setminus N_G[W_i]\subseteq V(G)\setminus N_G[w_i]=N_{\overline G}(w_i)$. This proves that $W$ is a total dominating set of $\overline G$ with at most $p$ vertices.\end{proof}

Since the problem of deciding, given a graph $G$ and a positive integer $p$, whether $G$ has a total dominating set of size at most $p$ is NP-complete~\cite{td}, Theorem~\ref{thm:dominating set} implies the following.

\begin{corollary}\label{cor:p-cover_d-convex}
It is NP-complete to decide, given a graph $G$ and an integer $p\geq 2$, whether $G$ has a d-convex $p$-cover.
\end{corollary}

Notice that Corollary~\ref{cor:p-cover_d-convex} proves the NP-completeness of deciding whether a graph $G$ has d-convex $p$-cover when $p$ is part of the input. However, the complexity for the case in which $p$ is a fixed integer is unknown.

We were not able to determine the computational complexity of the problem of deciding, given a graph $G$ and an integer $p$, whether the graph $G$ has a d-convex $p$-partition. Below, we present a result that shows that if the graph $G$ is assumed bipartite and we fix $p=2$, then the problem becomes polynomial-time solvable.
We first prove the following lemma.

\begin{lem}\label{lem:diameter}
Let $G$ be a connected graph. If $G$ has a d-convex $2$-partition, then $G$ has diameter at least 3.
\end{lem}
\begin{proof}
Let $\{V_1,V_2\}$ be a d-convex $2$-partition of a connected graph $G$. Since $G$ is connected, there exists $u_i\in V_i$ for each $i\in\{1,2\}$ such that $u_1$ is adjacent to $u_2$. Since $u_i\in N_G[V_{i+1}]$ (where sums should be considered modulo 2) and $V_{i+1}$ is a $d$-convex set, there exists some vertex $v_i$ adjacent to $u_i$ such that $v_i\notin N_G[V_{i+1}]$. By construction, $v_1,u_1,u_2,v_2$ is an induced path of length three of $G$. Consequently, the diameter of $G$ is at least $3$.
\end{proof}

We are now ready to prove the following result

\begin{theorem}\label{thm:2-partition_d-convex}
A bipartite graph $G$ has a d-convex $2$-partition if and only if $G$ has diameter at least 3. Moreover, if such a partition exists, it can be found in polynomial time.
\end{theorem}

\begin{proof} If $G$ is disconnected and $\mathcal{C}$ is any connected component of $G$, then $\{\mathcal{C},V(G)-\mathcal{C}\}$ is clearly a d-convex $2$-partition of $G$ that, in addition, can be built in polynomial time. Hence we assume, without loss of generality, that $G$ is connected. We have already proved in Lemma~\ref{lem:diameter} that if $G$ is a connected graph having a d-convex $2$-partition, then $G$ has diameter at least $3$. Conversely, assume now that $G$ is a connected bipartite graph with bipartition $\{X,Y\}$ and diameter at least 3. Two vertices $u,v\in V(G)$ such that $d_G(u,v)=3$ and the two sets $V_1=N_G[u]\cup\{x\in X\colon\,N_G(x)\subseteq N_G[u]\}$ and $V_2=V(G)\setminus V_1$ can be computed polynomial time. It is not hard to see that $\{V_1,V_2\}$ is a d-convex $2$-partition of $G$.
\end{proof}

\section{Convexities generated by paths of length three}\label{sec:P_3-convexity}
We1 call \emph{$P_3$-convex} (resp.\ \emph{$P_3^*$-convex}) to any convex set under the $P_3$-convexity (resp.\ $P_3^*$-convexity). Let $G$ be a bipartite graph with a bipartition $\{X,Y\}$ and let $p$ be an integer such that $p\geq 2$. We construct a bipartite graph $G'$ as follows: we take a copy of $G$ and a complete bipartite graph $K_{r,r}$ where $r=\max\{p+2,\vert X\vert,\vert Y\vert\}$, we add an edge connecting each vertex in $X$ with a vertex of one of the partite sets of $K_{r,r}$, and we add an edge connecting each vertex in $Y$ with a vertex of the other partite set of $K_{r,r}$, so that there are no two vertices in the copy of $G$ in $G'$ adjacent to the same vertex in the complete bipartite graph~$K_{r,r}$.

A \emph{cut} of a graph $G$ is a partition of $V(G)$ into two sets $X$ and $Y$, denoted by $(X,Y)$. The set of all edges having one endpoint in $X$ and the other one in $Y$ is called the \emph{edge cut} of the cut $(X,Y)$. A \emph{matching cut set} is an edge cut that is a (possible empty) matching (i.e., no two edges of the edge cut share an endpoint).

It can be easily proved that the problem of deciding whether a graph has a $P_3$-convex $2$-partition and the problem of deciding whether a graph has matching cut set are equivalent.

\begin{lem} \label{lem:2partitionP3}
A graph $G$ has a $P_3$-convex $2$-partition if and only if $G$ has a matching cut set.
\end{lem}

\begin{lem} \label{lem:p-convex_then_p+1convex}
Let $p$ be an integer such that $p\geq 2$. A graph $G$ has a $P_3$-convex $p$-partition if and only if $G'$ has a $P_3$-convex $(p+1)$-partition.
\end{lem}
\begin{proof}
If $G$ has a $P_3$-convex $p$-partition $\{V_1,\ldots,V_p\}$, then $G'$ has a $P_3$-convex $(p+1)$-partition $\{V_1,\ldots,V_p,V_{p+1}\}$, where $V_{p+1}$ is the set of vertices of the copy of $K_{r,r}$ in $G'$.

Conversely, suppose that $G'$ has a $P_3$-convex $(p+1)$-partition $\{V_1,\ldots,V_p,\linebreak V_{p+1}\}$. Let $V$ be the vertex set of the copy of $G$ in $G'$ and let $V'$ be the vertex set of the copy of $K_{r,r}$ in $G'$. We claim that $V'\subseteq V_i$ for some $i\in\{1,\ldots,p,p+1\}$. Indeed, since $r\ge p+2$, there exist at least two nonadjacent vertices $x,y\in V'\cap V_i$ for some $i\in\{1,\ldots,p,p+1\}$ and thus $V'\subseteq V_i$ (because $V_i$ is $P_3$-convex). We assume, without losing generality, that $i=p+1$; i.e., $V'\subseteq V_{p+1}$. Let $W=V_{p+1}\cap V$. Arguing towards a contradiction, suppose that $W\neq\emptyset$. Notice that if no vertex in $W$ has a neighbor in $V_i$ for some $i\in\{1,\ldots,p\}$, then $\{V_1,\ldots,V_{p-1},V_p\cup W\}$ is a $P_3$-convex $p$-partition of the copy $G$ in $G$' and, in particular, a $P_3$-convex $p$-partition of $G$, as desired. Hence, we assume, without loss of generality, that there is some vertex $a\in W$ adjacent to some vertex $b\in V_i$ for some $i\in\{1,\ldots,p\}$. By the construction of $G'$, there exists a vertex $c\in V'\subseteq V_{p+1}$ which is adjacent to $b$ and nonadjacent to $a$. Consequently, $a,b,c$ is a path on three vertices of $G'$ such that $a,c\in V_{p+1}$ but $b\notin V_{p+1}$, contradicting the fact that $V_{p+1}$ is a $P_3$-convex set of $G'$. This contradiction arose from assuming that $W\neq\emptyset$. Hence, $W=\emptyset$ and thus $V_{p+1}=V'$. Therefore, $\{V_1,\ldots,V_p\}$ is a $P_3$-convex $p$-partition of the copy of $G$ in $G'$ and, in particular, a $P_3$-convex $p$-partition of $G$.
\end{proof}

Since the matching cut set problem is NP-complete even when the input is a bipartite graph~\cite{LR-2003}, by virtue of Lemma~\ref{lem:p-convex_then_p+1convex}, we obtain the following theorem.
\begin{theorem}\label{cor:p-partition_p3-convex_in_bipartite} For each fixed integer $p\geq 2$, it is NP-complete to decide, given a graph $G$, whether $G$ has a $P_3$-convex $p$-partition, even if $G$ is a bipartite graph.
\end{theorem}
Notice that, in a bipartite graph, the family of $P_3$-convex sets in $G'$ coincides with the family of $P_3^*$-convex sets in $G'$. Hence, Corollary~\ref{cor:p-partition_p3-convex_in_bipartite} still holds if `$P_3$-convex' is replaced by `$P_3^*$-convex'.

A \emph{stable set} is a set of pairwise nonadjacent vertices. A \emph{clique} is a set of pairwise adjacent vertices. A \emph{split graph} is a graph whose vertex set can be partitioned into an independents set $S$ and a clique $K$; the pair $(K,S)$ is called a \emph{split partition}.
\begin{lem}\label{lem:split_graph-p3-convexity}
Let $G$ be a split graph with split partition $(K,S)$ and $p$ be an integer such that $p\ge 2$. If every vertex $s\in S$ has degree at least two, then $G$ has a $P_3$-convex $p$-partition if and only if $G$ has a $P_3$-convex $p$-cover.
\end{lem}

\begin{proof}
The `only if' part is clear. Assume that $G$ has a $P_3$-convex $p$-cover $\{V_1,V_2,\ldots,V_p\}$. Notice that, for each $i\in\{1,\ldots,p\}$, $\vert V_i\cap \mathcal{C}\vert \leq 1$ because otherwise every vertex $x\in \mathcal{C}$ would belong to $V_i$ and, since every vertex of $S$ is adjacent to at least two vertices of $\mathcal{C}$, $y\in V_i$ for every vertex $y\in S$, contradicting $V_i\neq V(G)$. Besides, if $x\in \mathcal{C}$ and $y\in S$ are adjacent, then there is no $i\in\{1,\ldots,p\}$ such that $x,y\in V_i$; otherwise, any other neighbor $z$ of $y$ in $\mathcal{C}$ would belong to $V_i$ and so $x,z\in V_i\cap \mathcal{C}$. We have proved that $V_i$ is an independent set for each $i\in\{1,\ldots,p\}$. Let $V'_1=V_1$ and let $V'_{i+1}=V_{i+1}\setminus(\bigcup_{j=1}^i V_j)$ for each $j\in\{2,\ldots,p\}$. By construction, $\{V'_1,\ldots,V'_p\}$ is a partition. We claim that, for each $i\in\{1.\ldots.p\}$, $V'_i$ is a $P_3$-convex set. Arguing towards a contradiction, suppose that there exists some $i\in\{1,\ldots,p\}$ and some vertex $x\in V(G)\setminus V'_i$ such that $\{u,v\}\subseteq N_G(x)\cap V'_i$. In particular, $u,v\in V_i$ and, since $V_i$ is $P_3$-convex, $x\in V_i$, contradicting the fact that $V_i$ is an independent set. This contradiction proves the claim. Hence, $\{V_1',V_2',\ldots,V_p'\}$ is a $P_3$-convex $p$-partition of $G$.\end{proof}

In~\cite{paper1}, it is proved that it is NP-complete to decide whether a split graph $G$ with split partition $(K,S)$ has a $P_3$-convex $p$-partition when $p$ is part of the input. Looking carefully at the proof given in~\cite{paper1}, one can readily verify that it is still valid if every vertex in $S$ has degree at least two.

\begin{theorem}[{\cite[Theorem 2.1]{paper1}}]\label{thm:p3-convex-partition}
The problem of deciding, given a split graph $G$ with a split partition $(K,S)$, where $G$ has a $P_3$-convex $p$-partition is NP-complete, even if each vertex in $S$ has at least two neighbors.\end{theorem}

Therefore, in virtue of Lemma~\ref{lem:split_graph-p3-convexity}, the result below follows.

\begin{corollary}\label{cor:P3-convex p-partition}
It is NP-complete to decide, given a graph $G$ and an integer $p\ge 2$, whether $G$ has a $P_3$-convex $p$-cover, even if $G$ is a split graph.
\end{corollary}

\section{Monophonic convexity}\label{sec:monophonic}

We will call m-convex to any convex set under the monophonic convexity. We will prove that it is NP-complete to decide, given a graph $G$ and an integer $p\ge 3$, whether $G$ has an m-convex $p$-partition, by adapting the proof of~\cite[Theorem 1]{paper3} for the analogous result for the geodesic convexity.
If $p$ is a positive integer, \textsc{Clique $p$-Partition} is the problem of deciding, given a graph $G$, whether the vertex set of $G$ can be partitioned into $p$ cliques of $G$. It is well known that this problem is NP-complete for all $p\geq 3$.

\begin{theorem}\label{thm:p-cover_m-convex}
It is NP-complete to decide, given a graph $G$ and an integer $p\ge 3$, whether $G$ has an m-convex $p$-cover.
\end{theorem}

\begin{proof}
Deciding if a set $S\subseteq V(G)$ is m-convex can be done in polynomial time~\cite{paper5} and thus the problem of deciding if a graph $G$ has an m-convex $p$-cover belongs to $NP$.
Let $G$ be an instance of the \textsc{Clique $p$-Partition} problem. We assume, without loss of generality, that $\vert V(G)\vert\ge 2$ and $G$ is not a complete graph. We construct a graph $G'$ whose vertex set is $V(G)\cup\{u,v\}$ and $E(G')=E(G)\cup \{ux,vx\colon\,x\in V(G)\}$. The proof follows in the same way as the proof of the NP-completeness of Theorem~1 in~\cite[Theorem~1]{paper3}. It is not hard to prove that any proper m-convex set of $G'$ is a clique. From this assertion, it follows that $G'$ has an m-convex $p$-partition if and only if $G$ has an $\ell$-clique partition for some integer $\ell$ such that $p-2\le\ell\le p$.
\end{proof}

Next, we will prove that deciding whether a graph $G$ has an m-convex $p$-cover becomes polynomial-time solvable for $p=2$. A \emph{clique separator} of a connected graph $G$ is a clique $\mathcal{C}$ such that $G-\mathcal{C}$ is disconnected.

\begin{lem}[{\cite{paper5}}]\label{lem:m-convex 2-cover}
Let $G$ be a connected graph, $\mathcal{C}$ a clique separator of $G$, and $S$ the union of the vertex sets of some of the connected components of $G-\mathcal{C}$. Then $S\cup \mathcal{C}$ is an m-convex set of $G$.
\end{lem}

\begin{corollary}\label{cor:m-convex 2-conver clique separator}
If $G$ is a connected graph having a clique separator, then $G$ has an m-convex 2-cover.
\end{corollary}

\begin{proof}
If $\mathcal{C}$ is a clique separator of $G$ and $G_1$ is any connected component of $G-\mathcal{C}$, then, by virtue of Lemma~\ref{lem:m-convex 2-cover}, $\{V(G_1)\cup \mathcal{C},(V(G)\setminus V(G_1))\cup \mathcal{C}\}$ is an m-convex 2-cover of $G$.
\end{proof}

Let $G$ be a graph. The \emph{m-convex hull} of a set $S\subseteq V(G)$ is the inclusion-wise minimal m-convex set $M$ of $G$ containing $S$ or, equivalently, $M=J_{\mathcal P}[S]$ where $\mathcal P$ is the set of all induced paths of $G$. A set $X$ of vertices of $G$ is an \emph{m-hull set} of $G$ if the m-convex hull of $X$ is $V(G)$.

\begin{lem}[{\cite{paper5}}]\label{lem:convex-mitre}
If $G$ is a connected graph having no clique separator that is not a complete graph, then every pair of nonadjacent vertices is an m-hull set of $G$.
\end{lem}

The following result is an immediate consequence of Lemma~\ref{lem:convex-mitre}.

\begin{corollary}\label{cor: proper m-convex}
If $G$ is a connected graph having no clique separator, then every proper m-convex of $G$ is a clique. Moreover, $G$ has an m-convex $2$-cover if and only if $G$ is a co-bipartite graph.
\end{corollary}

\begin{theorem}\label{thm:m-convex-cover}
It is polynomial-time solvable to decide, given a graph $G$, whether $G$ has an m-convex $2$-cover.
\end{theorem}

\begin{proof}
In order to decide whether a connected graph $G$ has an m-convex $2$-cover, we first look for a clique separator in $O(nm)$ time~\cite{clique}. If a clique separator is found, then, by Corollary~\ref{cor:m-convex 2-conver clique separator}, $G$ has an m-convex 2-cover. If $G$ has no clique separator, we test if $G$ is co-bipartite, which can be performed in linear time. Consequently, it can be decided in $O(nm)$ time whether or not a given graph $G$ has an m-convex 2-cover.\end{proof}

\section*\refname
\bibliographystyle{elsarticle-num}