{"ID":2889011,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.21445","arxiv_id":"2507.21445","title":"Structural Parameters for Steiner Orientation","abstract":"We consider the \\textsc{Steiner Orientation} problem, where we are given as input a mixed graph $G=(V,E,A)$ and a set of $k$ demand pairs $(s_i,t_i)$, $i\\in[k]$. The goal is to orient the undirected edges of $G$ in a way that the resulting directed graph has a directed path from $s_i$ to $t_i$ for all $i\\in[k]$. We adopt the point of view of structural parameterized complexity and investigate the complexity of \\textsc{Steiner Orientation} for standard measures, such as treewidth. Our results indicate that \\textsc{Steiner Orientation} is a surprisingly hard problem from this point of view. In particular, our main contributions are the following: (1) We show that \\textsc{Steiner Orientation} is NP-complete on instances where the underlying graph has feedback vertex number 2, treewidth 2, pathwidth 3, and vertex integrity 6; (2) We present an XP algorithm parameterized by vertex cover number $\\mathrm{vc}$ of complexity $n^{\\mathcal{O}(\\mathrm{vc}^2)}$. Furthermore, we show that this running time is essentially optimal by proving that a running time of $n^{o(\\mathrm{vc}^2)}$ would refute the ETH; (3) We consider parameterizations by the number of undirected or directed edges ($|E|$ or $|A|$) and we observe that the trivial $2^{|E|}n^{\\mathcal{O}(1)}$-time algorithm for the former parameter is optimal under the SETH. Complementing this, we show that the problem admits a $2^{\\mathcal{O}(|A|)}n^{\\mathcal{O}(1)}$-time algorithm. In addition to the above, we consider the complexity of \\textsc{Steiner Orientation} parameterized by $\\mathrm{tw}+k$ (FPT), distance to clique (FPT), and $\\mathrm{vc}+k$ (FPT with a polynomial kernel).","short_abstract":"We consider the \\textsc{Steiner Orientation} problem, where we are given as input a mixed graph $G=(V,E,A)$ and a set of $k$ demand pairs $(s_i,t_i)$, $i\\in[k]$. The goal is to orient the undirected edges of $G$ in a way that the resulting directed graph has a directed path from $s_i$ to $t_i$ for all $i\\in[k]$. We ado...","url_abs":"https://arxiv.org/abs/2507.21445","url_pdf":"https://arxiv.org/pdf/2507.21445v1","authors":"[\"Tesshu Hanaka\",\"Michael Lampis\",\"Nikolaos Melissinos\",\"Edouard Nemery\",\"Hirotaka Ono\",\"Manolis Vasilakis\"]","published":"2025-07-29T02:33:31Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}