Degreewidth : un nouveau paramètre pour résoudre les problèmes dans les tournois
Tom Davot  1@  , Lucas Isenmann  2  , Sanjukta Roy  3  , Jocelyn Thiebaut  3  
1 : Heudiasyc
Université de Technologie de Compiègne
2 : Université Paul-Valéry - Montpellier 3
Université Paul-Valéry - Montpellier 3
3 : Faculty of Technology, Czech Technical University Prague

Dans ce travail, nous introduisons un nouveau paramètre pour les tournois appelé degreewidth. Étant donné un ordre des sommets d'un tournoi, un arc (v_i,v_j) est un arc retour si v_j est avant v_i dans cet ordre. Le degreewidth d'un tournoi est le nombre minimum k tel qu'il existe un ordre des sommets tel que le nombre maximum d'arcs retours incident à un même sommet est k. Ce paramètre mesure à quel point le tournoi est proche d'être acyclique.

Nous avons d'abord étudié la complexité du calcul du degreewidth en montrant que c'était NP-difficile et nous avons complété ce résultat par une 3-approximation.

Nous avons également montré comment ce paramètre pouvait être utilisé pour résoudre des problèmes difficiles. Nous avons montré que Ensemble dominant était FPT quand paramétré par le degreewith et que Feedback Arc Set pouvait être résolu en temps polynomial si le degreewidth est égal à 1. À contrario, Feedback Vertex Set reste NP-difficile même si le degreewidth est égal à 1.


Personnes connectées : 1 Vie privée
Chargement...