Structural Parameters for Steiner Orientation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10512012" target="_blank" >RIV/00216208:11320/25:10512012 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.ISAAC.2025.38" target="_blank" >https://doi.org/10.4230/LIPIcs.ISAAC.2025.38</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ISAAC.2025.38" target="_blank" >10.4230/LIPIcs.ISAAC.2025.38</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Structural Parameters for Steiner Orientation

Popis výsledku v původním jazyce

We consider the 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 ∈ [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 ∈ [k]. We adopt the point of view of structural parameterized complexity and investigate the complexity of Steiner Orientation for standard measures, such as treewidth. Our results indicate that Steiner Orientation is a surprisingly hard problem from this point of view. In particular, our main contributions are the following:1) We show that 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 vc of complexity n^O(vc²). Furthermore, we show that this running time is essentially optimal by proving that a running time of n^o(vc²) 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^O(1)-time algorithm for the former parameter is optimal under the SETH. Complementing this, we show that the problem admits a 2^O(|A|) n^O(1)-time algorithm.In addition to the above, we consider the complexity of Steiner Orientation parameterized by tw+k (FPT), distance to clique (FPT), and vc+k (FPT with a polynomial kernel).

Název v anglickém jazyce

Structural Parameters for Steiner Orientation

Popis výsledku anglicky

We consider the 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 ∈ [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 ∈ [k]. We adopt the point of view of structural parameterized complexity and investigate the complexity of Steiner Orientation for standard measures, such as treewidth. Our results indicate that Steiner Orientation is a surprisingly hard problem from this point of view. In particular, our main contributions are the following:1) We show that 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 vc of complexity n^O(vc²). Furthermore, we show that this running time is essentially optimal by proving that a running time of n^o(vc²) 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^O(1)-time algorithm for the former parameter is optimal under the SETH. Complementing this, we show that the problem admits a 2^O(|A|) n^O(1)-time algorithm.In addition to the above, we consider the complexity of Steiner Orientation parameterized by tw+k (FPT), distance to clique (FPT), and vc+k (FPT with a polynomial kernel).

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA25-17221S" target="_blank" >GA25-17221S: Nové modely důvěry a volební robustnosti ve velkých multiagentních systémech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-408-6

ISSN

1868-8969

e-ISSN

1868-8969

Počet stran výsledku

14

Strana od-do

—

Název nakladatele

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Místo vydání

Wadern

Místo konání akce

ISAAC 2025

Datum konání akce

7. 12. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—