SAT-Encodings for Treecut Width and Treedepth

D 2019

SAT-Encodings for Treecut Width and Treedepth

GANIAN, Robert; Neha LODHA; Sebastian ORDYNIAK a Stefan SZEIDER

Základní údaje

Originální název

SAT-Encodings for Treecut Width and Treedepth

Autoři

GANIAN, Robert; Neha LODHA; Sebastian ORDYNIAK a Stefan SZEIDER

Vydání

USA, ALENEX 2019, od s. 117-129, 13 s. 2019

Nakladatel

SIAM

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/19:00113720

Organizační jednotka

Fakulta informatiky

ISBN

978-1-61197-549-9

ISSN

DOI

https://doi.org/10.1137/1.9781611975499.10

EID Scopus

2-s2.0-85065174173

Klíčová slova anglicky

Parameterized Complexity

Štítky

core_A, firank_A

Změněno: 14. 5. 2020 10:43, Mgr. Michal Petr

Anotace

V originále

The decomposition of graphs is a prominent algorithmic task with numerous applications in computer science. A graph decomposition method is typically associated with a width parameter (such as treewidth) that indicates how well the given graph can be decomposed. Many hard (even #P-hard) algorithmic problems can be solved efficiently if a decomposition of small width is provided; the runtime, however, typically depends exponentially on the decomposition width. Finding an optimal decomposition is itself an NP-hard task. In this paper we propose, implement, and test the first practical decomposition algorithms for the width parameters tree-cut width and treedepth. These two parameters have recently gained a lot of attention in the theoretical research community as they offer the algorithmic advantage over treewidth by supporting so-called fixed-parameter algorithms for certain problems that are not fixed-parameter tractable with respect to treewidth. However, the existing research has mostly been theoretical. A main obstacle for any practical or experimental use of these two width parameters is the lack of any practical or implemented algorithm for actually computing the associated decompositions. We address this obstacle by providing the first practical decomposition algorithms.

Citovat

GANIAN, Robert; Neha LODHA; Sebastian ORDYNIAK a Stefan SZEIDER. SAT-Encodings for Treecut Width and Treedepth. Online. In Stephen G. Kobourov and Henning Meyerhenke. ALENEX 2019. USA: SIAM, 2019, s. 117-129. ISBN 978-1-61197-549-9. Dostupné z: https://doi.org/10.1137/1.9781611975499.10.

@inproceedings{1648252,
   author = {Ganian, Robert and Lodha, Neha and Ordyniak, Sebastian and Szeider, Stefan},
   address = {USA},
   booktitle = {ALENEX 2019},
   doi = {https://doi.org/10.1137/1.9781611975499.10},
   editor = {Stephen G. Kobourov and Henning Meyerhenke},
   keywords = {Parameterized Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-1-61197-549-9},
   pages = {117-129},
   publisher = {SIAM},
   title = {SAT-Encodings for Treecut Width and Treedepth},
   url = {https://epubs.siam.org/doi/10.1137/1.9781611975499.10},
   year = {2019}
}

TY  - CONF
ID  - 1648252
AU  - Ganian, Robert - Lodha, Neha - Ordyniak, Sebastian - Szeider, Stefan
PY  - 2019
TI  - SAT-Encodings for Treecut Width and Treedepth
PB  - SIAM
CY  - USA
SN  - 9781611975499
KW  - Parameterized Complexity
UR  - https://epubs.siam.org/doi/10.1137/1.9781611975499.10
L2  - https://epubs.siam.org/doi/10.1137/1.9781611975499.10
N2  - The decomposition of graphs is a prominent algorithmic task with numerous applications in computer science. A graph decomposition method is typically associated with a width parameter (such as treewidth) that indicates how well the given graph can be decomposed. Many hard (even #P-hard) algorithmic problems can be solved efficiently if a decomposition of small width is provided; the runtime, however, typically depends exponentially on the decomposition width. Finding an optimal decomposition is itself an NP-hard task. In this paper we propose, implement, and test the first practical decomposition algorithms for the width parameters tree-cut width and treedepth. These two parameters have recently gained a lot of attention in the theoretical research community as they offer the algorithmic advantage over treewidth by supporting so-called fixed-parameter algorithms for certain problems that are not fixed-parameter tractable with respect to treewidth. However, the existing research has mostly been theoretical. A main obstacle for any practical or experimental use of these two width parameters is the lack of any practical or implemented algorithm for actually computing the associated decompositions. We address this obstacle by providing the first practical decomposition algorithms.
ER  -

GANIAN, Robert; Neha LODHA; Sebastian ORDYNIAK a Stefan SZEIDER. SAT-Encodings for Treecut Width and Treedepth. Online. In Stephen G. Kobourov and Henning Meyerhenke. \textit{ALENEX 2019}. USA: SIAM, 2019, s.~117-129. ISBN~978-1-61197-549-9. Dostupné z: https://doi.org/10.1137/1.9781611975499.10.

Přehled o publikaci