LIMOS

Tous les détails sont sur https://emploi.cnrs.fr/Offres/Doctorant/UMR6158-FLOFOU-001/Default.aspx

Un grand nombre de problèmes fondamentaux d’optimisation combinatoire sont NP-difficiles sur les graphes dirigés (digraphes). Cela inclut les problèmes du Directed Feedback Vertex/Arc Set [3,4], des chemins sommets/arcs disjoints [2], de  la couverture par chemins [1,2], et bien d’autres. Améliorer les algorithmes d’approximation ou paramétrés pour ces problèmes,  lorsque l’entrée peut être n’importe quel digraphe, constitue un problème bien connu et ouvert de longue date. Cela motive l’étude de ces problèmes sur des classes de digraphes structurés, où ils demeurent NP-difficiles, mais sont susceptibles d’admettre des algorithmes d’approximation et paramétrés non-triviaux, comme dans [1,2,3,4].
L’objectif de cette thèse de doctorat sera d’explorer le côté algorithmique des problèmes fondamentaux d’optimisation sur les digraphes. À cette fin, nous développerons de nouveaux algorithmes et des bornes inférieures pour ces problèmes sur différentes classes de digraphes structurés (tournois, digraphes semi-complets, digraphes planaires ou triangulés, etc). Nous nous concentrerons sur deux lignes de recherche :

1. Algorithmes d’approximation : l’objectif est de concevoir des algorithmes en temps polynomial pour produire des solutions d’approximation de facteur constant ou O(log n) pour des entrées de taille n.

2. Algorithmes paramétrés : l’objectif est de concevoir des algorithmes qui calculent une solution exacte de taille au plus k en temps f(k)poly(n), où f est une fonction à croissance (modérément) exponentielle de k et poly, un polynôme.

[1] M. Caceres, M. Cairo, B. Mumey, R. Rizzi, and A.I. Tomescu. Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pp. 359–376.
[2] H. Fernau, F. Foucaud, K. Mann, U. Padariya and R. Rao. Parameterizing path partitions. Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC 2023), Lecture Notes in Computer Science 13898:187-201, 2023.
[3] M. Kumar and D. Lokshtanov. Faster exact and parameterized algorithm for feedback vertex set in tournaments. Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016. LIPIcs 47, pp. 49:1–49:13, 2016.
[4] D. Lokshtanov, P. Misra, J. Mukherjee, F. Panolan, G. Philip and S. Saurabh. 2-approximating Feedback Vertex Set in tournaments. ACM Transactions on Algorithms17(2): 11:1-11:14, 2021.

Pour postuler à cette offre d’emploi veuillez visiter emploi.cnrs.fr.