
Parameterized Orientable Deletion
Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2018), Parameterized Orientable Deletion, in Eppstein, David, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik : Wadern, p. 24:1-24:13
View/ Open
Type
Communication / ConférenceDate
2018Conference title
SWAT 2018Conference date
2018-06Conference city
MalmöConference country
SwedenBook title
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)Book author
Eppstein, DavidPublisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Published in
Wadern
Pages
24:1-24:13
Metadata
Show full item recordAuthor(s)
Hanaka, Tesshuautre
Katsikarelis, Ioannis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Otachi, Yota
Kumamoto Gakuen University
Sikora, Florian

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
A 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.Subjects / Keywords
Graph orientations; FPT algorithms; Treewidth; SETHRelated items
Showing items related by title and author.
-
Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2020) Article accepté pour publication ou publié
-
Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
-
Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Article accepté pour publication ou publié
-
Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
-
Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2020) Article accepté pour publication ou publié