标题： Steiner定向的结构参数 显示英文标题

标题： Structural Parameters for Steiner Orientation

摘要： 我们考虑\textsc{斯特奈尔定向}问题，其中输入是一个混合图$G=(V,E,A)$和一组$k$需求对$(s_i,t_i)$，$i\in[k]$。 目标是定向$G$的无向边，使得所得的有向图对于所有$i\in[k]$都存在从$s_i$到$t_i$的有向路径。我们采用结构参数化复杂性的观点，研究\textsc{斯特凡定向}在标准度量（如树宽）下的复杂性。我们的结果表明，从这个观点来看，\textsc{斯坦纳 方向}是一个令人惊讶的困难问题。 特别地，我们的主要贡献如下：(1) 我们证明了\textsc{Steiner定向}在基础图具有反馈顶点数 2、树宽 2、路径宽 3 和顶点完整性 6 的实例上是 NP 完全的；(2) 我们提出了一个由顶点覆盖数$\mathrm{vc}$参数化的 XP 算法，其复杂度为$n^{\mathcal{O}(\mathrm{vc}^2)}$。此外，我们证明了该运行时间本质上是最优的，通过证明运行时间为$n^{o(\mathrm{vc}^2)}$将反驳 ETH；(3) 我们考虑了由无向或有向边的数量（$|E|$或$|A|$）的参数化，并观察到对于前者的平凡$2^{|E|}n^{\mathcal{O}(1)}$-时间算法在 SETH 下是最优的。 与此互补，我们证明该问题有一个$2^{\mathcal{O}(|A|)}n^{\mathcal{O}(1)}$-时间算法。 除了上述内容，我们还考虑了\textsc{斯特凡定向}在$\mathrm{tw}+k$参数化下的复杂度（FPT），团距离（FPT），以及$\mathrm{vc}+k$（具有多项式核的 FPT）。 显示英文摘要

摘要： 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).