{"ID":2858257,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.08378","arxiv_id":"2510.08378","title":"A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers","abstract":"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{Hamiltonian\\ Path}$ and $\\mathsf{Hamiltonian\\ Cycle}$ are in $\\mathsf{FPT}$. 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[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{XP}$ time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some $\\mathsf{FPT}$ algorithms, e.g., for edge distance to block. Additionally, we prove para-$\\mathsf{NP}$-hardness when considered with the edge clique cover number.","short_abstract":"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{Hamiltonian\\ Path}$ and $\\mathsf{Hamiltonian\\ Cycle}$ are in $\\mathsf{FPT}$. In particu...","url_abs":"https://arxiv.org/abs/2510.08378","url_pdf":"https://arxiv.org/pdf/2510.08378v1","authors":"[\"Jesse Beisegel\",\"Katharina Klost\",\"Kristin Knorr\",\"Fabienne Ratajczak\",\"Robert Scheffler\"]","published":"2025-10-09T16:02:03Z","proceeding":"cs.DM","tasks":"[\"cs.DM\",\"cs.CC\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}