• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
LIPIcs-SWAT-2018-24.pdf (638.9Kb)
Type
Communication / Conférence
Date
2018
Conference title
SWAT 2018
Conference date
2018-06
Conference city
Malmö
Conference country
Sweden
Book title
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Book author
Eppstein, David
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Published in
Wadern
Pages
24:1-24:13
Metadata
Show full item record
Author(s)
Hanaka, Tesshu
autre
Katsikarelis, Ioannis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Otachi, Yota
Kumamoto Gakuen University
Sikora, Florian cc
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; SETH

Related items

Showing items related by title and author.

  • Thumbnail
    Parameterized Orientable Deletion 
    Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2020) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized Complexity of Safe Set 
    Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
  • Thumbnail
    Parameterized Complexity of Safe Set 
    Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Article accepté pour publication ou publié
  • Thumbnail
    Independent Set Reconfiguration Parameterized by Modular-Width 
    Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
  • Thumbnail
    Independent Set Reconfiguration Parameterized by Modular-Width 
    Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2020) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo