Show simple item record

Parameterized Orientable Deletion

hal.structure.identifierautre
dc.contributor.authorHanaka, Tesshu
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKatsikarelis, Ioannis
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLampis, Michael
HAL ID: 182546
ORCID: 0000-0002-5791-0887
hal.structure.identifierKumamoto Gakuen University
dc.contributor.authorOtachi, Yota
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
dc.date.accessioned2019-03-21T09:50:09Z
dc.date.available2019-03-21T09:50:09Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18542
dc.language.isoenen
dc.subjectGraph orientationsen
dc.subjectFPT algorithmsen
dc.subjectTreewidthen
dc.subjectSETHen
dc.subject.ddc518en
dc.titleParameterized Orientable Deletionen
dc.typeCommunication / Conférence
dc.description.abstractenA graph is d-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d. d-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-ORIENTABLE DELETION problem: given a graph G=(V,E), delete the minimum number of vertices to make G d-orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: - We show that the problem is W[2]-hard and logn-inapproximable with respect to k, the number of deleted vertices. This closes the gap in the problem's approximability.- We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by d+k, but W-hard for each of the parameters d,k separately. - We show that, under the SETH, for all d,ϵ, the problem does not admit a (d+2−ϵ)tw, algorithm where tw is the graph's treewidth, resolving as a special case an open problem on the complexity of PSEUDOFOREST DELETION. - We show that the problem is W-hard parameterized by the input graph's clique-width. Complementing this, we provide an algorithm running in time dO(d⋅cw), showing that the problem is FPT by d+cw, and improving the previously best known algorithm for this case.en
dc.identifier.citationpages24:1-24:13en
dc.relation.ispartoftitle16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)en
dc.relation.ispartofeditorEppstein, David
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.relation.ispartofpublcityWadernen
dc.relation.ispartofdate2018
dc.subject.ddclabelModèles mathématiques. Algorithmesen
dc.relation.conftitleSWAT 2018en
dc.relation.confdate2018-06
dc.relation.confcityMalmöen
dc.relation.confcountrySwedenen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-21T09:40:11Z
hal.identifierhal-02075097*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
LIPIcs-SWAT-2018-24.pdf
Size:
638.9Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record