  Covering alignment problems arise from recent developments in genomics; so
called pan-genome graphs are replacing reference genomes, and advances in
haplotyping enable full content of diploid genomes to be used as basis of
sequence analysis. In this paper, we show that the computational complexity
will change for natural extensions of alignments to pan-genome representations
and to diploid genomes. More broadly, our approach can also be seen as a
minimal extension of sequence alignment to labelled directed acyclic graphs
(labeled DAGs). Namely, we show that finding a \emph{covering alignment} of two
labeled DAGs is NP-hard even on binary alphabets. A covering alignment asks for
two paths $R_1$ (red) and $G_1$ (green) in DAG $D_1$ and two paths $R_2$ (red)
and $G_2$ (green) in DAG $D_2$ that cover the nodes of the graphs and maximize
the sum of the global alignment scores:
$\mathsf{as}(\mathsf{sp}(R_1),\mathsf{sp}(R_2))+\mathsf{as}(\mathsf{sp}(G_1),\mathsf{sp}(G_2))$,
where $\mathsf{sp}(P)$ is the concatenation of labels on the path $P$.
Pair-wise alignment of haplotype sequences forming a diploid chromosome can be
converted to a two-path coverable labelled DAG, and then the covering alignment
models the similarity of two diploids over arbitrary recombinations. We also
give a reduction to the other direction, to show that such a
recombination-oblivious diploid alignment is NP-hard on alphabets of size $3$.
