Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

On extended formulations for parameterized steiner trees

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10437397" target="_blank" >RIV/00216208:11320/21:10437397 - isvavai.cz</a>

  • Výsledek na webu

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

  • DOI - Digital Object Identifier

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

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    On extended formulations for parameterized steiner trees

  • Popis výsledku v původním jazyce

    We present a novel linear program (LP) for the Steiner Tree problem, where a set of terminal vertices needs to be connected by a minimum weight tree in a graph G = (V, E) with non-negative edge weights. This well-studied problem is NP-hard and therefore does not have a compact extended formulation (describing the convex hull of all Steiner trees) of polynomial size, unless P=NP. On the other hand, Steiner Tree is fixed-parameter tractable (FPT) when parameterized by the number k of terminals, and can be solved in O(3k|V | + 2k|V |2) time via the Dreyfus-Wagner algorithm. A natural question thus is whether the Steiner Tree problem admits an extended formulation of comparable size. We first answer this in the negative by proving a lower bound on the extension complexity of the Steiner Tree polytope, which, for some constant c &gt; 0, implies that no extended formulation of size f(k)2cn exists for any function f. However, we are able to circumvent this lower bound due to the fact that the edge weights are non-negative: we prove that Steiner Tree admits an integral LP with O(3k|E|) variables and constraints. The size of our LP matches the runtime of the Dreyfus-Wagner algorithm, and our poof gives a polyhedral perspective on this classic algorithm. Our proof is simple, and additionally improves on a previous result by Siebert et al. [2018], who gave an integral LP of size O((2k/e)k)|V |O(1) (C) Andreas Emil Feldmann and Ashutosh Rai; licensed under Creative Commons License CC-BY 4.0

  • Název v anglickém jazyce

    On extended formulations for parameterized steiner trees

  • Popis výsledku anglicky

    We present a novel linear program (LP) for the Steiner Tree problem, where a set of terminal vertices needs to be connected by a minimum weight tree in a graph G = (V, E) with non-negative edge weights. This well-studied problem is NP-hard and therefore does not have a compact extended formulation (describing the convex hull of all Steiner trees) of polynomial size, unless P=NP. On the other hand, Steiner Tree is fixed-parameter tractable (FPT) when parameterized by the number k of terminals, and can be solved in O(3k|V | + 2k|V |2) time via the Dreyfus-Wagner algorithm. A natural question thus is whether the Steiner Tree problem admits an extended formulation of comparable size. We first answer this in the negative by proving a lower bound on the extension complexity of the Steiner Tree polytope, which, for some constant c &gt; 0, implies that no extended formulation of size f(k)2cn exists for any function f. However, we are able to circumvent this lower bound due to the fact that the edge weights are non-negative: we prove that Steiner Tree admits an integral LP with O(3k|E|) variables and constraints. The size of our LP matches the runtime of the Dreyfus-Wagner algorithm, and our poof gives a polyhedral perspective on this classic algorithm. Our proof is simple, and additionally improves on a previous result by Siebert et al. [2018], who gave an integral LP of size O((2k/e)k)|V |O(1) (C) Andreas Emil Feldmann and Ashutosh Rai; licensed under Creative Commons License CC-BY 4.0

Klasifikace

  • 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)

Návaznosti výsledku

  • Projekt

    <a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>

  • Návaznosti

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

Ostatní

  • Rok uplatnění

    2021

  • 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ů

Údaje specifické pro druh výsledku

  • Název statě ve sborníku

    16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

  • ISBN

    978-3-95977-216-7

  • ISSN

    1868-8969

  • e-ISSN

  • Počet stran výsledku

    16

  • Strana od-do

  • Název nakladatele

    Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

  • Místo vydání

    Dagstuhl

  • Místo konání akce

    Online

  • Datum konání akce

    8. 9. 2021

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

    WRD - Celosvětová akce

  • Kód UT WoS článku