Show simple item record

An FPT 2-Approximation for Tree-Cut Decomposition

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung*
hal.structure.identifierDepartment of Mathematical Sciences, KAIST
dc.contributor.authorOum, Sang-il*
hal.structure.identifierLaboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
dc.contributor.authorPaul, Christophe
HAL ID: 4726		*
hal.structure.identifierLaboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
dc.contributor.authorSau Valls, Ignasi
HAL ID: 7331
ORCID: 0000-0002-8981-9287		*
hal.structure.identifierComputer Technology Institute and Press "Diophantus"
dc.contributor.authorThilikos, Dimitrios M.
HAL ID: 178742
ORCID: 0000-0003-0470-1800		*
dc.date.accessioned2019-06-25T10:44:49Z
dc.date.available2019-06-25T10:44:49Z
dc.date.issued2018
dc.identifier.issn0178-4617
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19025
dc.language.isoenen
dc.subjectFixed-parameter tractable algorithmen
dc.subjectTree-cut widthen
dc.subjectApproximation algorithmen
dc.subject.ddc518en
dc.titleAn FPT 2-Approximation for Tree-Cut Decompositionen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe tree-cut width of a graph is a graph parameter defined by Wollan (J Combin Theory, Ser B, 110:47–66, 2015) with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width; for an input n-vertex graph G and an integer w, our algorithm either confirms that the tree-cut width of G is more than w or returns a tree-cut decomposition of G certifying that its tree-cut width is at most 2w, in time 2O(w2logw)⋅n2 . Prior to this work, no constructive parameterized algorithms, even approximated ones, existed for computing the tree-cut width of a graph. As a consequence of the Graph Minors series by Robertson and Seymour, only the existence of a decision algorithm was known.en
dc.relation.isversionofjnlnameAlgorithmica
dc.relation.isversionofjnlvol80en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2018-01
dc.relation.isversionofjnlpages116-135en
dc.relation.isversionofdoi10.1007/s00453-016-0245-5en
dc.identifier.urlsitehttps://arxiv.org/abs/1509.04880v1en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelModèles mathématiques. Algorithmesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-31T15:20:05Z
hal.faultCode{"duplicate-entry":{"hal-01690385":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record