Degreewidth: A New Parameter for Solving Problems on Tournaments - Université de technologie de Compiègne Access content directly
Conference Papers Year : 2023

Degreewidth: A New Parameter for Solving Problems on Tournaments

Lucas Isenmann
  • Function : Author
  • PersonId : 1289251
Sanjukta Roy
  • Function : Author
  • PersonId : 1289252
Jocelyn Thiebaut
  • Function : Author
  • PersonId : 1289253

Abstract

In the paper, we define a new parameter for tournaments called degreewidth which can be seen as a measure of how far is the tournament from being acyclic. The degreewidth of a tournament T denoted by ∆(T) is the minimum value k for which we can find an ordering ⟨v1,. .. , vn⟩ of the vertices of T such that every vertex is incident to at most k backward arcs (i.e. an arc (vi, vj) such that j < i). Thus, a tournament is acyclic if and only if its degreewidth is zero. Additionally, the class of sparse tournaments defined by Bessy et al. [ESA 2017] is exactly the class of tournaments with degreewidth one. We study computational complexity of finding degreewidth. We show it is NP-hard and complement this result with a 3-approximation algorithm. We provide a O(n 3)-time algorithm to decide if a tournament is sparse, where n is its number of vertices. Finally, we study classical graph problems Dominating Set and Feedback Vertex Set parameterized by degreewidth. We show the former is fixed-parameter tractable whereas the latter is NP-hard even on sparse tournaments. Additionally, we show polynomial time algorithm for Feedback Arc Set on sparse tournaments.
Fichier principal
Vignette du fichier
main.pdf (565.63 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04224722 , version 1 (02-10-2023)
hal-04224722 , version 2 (04-10-2023)

Identifiers

Cite

Tom Davot, Lucas Isenmann, Sanjukta Roy, Jocelyn Thiebaut. Degreewidth: A New Parameter for Solving Problems on Tournaments. 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023), Jun 2023, Fribourg (CH), Switzerland. pp.246-260, ⟨10.1007/978-3-031-43380-1_18⟩. ⟨hal-04224722v2⟩
18 View
6 Download

Altmetric

Share

Gmail Facebook X LinkedIn More