Paired Many-to-Many 2-Disjoint Path Covers in Meshes

In the paired many-to-many <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-disjoint path cover (<inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-DPC) problem, given a set of <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> pairs of vertices <inline-formula><tex-math notation="LaTeX">$(s_{i},t_{i})$</tex-math></inline-formula>, <inline-formula><tex-math notation="LaTeX">$1\leqslant i\leqslant k$</tex-math></inline-formula>, of a graph <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> we want to find <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> simple vertex-disjoint paths whose end-vertices are these <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> pairs, such that each vertex of <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> is covered by a path. This problem is a well-known problem in parallel processing and is a generalization of the well-known Hamiltonian <inline-formula><tex-math notation="LaTeX">$(s,t)$</tex-math></inline-formula>-path problem, which is equal to 1-DPC. In this paper, we consider the paired many-to-many 2-disjoint path cover problem (2-DPC) in meshes (rectangular grids). We give the necessary conditions for existence of such covers, and present a linear-time algorithm to compute them. Although the paired many-to-many <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-disjoint path cover problem is well-known in parallel processing, our motivation to study this problem is its application in solving the Hamiltonian path problem in solid grid graphs. We consider the case where the pairs of vertices are on the outer face of the graph.