SAT-Encodings for Treecut Width and Treedepth

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113720" target="_blank" >RIV/00216224:14330/19:00113720 - isvavai.cz</a>

Result on the web

<a href="https://epubs.siam.org/doi/10.1137/1.9781611975499.10" target="_blank" >https://epubs.siam.org/doi/10.1137/1.9781611975499.10</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/1.9781611975499.10" target="_blank" >10.1137/1.9781611975499.10</a>

Result language

angličtina

Original language name

SAT-Encodings for Treecut Width and Treedepth

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2019

Confidentiality

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

Article name in the collection

ALENEX 2019

ISBN

9781611975499

ISSN

2164-0300

e-ISSN

—

Number of pages

13

Pages from-to

117-129

Publisher name

SIAM

Place of publication

USA

Event location

USA

Event date

Jan 1, 2019

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—