
%Tady pokracuj
\documentstyle{article}
\def\textfraction{0.01}
\def\topfraction{0.99}
\addtolength{\textwidth}{3cm}
\addtolength{\oddsidemargin}{-15mm}
\def\Ipe#1{\def\IPEfile{#1}\input{\IPEfile}}
%\def\Ipe#1{Tady bude obrazek #1}
\sloppy
\begin{document}

%%\def\picture #1 by #2 (#3){\vbox to #2{\hrule width #1 height 0pt depth 0pt
%%                           \vfill\special{picture #3} }}
%%
%%\def\scaledpicture #1 by #2 (#3 scaled #4){{\dimen0=#1 \dimen1=#2
%%            \divide\dimen0 by 1000 \multiply\dimen0 by #4
%%            \divide\dimen1 by 1000 \multiply\dimen1 by #4
%%            \picture \dimen0 by \dimen1 (#3 scaled #4)}}
%%
%%\def\figi{\hskip1.7in\picture 3.09in by 1.0in (p2path scaled 500)}

\def\vH{\overline{H}}
\def\qed{$\Box$}%\vrule height .9ex width .8ex depth -.1ex}

\newtheorem{lem}{Lemma}[section]
\newtheorem{thm}{Theorem}
\newtheorem{prop}[lem]{Proposition}
\newtheorem{cor}[lem]{Corollary}
\newtheorem{fact}[lem]{Fact}
\newtheorem{defi}[lem]{Definition}

\newenvironment{pf}{\par\noindent {\bf Proof.}}{\qed\par\medskip}

\newcommand\gc{graph covering}
\newcommand\NP{$\cal NP$}
\title{Complexity of colored graph covers II.\\
When 2-SAT helps. }
\date{\today}

\author{Jan Kratochv\'{\i}l\thanks{
Research partially supported by Czech Research grants GAUK 194/1996 and
GA\v{C}R
0194/1996.}\\
{\footnotesize Charles University}\\ {\footnotesize Prague, Czech Republic}
%\and Andrzej Proskurowski\\ {\footnotesize University of Oregon}\\
%{\footnotesize Eugene, Oregon}
\and Jan Arne Telle\thanks{Third author supported by a fellowship from the
Norwegian Research Council.}\\
{\footnotesize University of Bergen}\\{\footnotesize Bergen,
Norway}}
\maketitle

\begin{abstract}
A covering projection from a graph $G$ onto a graph $H$ is a
 ``local isomorphism'': a mapping from the vertex set of
$G$ onto the vertex set of $H$ such that, for every $v\in V(G)$,
 the neighborhood of
$v$ is mapped bijectively onto the neighborhood (in $H$) of the image
of $v$. We continue the investigation of the computational complexity of
the
$H$-cover problem -- deciding if a given graph $G$
covers $H$. We present a characterization of a
large class of parameter graphs $H$ for which this
problem is solvable in polynomial time.
\end{abstract}

%\tableofcontents

\section{Motivation and overview}

For a fixed graph $H$, the $H$-cover problem admits a graph $G$ as input
and
asks about the existence of a ``local isomorphism'': a labeling of the vertices
of
$G$ by vertices of $H$ so that the label set of the neighborhood of every
$v\in V(G)$ is equal to the neighborhood (in $H$) of the label of $v$
and
each neighbor of $v$ is labeled by a different neighbor of the label of $v$.
Such
a labeling is referred to as a {\em covering projection} from $G$ onto $H$.
 Abello {\it et al.}
\cite{AFS} raised the question of computational complexity of
$H$-cover problems, noting that there are both polynomial-time solvable
({\sl easy})
and
NP-complete ({\sl difficult}) versions of this problem depending on the
parameter  graph
$H$. We have studied the question of complexity of {\gc} problems in \cite{KPT},
where one of our main results was a complete catalogue of the complexity of
this problem for graphs on at most 6 vertices. In \cite{KPT2},
we  showed that in order
to achieve a complete characterization of the complexity of
graph covering problems for simple undirected graphs, it is necessary and
sufficient to give a complete characterization of the $H$-cover problem for
colored directed multigraphs $H$ of minimum total degree $\ge 3$. We
continue the study of the complexity of the $H$-cover problem for
cdm-graphs in this paper by describing a large class of graphs that allow
polynomial-time solution. In \cite{KPT}, we have showed that in the case of
simple undirected graphs the $H$-cover problem is polynomial if every block
of the degree partition of $H$ has at most two vertices. Our
Theorem~\ref{2sat} provides a generalization of this theorem to cdm-graphs.

We first define the necessary notions in the next subsections. The main
theorem is then presented in Section~\ref{main}.

\subsection{Directed multigraphs}

 A directed multigraph
with vertex set $V$ has edge set $E=D\cup F\cup L$, where $D$ is the set of
directed edges (including directed loops),
$F$ is the set of undirected edges and $L$ is the set of
undirected loops.
A function $\mu:E\rightarrow (V\times V)\cup{V\choose 2}\cup V$
describes the incidences, i.e., for an undirected edge $e\in F$,
$\mu(e)\in {V\choose 2}$ is the pair of vertices connected by $e$, for a
loop $e\in L$, $\mu(e)\in V$ is the vertex hosting the loop $e$ and for a
directed edge $e\in D$, $\mu(e)\in V\times V$ is the ordered pair of
vertices connected by $e$.
Vertices and edges are colored by a coloring $C:V\cup E\rightarrow C(V\cup
E)$
(this coloring need not be proper in the sense that adjacent vertices
and/or edges may
receive the same color). Since vertices, directed and undirected edges may
be distinguished regardless the color, we may assume that $C(V)$, $C(D)$
and $C(F\cup L)$ are disjoint.
A cdm-graph is uncolored if $C(V)$,  $C(D)$ and $C(F\cup L)$
are one-element set each.



For an edge-color $c$, the {\em $c$-colored degree} of a vertex
$x\in V(G)$ is defined as
$$deg^c_G(x)=|\{e:x\in \mu(e), e\in F(G),C(e)=c\}|+2|\{e:x=\mu(e), e\in L(G),
C(e)=c\}|$$
for $c\in C(F\cup L)$, and
$$deg^c_G(x)=(deg^{c-}_G(x),deg^{c+}_G(x))$$
where
$$deg^{c-}_G(x)=|\{e:\mu(e)=(x,u)\mbox{ for some $u$}, e\in D(G), C(e)=c\}|$$
and
$$deg^{c+}_G(x)=|\{e:\mu(e)=(u,x)\mbox{ for some $u$}, e\in D(G), C(e)=c\}|.$$

The {\em total degree} of a vertex $u$ is
$$deg_Gu=\sum_{c\in C(F\cup L)}deg^c(u)+\sum_{c\in
C(D)}(deg^{c+}(u)+deg^{c-}(u)).$$


A {\em covering projection of a cdm-graph $G$ onto a cdm-graph $H$} is a
mapping $f:V(G)\cup E(G)\rightarrow V(H)\cup E(H)$ such that

(1) $f(u)\in V(H)$ and $C(f(u))=C(u)$ for every $u\in V(G)$,

(2) $f(e)\in D(H)$, $C(f(e))=C(e)$ and $\mu(f(e))=(f(u),f(v))$ for every
$e\in D(G)$ such that $\mu(e)=(u,v)$,

(3) $f(e)\in F(H)\cup L(H)$, $C(f(e))=C(e)$ and $\mu(f(e))=\{f(u),f(v)\}$
for every
$e\in F(G)\cup L(G)$ such that $\mu(e)=\{u,v\}$,

(4) for every $u\in V(G)$ and every $e\in D(H)$ such that $\mu(e)=(f(u),w)$
($\mu(e)=(w,f(u))$) for some $w$, there is exactly one arc $e'\in D(G)$
such that $\mu(e')=(u,w')$
($\mu(e')=(w',u)$, respectively) for some $w'$ and $f(e')=e$,

(5) for every $u\in V(G)$ and every $e\in F(H)$ such that
$f(u)\in\mu(e)$, there is exactly one edge $e'\in F(G)$
such that $u\in \mu(e')$ and $f(e')=e$,

(6) for every $u\in V(G)$ and every $e\in L(H)$ such that
$\mu(e)=f(u)$, there is either exactly one loop $e'\in L(G)$
such that $\mu(e')=u$ and $f(e')=e$,
or there are exactly two edges $e',e''\in F(G)$
such that $u\in\mu(e'),u\in \mu(e'')$
and $f(e')=f(e'')=e$.\\
We have proved in \cite{KPT2} that a cdm-graph $G$ covers a cdm-graph $H$
if and only if there exists a
{\em vertex-covering projection} of $G$ onto $H$, i.e.,
a mapping $g:V(G)\to V(H)$ such that

(1') $C(g(u))=C(u)$ for every $u\in V(G)$,

(4') for every $u\in V(G)$, $w\in V(H)$ and every edge color $c\in C(D)$,
$$|\{e\in D(G):\mu(e)=(u,x), g(x)=w, C(e)=c\}|=
|\{e'\in D(H):\mu(e')=(g(u),w), C(e')=c\}|$$
and
$$|\{e\in D(G):\mu(e)=(x,u), g(x)=w, C(e)=c\}|=
|\{e'\in D(H):\mu(e')=(w,g(u)), C(e')=c\}|,$$


(5') for every $u\in V(G)$, $w\in V(H)$ such that $w\neq g(u)$,
 and every $c\in C(F\cup L)$,
$$|\{e\in F(G):\mu(e)=\{x,u\}, g(x)=w, C(e)=c\}|=
|\{e'\in F(H):\mu(e')=\{w,g(u)\}, C(e')=c\},|$$



(6') for every $u\in V(G)$ and every $c\in C(F\cup L)$,
$$|\{e\in F(G):\mu(e)=\{x,u\}, g(x)=g(u), C(e)=c\}|+
2|\{e\in L(G):\mu(e)=u, C(e)=c\}|=$$
$$2|\{e'\in L(H):\mu(e')=g(u), C(e')=c\}|.$$

We have also presented reductions in \cite{KPT2} that show that it suffices
to consider connected cdm-graphs of minimum total degree $\ge3$.

\subsection{Degree partitions and refinements}


The {\em degree partition} of a
cdm-graph $G$ is the coarsest partition of $V(G)$ into monochromatic
equivalence classes
$B_1,\ldots,B_k$ such that there exist numbers $r^c_{ij}, d^{c+}_{ij},
d^{c-}_{ij}$
($i,j=1,2,\ldots,k$, $c\in C(D)\cup C(F)\cup C(L)$) such that

(i) for every $i,j$ and every $u\in B_i$,
$$|\{e\in D(G): \mu(e)\in \{u\}\times B_j, C(e)=c\}|=d^{c+}_{ij},$$

(ii) for every $i,j$ and every $u\in B_i$,
$$|\{e\in D(G): \mu(e)\in  B_j\times\{u\}, C(e)=c\}|=d^{c-}_{ij},$$

(iii) for every $i\neq j$ and every $u\in B_i$,
$$|\{e\in F(G): u\in\mu(e), \mu(e)\setminus\{u\}\in B_j,
C(e)=c\}|=r^c_{ij},$$

(iv) for every $i$ and every $u\in B_i$,
$$|\{e\in F(G): u\in\mu(e), \mu(e)\setminus\{u\}\in B_i, C(e)=c\}|
+2|\{e\in L(G): \mu(e)=u, C(e)=c\}|=r^c_{ii}.$$

The collection $r^c_{ij}, d^{c+}_{ij}, d^{c-}_{ij}$
($i,j=1,2,\ldots,k$, $c\in C(D)\cup C(F)\cup C(L)$) is then called
the {\em degree refinement} of $G$. The equivalence classes of the degree
partition are refered to as {\em blocks} of the partition.

As in the case of simple undirected graphs,
the degree
partition of a cdm-graph is unique and
can be determined in polynomial time. It is also clear that
if a cdm-graph $G$ covers a cdm-graph $H$ then $G$ and $H$ have the same
degree refinements. Moreover, if $B_1,\ldots,B_k$ are the blocks of
 the degree partition
of $G$ and $B'_1,\ldots,B'_k$ are the blocks of
the degree partition of $H$ (indexed so that
$r^c_{ij}=r'^c_{ij}$, $d^{c+}_{ij}=d'^{c+}_{ij}$ and
$d^{c-}_{ij}=d'^{c-}_{ij}$
for all $i,j=1,2,\ldots,k$ and $c\in C(D)\cup C(F)\cup C(L)$) then
$f(B_i)=B'_i$ for every $i$ and every covering projection  $f:G\to H$.

\section{The polynomial theorem}\label{main}

For a cdm-graph $H$ and a color $c$, we denote by $H^c$ the subgraph
induced by the edges of color $c$. We call $H^c$ a {\em color
specification} of $H$.
%In view of \cite{KPT2}, we assume that every vertex
%of $H$ has total degree at least 3.
Since vertices of different blocks can
be distinguished in the covering graph as well as in $H$,
we may assume without loss of generality that
colors used on edges within distinct blocks and between distinct pairs of
blocks are distinct.
For colors used on directed edges, we
introduce one more simplification.
We may assume without loss of generality that
edges directed into a block have different colors than edges directed out
from that block. The orientation of such edges is then meaningless, and so
we assume that all edges between vertices of {\em different} blocks are
undirected.

\begin{thm}\label{2sat}
The $H$-cover problem is polynomial if each block of the degree partition
of $H$ has 1, 2 or 4 vertices, every color specification of each block
is of one of the types described in
Table~\ref{blocks}, and every color specification of every bipartite graph
that expresses the connections between two blocks is of
one of the types described in Table~\ref{edgeblocks}.
\end{thm}



\begin{table}
\begin{center}
\begin{tabular}{|c|p{6cm}|p{6cm}|}
\hline
block size & undirected colors & directed colors\\
\hline\hline
1 & $K_1(k)$ - $k$ loops around a vertex & $DK_1(k)$ - $k$ directed loops
around a vertex\\
\hline
2 & $2K_1(k)$ - $k$ loops around each of the two vertices &
$2DK_1(k)$ - $k$ directed loops
around each of the two vertices\\
\hline
2 &  $K_{2}(0,m)$ - $m$ parallel edges between the two vertices &
$DK_2(0,m)$ - $m$ parallel directed edges in each direction
between the two vertices\\
\hline
2 & & $DK_2(1,1)$ - one directed loop around each of the two vertices and one
directed edge in each direction between the two vertices\\
\hline
4 & $4K_1(k)$ - $k$ loops around each of the 4 vertices
& $4DK_1(k)$ - $k$ directed loops around each of the 4 vertices\\
\hline
4 & $2K_2(0,m)$ - two bundles of $m$ parallel edges between distinct
pairs of vertices
& $2DK_2(0,m)$ - disjoint union of two $DK_2(0,m)$'s\\
\hline
4 & $K_2(0,2m)+2K_1(m)$ -
a bundle of $2m$ parallel edges between two
vertices and $m$ loops around each of the remaining two vertices
& $DK_2(0,m)+2DK_1(m)$ - disjoint union of a $DK_2(0,m)$'s and two copies
of $DK_1(m)$\\
\hline
4 & & $2DK_2(1,1)$ - disjoint union of two $DK_2(1,1)$'s\\
\hline
4 & $C_4$ - a simple undirected 4-cycle
& $DC_4(1,1)$ - symmetric orientation of $C_4$\\
\hline
4 & & $DC_4(m,0)$ - directed 4-cycle with each edge replaced by $m$ parallel
edges\\
%\hline
%4 & & $DC^+_4(1,0)$ - directed 4-cycle with one directed loop around each
%vertex\\
\hline
\end{tabular}
\caption{Color specifications of blocks.}
\label{blocks}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{|c|p{10cm}|}
\hline
block sizes & connecting graphs  \\
\hline\hline
1 - 1 & $K_{1,1}(k)$ - $k$ parallel edges between the vertices
\\
\hline
1 - 2 & $K_{1,2}$ - single edges between vertices from different blocks
\\
%\hline
%1 - 4 & no edges \\
\hline
2 - 2 & $2K_{1,1}(k)$ - disjoint union of two bundles of $k$ parallel edges
each\\
\hline
2 - 2 & $K_{2,2}$ - complete bipartite graph between the two pairs of
vertices\\
\hline
2 - 4  & $2K_{1,2}$ - disjoint union of two copies of $K_{1,2}$\\
\hline
4 - 4  & $4K_{1,1}(k)$ - disjoint union of four bundles of $k$ parallel edges
each\\
\hline
4 - 4  & $2K_{2,2}$ - disjoint union of two copies of $K_{2,2}$\\
\hline
\end{tabular}
\caption{Color specifications of block connections.}
\label{edgeblocks}
\end{center}
\end{table}

Note that no edges are allowed between blocks of size 1 and 4.
It may seem somewhat surprising that block size 3 does not appear in the
table. The reason is that 4 vertices may be split naturally into two groups
of two vertices each, which does help for certain block types (see the
proof below). And indeed, while 2 undirected cycles of different colors on
the same 4-vertex set yield a polynomial instance, 2 undirected cycles of
different colors on the same 3-vertex set generate an NP-complete graph
(equivalent to the 3-starfish, cf. \cite{KPT}). The graphs from Tables~\ref{blocks} and \ref{edgeblocks} are depicted in
Figures~\ref{blundir}, \ref{bldir} and \ref{conundir}.

\begin{figure}[ht]
\begin{center}
\Ipe{blundir.ipe}
\caption{Undirected blocks.}
\label{blundir}
\end{center}
\end{figure}


\begin{figure}[ht]
\begin{center}
\Ipe{bldir.ipe}
\caption{Directed blocks.}
\label{bldir}
\end{center}
\end{figure}




\medskip
\begin{pf}
Suppose $H$ is as described in the assumption and we are given a cdm-graph
$G$ subject to the question if $G$ covers $H$. We first check if $G$ and
$H$ have the same degree refinement, and let us assume that this is the case.
Let $B_i, i=1,2,\ldots,n$ be
the blocks of the degree partition of $H$ and let $B'_i,i=1,2,\ldots,n$ be
the corresponding degree partition of $G$.

Assume $f:V(G)\to V(H)$ is a mapping such that $f^{-1}(B_i)=B'_i$
for every
block $B_i$. It follows that $f(x)$
is uniquely determined if $x\in B'_i$ and $B_i$ has only one vertex.

For every two-element block $B_i$, denote the vertices of $B_i$ by
$L_i,R_i$. For every $x\in B'_i$, we introduce a variable $\alpha(x)$.
These variables will attain values from $GF(2)=\{0,1\}$ so that
$\alpha(x)=1$ if and only if $f(x)=L_i$.

For every four-element block $B_i$, denote its vertices by
$S_i,T_i,X_i,Y_i$. For every $x\in B'_i$, we introduce  variables $\phi(x),
\psi(x)$ and $\xi(x)$ so that
$\phi(x)=1$ if and only if $f(x)\in\{S_i,T_i\}$,
$\psi(x)=1$ if and only if $f(x)\in\{S_i,X_i\}$ and
$\xi(x)=1$ if and only if $f(x)\in\{S_i,Y_i\}$.

We build up a system of linear equations modulo 2, which is solved by these
variables  if and
only if $f$ is a vertex-covering projection of $G$ onto $H$.
Since equations modulo 2 can be solved in polynomial time via Gauss
elimination, a polynomial algorithm for our covering problem will thus follow.
The description of
this system is somewhat tedious but cannot be avoided.

0. If $B_i$ is a 1-element block and $x\in B'_i$ then the fact that $H$ and
$G$ have the same degree refinement implies that $x$ has the right number
of neighbors in $B'_i$ (if $B_i^c\simeq K_1(k)$ then $r^c_{ii}=2k$, and
hence $r'^c_{ii}=
|\{e\in F(G): x\in\mu(e), \mu(e)\setminus\{x\}\in B'_i, C(e)=c\}|
+2|\{e\in L(G): \mu(e)=x, C(e)=c\}|=2k$ and (6') of the definition of
vertex-coverings is fulfilled for $x$;
if $B_i^c\simeq DK_1(k)$ then $d^{c+}_{ii}=d^{c-}_{ii}=k$, and
hence $d'^{c+}_{ii}=
|\{e\in D(G): \mu(e)\in \{x\}\times B_i, C(e)=c\}|,
d'^{c-}_{ii}=
|\{e\in D(G): \mu(e)\in  B_i\times\{x\}, C(e)=c\}|$ and
(4') of the definition of
vertex-coverings is fulfilled for $x$). The following three cases describe
two-element blocks.

1. For every edge color $c$ such that $B^c_i\cong 2K_1(k)$ or
$B^c_i\cong 2DK_1(k)$ and vertices
$x,y\in B'_i$ connected by an edge of color $c$ (note that
$deg^c_G(x)=2k$ resp. $deg^c_G(x)=(k,k)$ for each vertex
$x\in B'_i$), we introduce the equation
\begin{eqnarray}\alpha(x) + \alpha(y)=0.\label{eq1}\end{eqnarray}
Indeed, if $f$ is a vertex-covering projection then $x,y$ must map on the
same vertex of $B_i$ (i.e., either both of them map on $L_i$ or both of
them on $R_i$) and $\alpha(x)=\alpha(y)$, which is the same as
equation~(\ref{eq1}). On the other hand, if $\alpha(x)=\alpha(y)$ for each
pair $x,y$ connected by an edge of color $c$, then $f$ maps
all vertices connected
to a vertex $x\in B'_i$ by an edge of color $c$ onto the same vertex,
namely onto $f(x)$, and the fact that $G$ and $H$ have the same degree
refinement implies that (4') resp. (6') is fulfilled for vertex $x$.


\begin{figure}[ht]
\begin{center}
\Ipe{conundir.ipe}
\caption{Block connections.}
\label{conundir}
\end{center}
\end{figure}



2. For every edge color $c$ such that $B^c_i\cong K_2(0,m)$ or
$B^c_i\cong DK_2(0,m)$ and vertices
$x,y\in B'_i$ connected by an edge of color $c$ (note that
$deg^c_G(x)=m$ resp. $deg^c_G(x)=(m,m)$ for each vertex
$x\in B'_i$), we introduce the equation
\begin{eqnarray}\alpha(x) + \alpha(y) = 1.\label{eq2}\end{eqnarray}
If $f$ is a vertex-covering projection then $x,y$ must be mapped onto
different vertices of $B_i$, i.e., one of them onto $L_i$ and the other one
onto $B_i$. This means that
 $\alpha(x)\neq \alpha(y)$, which is equivalent to equation~(\ref{eq2}).
On the other hand, if equation~(\ref{eq2}) is fulfilled for every
two vertices $x,y$ connected by an edge of color $c$, none of such edges is
a loop and the equality of degree refinements of $G$ and $H$ implies that
(4') resp. (5') is fulfilled for $x$.

3. For every edge color $c$ such that $B^c_i\cong DK_2(1,1)$
and edges $e,e'\in D(G)$ of color $c$
such that $\mu(e)=(x,z), \mu(e')=(y,z)$
(or $\mu(e)=(z,x), \mu(e')=(z,y)$) for vertices
$x,y,z\in B'_i$ (note that
$deg^c_G(x)=(2,2)$ for each vertex
$x\in B'_i$), we introduce the equation
\begin{eqnarray}\alpha(x) + \alpha(y) = 1.\label{eq3}\end{eqnarray}
If $f$ is a vertex-covering projection then one of $x,y$ is mapped onto
$L_i$ and the other one onto $R_i$ (note that necessarily $x\neq y$) and
hence $\alpha(x)\neq \alpha(y)$, i.e., $\alpha(x)+\alpha(y)=1$. On the
other hand, if equation~(\ref{eq3}) is fulfilled for each such triple
$x,y,z$, then $f(x)\neq f(y)$. Since for every $z\in B'_i$, there are
exactly two vertices, say $x,y\in B'_i$, connected to $z$ by edges of color
$c$ directed to $z$ (and exactly two vertices, say $x',y'\in B'_i$
connected to $z$ by edges of color $c$ directed from $z$), one of the
vertices $x,y$ maps onto $L_i$ and the other one onto $R_i$ (and the same is
true for $x',y'$), and (4') is fulfilled for $z$. The argumentation is
analogous in the forthcoming cases. Therefore we always give the full
description of the equations, but only sketch the proofs.


Before we proceed to the equations based on particular
4-vertex blocks, we should note
that the variables $\phi(x), \psi(x)$ and $\xi(x)$ are not independent. It
is readily seen that $\phi(x)=\psi(x)$ if and only if $\xi(x)=1$, i.e.,
these 3 variables are tied by the equation
\begin{eqnarray}\phi(x)+\psi(x)+\xi(x) = 1\label{eq4}\end{eqnarray}
and such equation is added to our system for every $x\in B'_i$, whenever
$|B_i|=4$. The reason why we introduce three dependent variables is that
this enables a more uniform description of the equations. We purposedly
include dependent equations, since we are not interested in the minimum
possible number of them, but rather favor the clarity of the argumentation
in the proof below.

4. For every edge color $c$ such that $B^c_i\cong 4K_1(k)$ or
$B^c_i\cong 4DK_1(k)$ and vertices
$x,y\in B'_i$ connected by an edge of color $c$,
%(note that
%$deg^c_G(x)=2k$ resp. $deg^c_G(x)=(k,k)$ for each vertex
%$x\in B'_i$),
we introduce the equations
\begin{eqnarray}\phi(x) = \phi(y)\label{eq5}\\
\psi(x) = \psi(y)\label{eq6}\\
\xi(x) = \xi(y)\label{eq7}.
\end{eqnarray}
These equations express $f(x)=f(y)$ for such pair of vertices $x,y$.

5. Consider  $x,y\in B'_i$ connected by an edge of color $c$ and suppose
$B_i^c\cong 2K_2(0,m)$ or $B_i^c\cong 2DK_2(0,m)$. If the edges of
$B_i^c$ are between $S_i$ and $T_i$ (and between $X_i$ and $Y_i$), we add
equations
\begin{eqnarray}
\phi(x) + \phi(y) = 0\label{eq8}\\
\psi(x) + \psi(y) = 1\label{eq9}\\
\xi(x) + \xi(y)=1\label{eq10}.
\end{eqnarray}
Equation (\ref{eq8}) expresses $f(x)\in\{S_i,T_i\}$ iff $f(y)\in\{S_i,T_i\}$,
while equations~(\ref{eq9}) and (\ref{eq10})
express $f(x)\in\{S_i,X_i\}$ iff
$f(y)\in\{T_i,Y_i\}$, i.e., altogether $f(x)=S_i$ iff $f(y)=T_i$ and
$f(x)=X_i$ iff $f(y)=Y_i$.

If the edges of $B^c_i$
are between $S_i$ and $X_i$ (and between $T_i$ and $Y_i$),
we add
equations\\
\mbox{\quad}\hfill$\phi(x) + \phi(y) = 1$\hfill(\ref{eq8}$'$)\\
\mbox{\quad}\hfill$\psi(x) + \psi(y) = 0$\hfill(\ref{eq9}$'$)\\
\mbox{\quad}\hfill$\xi(x) + \xi(y)=1.$\hfill(\ref{eq10}$'$)\\
Finally,
if these edges are between $S_i$ and $Y_i$ (and between $T_i$ and $X_i$),
we add
equations  \\
\mbox{\quad}\hfill$\phi(x) + \phi(y) = 1$\hfill(\ref{eq8}$''$)\\
\mbox{\quad}\hfill$\psi(x) + \psi(y) = 1$\hfill(\ref{eq9}$''$)\\
\mbox{\quad}\hfill$\xi(x) + \xi(y)=0.$\hfill(\ref{eq10}$''$)

%Tady pokracuj

6. Let  $x,y\in B'_i$ be connected by an edge of color $c$ and suppose
$B_i^c\cong K_2(0,2m)+2K_1(m)$ or $B_i^c\cong DK_2(0,m)+2DK_1(m)$.
Let $\tau\in\{\phi,\psi,\xi\}$ be such that the two vertices forming
$K_2(0,2m)$ (resp. $DK_2(m)$) in $B^c_i$ have the same value of $\tau$
and let this value be $\varepsilon\in \{0,1\}$.
Then we add
equations
\begin{eqnarray}
\rho(x) + \sigma(y) = \varepsilon\label{eq11}
\end{eqnarray}
for $\rho,\sigma\in\{\phi,\psi,\xi\}\setminus\{\tau\}, \rho\neq\sigma$.
For the sketch of the proof, consider e.g. the case when $X_i$ and $Y_i$
are adjacent in $B^c_i$, i.e., $\tau=\phi$ and $\varepsilon=0$. Then
equation~(\ref{eq11}) becomes
$$\psi(x)+\xi(y)=0,$$
$$\psi(y)+\xi(x)=0,$$
which is solved exactly by the following 4-tuples
$$(\psi(x),\xi(x),\psi(y),\xi(y))\in\{(0,0,0,0),(1,1,1,1),(0,1,1,0),(1,0,0,1)\},$$
i.e., these equations express
$$f(x)=f(y)=S_i\mbox{ or }f(x)=f(y)=T_i\mbox{ or }
\{f(x),f(y)\}=\{X_i,Y_i\}.$$

7. For every edge color $c$ such that $B^c_i\cong 2DK_2(1,1)$
and edges $e,e'\in D(G)$ of color $c$
such that $\mu(e)=(x,z), \mu(e')=(y,z)$
(or $\mu(e)=(z,x), \mu(e')=(z,y)$) for vertices
$x,y,z\in B'_i$ , we add equations depending again on the actual placement
of $2DK_2(1,1)$ on $B^c_i$:
If the non-loop edges of
$B_i^c$ are between $S_i$ and $T_i$ (and between $X_i$ and $Y_i$), we add
equations
\begin{eqnarray}
\phi(x) + \phi(z) = 0\label{eq12}\\
\psi(x) + \psi(y) = 1\label{eq13}\\
\xi(x) + \xi(y)=1. \label{eq14}
\end{eqnarray}
These equations express that $f(x),f(y)\in\{S_i,T_i\}$ (or
$f(x),f(y)\in\{X_i,Y_i\}$) provided $f(z)\in\{S_i,T_i\}$ (resp.
$f(z)\in\{X_i,Y_i\}$), and $f(x)\neq f(y)$. I.e., if $z$ maps into
$\{S_i,T_i\}$ then one of $x,y$ maps onto $S_i$ and the other one onto
$T_i$,
and
if $z$ maps into
$\{X_i,Y_i\}$ then one of $x,y$ maps onto $X_i$ and the other one onto
$Y_i$.

If the non-loop  edges of $B^c_i$
are between $S_i$ and $X_i$ (and between $T_i$ and $Y_i$),
we add
equations  \\
\mbox{\quad}\hfill$\phi(x) + \phi(y) = 1$\hfill(\ref{eq12}$'$)\\
\mbox{\quad}\hfill$\psi(x) + \psi(z) = 0$\hfill(\ref{eq13}$'$)\\
\mbox{\quad}\hfill$\xi(x) + \xi(y)=1.$\hfill(\ref{eq14}$'$)\\
Finally,
if these edges are between $S_i$ and $Y_i$ (and between $T_i$ and $X_i$),
we add
equations\\
\mbox{\quad}\hfill$\phi(x) + \phi(y) = 1$\hfill(\ref{eq12}$''$)\\
\mbox{\quad}\hfill$\psi(x) + \psi(y) = 1$\hfill(\ref{eq13}$''$)\\
\mbox{\quad}\hfill$\xi(x) + \xi(z)=0.$\hfill(\ref{eq14}$''$)\\


\medskip
 Next we pay attention to those blocks $B_i$ whose  color specifications
are based on a 4-cycle. For the sake of brevity we assume that this 4-cycle
is $S_i\to T_i\to X_i\to Y_i\to S_i$ (the other possibilities are similar
and would be derived from Equations~(\ref{eq15}-\ref{eq27}) similarly as
Equations~(\ref{eq12}'-\ref{eq14}') and (\ref{eq12}''-\ref{eq14}'')
were derived from Equations~(\ref{eq12}-\ref{eq14}).

8. Consider first a color of undirected edges, i.e.,
$B_i^c\cong C_4$. Let $x\in B'_i$ and
let $e,e'\in D(G)$ be distinct edges of color $c$ such that $\mu(e)=\{x,y\},
\mu(e')=\{x,z\}$ for vertices $y,z\in B'_i$. Then we add equations
\begin{eqnarray}
\phi(z) + \phi(y) = 1\label{eq15}\\
\psi(z) + \psi(y) = 0\label{eq16}\\
\xi(z) + \xi(y)=1, \label{eq17}
\end{eqnarray}
and for every pair of vertices $x,y$ connected by an edge of color $c$,
we add equation
\begin{eqnarray}
\psi(x) + \psi(y) = 1.\label{eq18}
\end{eqnarray}
Equation (\ref{eq18}) expresses that vertices connected by edges of color
$c$ have distinct value of $\psi$, while equations~(\ref{eq15}-\ref{eq17})
express that vertices connected to a common neighbor by edges of color $c$
have the same $\psi$ but map onto distinct vertices of $B_i$. I.e., if
$f(x)=S_i$ then one of $y,z$ is mapped onto $T_i$ and the other one onto
$Y_i$, etc.

9. Next
consider a color specification $B_i^c\cong DC_4(m,0)$. Let $x\in B'_i$ and
let $e,e'\in D(G)$ be edges of color $c$ such that $\mu(e)=(x,y),
\mu(e')=(x,z)$ (or $\mu(e)=(y,x),
\mu(e')=(z,x)$) for vertices $y,z\in B'_i$. Then we add equations
\begin{eqnarray}
\phi(z) + \phi(y) = 0\label{eq19}\\
\psi(z) + \psi(y) = 0\label{eq20}\\
\xi(z) + \xi(y)=0,   \label{eq21}
\end{eqnarray}
and for every pair of vertices $x,y$ connected by an edge of color $c$
(in this order, i.e., $\mu(e)=(x,y)$ for some edge $e\in D(G)$ of color
$c$), we add equations
\begin{eqnarray}
\psi(x) + \psi(y) = 1\label{eq22}\\
\psi(y) + \xi(x) + \xi(y) = 1. \label{eq23}
\end{eqnarray}
Equations (\ref{eq19}-\ref{eq21}) express that all vertices connected to a
common neighbor by edges of color $c$ directed all towards (or all from)
this common neighbor map onto the same vertex of $B_i$.
Equations~(\ref{eq22}-\ref{eq23}) are solved exactly by values
corresponding to
$$(f(x),f(y))\in\{(S_i,T_i),(T_i,X_i),(X_i,Y_i),(Y_i,S_i)\}.$$

10. Finally let
$B_i^c\cong DC_4(1,1)$. Let $x\in B'_i$ and
let $e,e'\in D(G)$ be the two edges of color $c$ that start in $x$
(or that end in $x$) and let these edges end (resp. start) in vertices
$y,z\in B'_i$. Then we add equations
\begin{eqnarray}
\phi(z) + \phi(y) = 1\label{eq24}\\
\psi(z) + \psi(y) = 0\label{eq25}\\
\xi(z) + \xi(y)=1.   \label{eq26}
\end{eqnarray}
For every pair of vertices $x,y$ connected by an edge of color $c$,
we add equation
\begin{eqnarray}
\psi(x) + \psi(y) = 1.\label{eq27}
\end{eqnarray}
Similarly as in case 8., these equations guarantee that if $f(x)=S_i$ then
one of $x,y$ is mapped onto $T_i$ and the other one onto $Y_i$, etc.

\medskip
Now we describe the equations arising from interblock connections. We
consider blocks $B_i,B_j$ such that $|B_i|\le|B_j|$.
% and we assume $x\in
%B'_i$, $y\in B'_j$.
Let $BC_{ij}^c$ be the color $c$ specification of the
bipartite graph between $B_i$ and $B_j$ (we consider only colors such
that the edge set of $BC_{ij}^c$ is nonempty).

11. When $|B_i|=|B_j|=1$, no equations are needed (the values of $f(x)$ and
$f(y)$ are uniquely determined and the right number of neighbors is
guaranteed by the equality of the degree refinements of $G$ and $H$).

12. If $|B_i|=1$ and $|B_j|=2$ then $BC_{ij}^c\cong K_{1,2}$. Let $x\in B'_i$
and let $e,e'\in F(G)$, $\mu(e)=\{x,y\}, \mu(e')=\{x,z\}$, be the two edges
of color $c$ incident to $x$ that end in $B'_j$.
Then $y,z$ should be mapped onto different
vertices of $B_j$, which is expressed by the equation
\begin{eqnarray}
\alpha(y) + \alpha(z) = 1\label{eq28}.
\end{eqnarray}

13. Next suppose $|B_i|=|B_j|=2$ and $BC_{ij}^c\cong 2K_{1,1}(m)$.
Let $x\in B'_i$ and $y\in B'_j$ be connected by an edge of color $c$ in
$G$.
If the edges of $BC_{ij}^c$ connect the vertices $L_i$ and $L_j$ (and $R_i$
and $R_j$), we add the equation
\begin{eqnarray}
\alpha(x) + \alpha(y) = 0\label{eq29},
\end{eqnarray}
if the edges of $BC_{ij}^c$ connect the vertices $L_i$ and $R_j$ (and $R_i$
and $L_j$), we add the equation\\
\mbox{\quad}\hfill$\alpha(x) + \alpha(y) = 1.$\hfill(\ref{eq29}$'$)\\
These equations express that all neighbors of a vertex mapped onto $L_i$
(or $R_i$)
 are mapped onto $L_j$ (resp. onto $R_j$) in the former case, and vice
versa in the latter case.

14. If $|B_i|=|B_j|=2$, $BC_{ij}^c\cong K_{2,2}$,
 $x\in B'_i$ and $y\in B'_j$ are connected by an edge of color $c$ in
$G$ and $u\in B'_j$ (resp. $v\in B'_i$) is the endpoint of the other edge
of color $c$ incident to $x$ (resp. $y$), we add the equations
\begin{eqnarray}
\alpha(y) + \alpha(u) = 1,\label{eq30}\\
\alpha(x) + \alpha(v) = 1,\label{eq31}
\end{eqnarray}
which express that each vertex of $B'_i$ is connected by an edge of color
$c$ to exactly one vertex mapped onto $L_j$ and to one vertex mapped onto
$R_j$ (and vice versa).

15. Let $|B_i|=2$, $|B_j|=4$ and $BC_{ij}^c\cong 2K_{1,2}$.
Let $x\in B'_i$ and $y\in B'_j$ be connected by an edge of color $c$ in
$G$, and let $z\in B'_j$ be the endpoint of the other edge of color $c$
incident to $x$. Our equations now depend on the routing of the edges of
$BC_{ij}^c$. Let $\pi\in\{\phi,\psi,\xi\}$ be such that the neighbors of
$L_i$ (in $BC_{ij}^c$) have the same $\pi$, and let the value of their
$\pi$ be $\varepsilon$.
Then we add the equations ($\sigma\in\{\phi,\psi,\xi\}\setminus\{\pi\}$)
\begin{eqnarray}
\pi(y) + \pi(z) = 0\label{eq32},        \\
\sigma(y) + \sigma(z) = 1, \label{eq33}   \\
\alpha(x) + \pi(y) = 1+\varepsilon \label{eq34}
\end{eqnarray}
(note that the first and last of these equations yield
$\alpha(x)+\pi(z)=1+\varepsilon$ as well).\\
E.g., if $L_i$ is adjacent to $T_j,X_j$, we have $\pi=\xi$ and
$\varepsilon=0$ and the equations are
\begin{eqnarray*}
\xi(y) + \xi(z) = 0,\\
\phi(y) + \phi(z) = 1,\\
\psi(y) + \psi(z) = 1,\\
\alpha(x) + \xi(y) = 1.
\end{eqnarray*}
The first three of these equations guarantee that $y,z$ map onto distinct
vertices having the same value of $\xi$, and the last equation expresses
how this value of $\xi$ depends on $f(x)$. Namely, if $f(x)=L_i$ then
$\xi=0$ and one
of $y,z$ maps onto $T_j$ and the other one onto $X_j$, and if $f(x)=R_i$
then one
of $y,z$ maps onto $S_j$ and the other one onto $Y_j$.

16. Suppose $|B_i|=|B_j|=4$ and $BC_{ij}^c\cong 2K_{2,2}$.
Let $x\in B'_i$ and $y\in B'_j$ be connected by an edge of color $c$ in
$G$, and let $u\in B'_j$ (resp. $v\in B'_i$)
be the endpoint of the other edge of color $c$
incident to $x$ (resp. $y$).
Our equations depend again on the routing of the edges of
$BC_{ij}^c$. Let $\pi,\rho\in\{\phi,\psi,\xi\}$ be such that the vertices of
$B_i$ with $\pi=1$ are adjacent (in $BC_{ij}^c$) to vertices of $B_j$ of
the value of
$\rho=\varepsilon$.
Then we add the equations ($\sigma\in\{\phi,\psi,\xi\}\setminus\{\pi\}$,
$\tau\in\{\phi,\psi,\xi\}\setminus\{\rho\}$)
\begin{eqnarray}
\pi(x) + \pi(v) = 0\label{eq35},\\
\sigma(x) + \sigma(v) = 1,    \label{eq36}\\
\rho(y) + \rho(u) = 0\label{eq37},\\
\tau(y) + \tau(u) = 1,          \label{eq38}\\
\pi(x) + \rho(y) = 1+\varepsilon.     \label{eq39}
\end{eqnarray}
Similarly as in cases 14. and 15., these equations expresses that $f$ is a
vertex-covering projection in the neighborhood of $x$.

17. Finally let
$|B_i|=|B_j|=4$ and $BC_{ij}^c\cong 4K_{1,1}(m)$.
Let $x\in B'_i$ and $y\in B'_j$ be connected by an edge of color $c$ in
$G$. Our equations again depend on the routing of edges in
$BC_{ij}^c$, but this time the actual dependence is less simple to describe.
Therefore we first describe the simplest case when $S_i$ is adjacent to
$S_j$, $T_i$ to $T_j$, $X_i$ to $X_j$ and $Y_i$ to $Y_j$.
In this case the neighbors have to have the same $\phi,\psi$ and $\xi$,
which is expressed by the equations (here we assume $x\in B'_i,y\in B'_j$
connected by an edge of color $c$)
\begin{eqnarray}
\phi(x) + \phi(y) = 0\label{eq40},\\
\psi(x) + \psi(y) = 0,\label{eq41}\\
\xi(x) + \xi(y) = 0.  \label{eq42}
\end{eqnarray}

For the general case, we exploit the fact that the vertices of $B_i$ and
$B_j$ are uniquely determined by their $\phi$ and $\psi$. We will express
them as elements of $GF(2)^2$ according to their $(\phi,\psi)$, i.e.
$$S\qquad\sim\qquad(1,1),$$
$$T\qquad\sim\qquad(1,0),$$
$$X\qquad\sim\qquad(0,1),$$
$$Y\qquad\sim\qquad(0,0).$$
Given the edges of $BC^c_{ij}$, we define a bijection $g:GF(2)^2\to
GF(2)^2$ so that
$$g(p,q)=(r,s)\mbox{ if and only if }(p,q)\mbox{ is adjacent to
}(r,s)\mbox{ in }BC^c_{ij}$$
($p,q,r,s\in \{0,1\}$). Our separate Lemma~\ref{lak} says that then there
exists a system of linear equations (Eq) over the variables $p,q,r,s$ such
that solution set is exactly $\{(p,q,g(p,q)):p,q\in GF(2)\}$. If $x\in
B'_i$ and $y\in B'_j$ are connected by an edge of color $c$, we add the
system of equations (Eq) with variables renamed $\phi(x), \psi(x), \phi(y),
\psi(y)$ instead of equations~(\ref{eq39}-\ref{eq41}).
\end{pf}

\begin{lem}\label{lak}
For every bijection $g:GF(2)^2\to
GF(2)^2$,  there
exists a system of linear equations over variables $p,q,r,s$ whose
solution set is exactly $\{(p,q,g(p,q)):p,q\in GF(2)\}$.
\end{lem}

\begin{pf}
Set ${\cal L}=\{(p,q,g(p,q)):p,q\in GF(2)\}$ and ${\cal
U}=\{(p,q,g(p,q)+g(0,0)):p,q\in GF(2)\}$, i.e., ${\cal
L}=(0,0,g(0,0))+{\cal U}$. We claim that $\cal U$ is a linear subspace of
$GF(2)^4$. Indeed, in $GF(2)^2$ the sum of {\em any} two non-zero vectors
equals the third non-zero vector, and the same is true for $\cal U$,
since the zero vector belongs to $\cal U$. Hence $dim_{GF(2)}{\cal U}=2$
and $\cal L$ is the solution set of a system of two independent linear
equations.
\end{pf}


\begin{thebibliography}{9}

\bibitem{AFS} J. Abello, M.R. Fellows and J.C. Stillwell, On the complexity
and
combinatorics of covering finite complexes, {\sl Australasian Journal of
Combinatorics 4} (1991), 103-112;

\bibitem{Ang} D. Angluin, Local and global properties in networks of
processors,
in {\sl Proceedings of the 12th ACM Symposium on Theory of Computing}
(1980),
82-93;

\bibitem{AG} D. Angluin and A. Gardner, Finite common coverings of pairs of
regular graphs, {\sl Journal of Combinatorial Theory B 30} (1981), 184-187;

\bibitem{Big} N. Biggs, {\sl Algebraic Graph Theory}, Cambridge University
Press, 1974;

%\bibitem{Fi} J. Fiala, Covers of graphs (in Czech), Master Thesis, Charles
%University, 1997

\bibitem{GJ} M.R. Garey and D.S. Johnson, {\sl Computers and
Intractability},
W.H.Freeman and Co., 1978;

%\bibitem{HN} P. Hell and J. Ne\v set\v ril, On the complexity of
%$H$-colouring,
%{\sl Journal of Combinatorial Theory B 48} (1990), 92-110;

\bibitem{Ho} I. Holyer, The \NP-completeness of edge-coloring, {\sl SIAM
J.
Computing 4} (1981), 718-720;

\bibitem{regco}
J. Kratochv\'{\i}l: Regular codes in regular graphs are difficult,
Discrete Math. 133 (1994), 191-205

\bibitem{KPT}
J. Kratochv\'{\i}l, A. Proskurowski, J.A. Telle: On the complexity of graph
covering problems, In:  Graph-Theoretic Concepts in Computer
Science, Proceedings of 20th International Workshop WG'94,
Munchen, Germany, 1994, Lecture Notes in Computer Science 903, Springer Verlag,
Berlin Heidelberg, 1995, pp. 93-105.

\bibitem{KPT1}
J. Kratochv\'{\i}l, A. Proskurowski, J.A. Telle:
Covering regular graphs, to appear in Journal of Combin. Theory Ser. B

\bibitem{KPT2}
J. Kratochv\'{\i}l, A. Proskurowski, J.A. Telle:
{Complexity of colored graph covers I. Colored directed multigraphs.}
(in preparation)

\bibitem{KPT3}
J. Kratochv\'{\i}l,  J.A. Telle:
{Complexity of colored graph covers III. Three-vertex graphs.}
(in preparation)

%\bibitem{Lei} F.T. Leighton, Finite common coverings of graphs, {\sl
%Journal of
%Combinatorial Theory B 33} (1982), 231-238;

%\bibitem{LG} D. Leven, Z. Galil, NP-completeness of finding the chromatic
%index of regular graphs, J. Algoritms 4 (1983) 35-44



\end{thebibliography}
\end{document}




