A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers

We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems $\mathsf{H}\mathsf{a}\mathsf{m}\mathsf{i}\mathsf{l}\mathsf{t}\mathsf{o}\mathsf{n}\mathsf{i}\mathsf{a}\mathsf{n}\mathsf{P}\mathsf{a}\mathsf{t}\mathsf{h}$ and $\mathsf{H}\mathsf{a}\mathsf{m}\mathsf{i}\mathsf{l}\mathsf{t}\mathsf{o}\mathsf{n}\mathsf{i}\mathsf{a}\mathsf{n}\mathsf{C}\mathsf{y}\mathsf{c}\mathsf{l}\mathsf{e}$ are in $\mathsf{F}\mathsf{P}\mathsf{T}$. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are $\mathsf{W}[\mathsf{1}]$-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in $\mathsf{X}\mathsf{P}$ time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some $\mathsf{F}\mathsf{P}\mathsf{T}$ algorithms, e.g., for edge distance to block. Additionally, we prove para-$\mathsf{N}\mathsf{P}$-hardness when considered with the edge clique cover number.