Julien Baste

Maître de conférences
(assistant professor)
in Université de Lille
email : julien.baste (at) univ-lille.fr

Teaching

at IUT A
Office: ESPRIT 3.47
Tel: +33 3 59 63 22 48

Research

in the ORKAD research team
at CRIStAL
Office: S3.05
Tel: +33 3 28 77 85 78

Since September 2020, I am "Maître de conférences" (assistant professor) at Université de Lille in Lille, France. I am teaching computer science at IUT A. I do my research as a member of the ORKAD research team in CRIStAL.

My research interests are: Algorithms, reductions, graph theory, parameterized complexity, treewidth, matchings, multi-objective combinatorial optimization

Publications

Acyclic matchings in graphs of bounded maximum degree
Julien Baste, Maximilian Fürst, and Dieter Rautenbach.
- arXiv version.
- Short version in Proceedings of the 26th International Computing and Combinatorics Conference (COCOON), LNCS 12273: 542-553, 2020.
- Full version submitted.
FPT Algorithms for Diverse Collections of Hitting Sets
Julien Baste, Lars Jaffke, Tomas Masarik, Geevarghese Philip, and Günter Rote.
- arXiv version.
- Full version in Algorithms, 12(12): 254, 2019.
A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.
- arXiv version.
- Short version in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), 951-970, 2020.
Domination versus edge domination
Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr, and Dieter Rautenbach.
- arXiv version.
- Short version in Proceedings of 5th Bordeaux Graph Workshop (BGW), 42-44, 2019.
- Full version to appear in Discrete Applied Mathematics (DAM), 2020.
Bounding and approximating minimum maximal matchings in regular graphs
Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr, and Dieter Rautenbach.
- arXiv version.
- Short version in Proceedings of 5th Bordeaux Graph Workshop (BGW), 45-47, 2019.
- Full version submitted.
Composing dynamic programming tree-decomposition-based algorithms
Julien Baste.
- arXiv version.
Linear programming based approximation for unweighted induced matchings — breaking the ∆ barrier
Julien Baste, Maximilian Fürst, and Dieter Rautenbach.
- arXiv version.
- Short version in Proceedings of 5th Bordeaux Graph Workshop (BGW), 48-51, 2019.
- Full version in Discrete Optimization, 38: 100593, 2020.
Minimum Reload Cost Graph Factors
Julien Baste, Didem Gözüpek, Mordechai Shalom, and Dimitrios M. Thilikos.
- arXiv version.
- Short version in Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS 11376: 67-80, 2019.
- Full version to appear in Theory of Computing Systems (TOCS), 2020.
Diversity in Combinatorial Optimization
Julien Baste, Michael R. Fellows, Lars Jaffke, Tomas Masarik, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond.
- arXiv version.
- Short version (Part 1/2) in Proceedings of the VIII Latin American Workshop on Cliques in Graphs (LAWCG), 47-47, 2018.
- Short version (Part 2/2) to appear in the 29th International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Temporal matching in link stream: kernel and approximation
Julien Baste, Bình Minh Bùi Xuân, and Antoine Roux.
- arXiv version.
- Short version in Proceedings of the 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW), 163-166, 2018.
- Full version in Theoretical Computer Science (TCS), 806: 184-196, 2020.
Hitting (topological) minors on graphs of bounded treewidth
Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.
- arXiv version.
- Short version (Part 1/2) in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), LIPICS 89: 4:1-4:12, 2017.
- Short version (Part 2/2) in Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC), LIPICS 115: 2:1-2:13, 2018.
- Full version (Part 1/3) to appear in SIAM Journal on Discrete Mathematics, 2020.
- Full version (Part 2/3) in Theoretical Computer Science (TCS), 814: 135-152, 2020.
- Full version (Part 3/3) in Journal of Computer and System Sciences (JCSS), 109: 56-77, 2020.
Contraction-Bidimensionality of geometric intersection graphs
Julien Baste and Dimitrios M. Thilikos.
- Short version in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), LIPIcs 89: 5:1-5:13, 2017.
Parameterized complexity of finding a spanning tree with minimum reload cost diameter
Julien Baste, Didem Gözüpek, Christophe Paul, Ignasi Sau, Mordechai Shalom, and Dimitrios M. Thilikos.
- arXiv version.
- Short version in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), LIPIcs 89: 3:1-3:12, 2017.
- Full version in Networks (Networks), 75: 259-277, 2020.
Degenerate Matchings and Edge Colorings
Julien Baste and Dieter Rautenbach.
- arXiv version.
- Full version in Discrete Applied Mathematics (DAM), 239: 38-44, 2018.
Uniquely restricted matchings and edge colorings
Julien Baste, Dieter Rautenbach, and Ignasi Sau.
- arXiv version.
- Short version in Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), LNCS 10520: 100-112, 2017.
- Full version (Part 1/2) in Journal of Graph Theory (JGT), 91(3): 251-258, 2019.
- Full version (Part 2/2) in Discrete Applied Mathematics (DAM), 267: 30-40, 2019.
Ruling out FPT algorithms for Weighted Coloring on forests
Júlio Araújo, Julien Baste, and Ignasi Sau.
- arXiv version.
- Short version in Proceedings of the IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), EDM 62: 195-200, 2017.
- Full version in Theoretical Computer Science (TCS), 729: 11-19, 2018.
On the number of labeled graphs of bounded treewidth
Julien Baste, Marc Noy, and Ignasi Sau.
- arXiv version.
- Short version in Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), LNCS 10520: 88-99, 2017.
- Full version in European Journal of Combinatorics (EJC), 71: 12-21, 2018.
On the Parameterized Complexity of the Edge Monitoring problem
Julien Baste, Fairouz Beggas, Hamamache Kheddouci, and Ignasi Sau.
- Full version in Information Processing Letters (IPL), 121: 39-44, 2017.
Parameterized complexity dichotomy for (r,l)-Vertex Deletion
Julien Baste, Luerbio Faria, Sulamita Klein, and Ignasi Sau.
- arXiv version.
- Full version in Theory of Computing Systems (TOCS), 61(3): 777-794, 2017.
Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca.
- arXiv version.
- Short version in Proceedings of the 11th International Conference on Algorithmic Aspects of Information and Management (AAIM), LNCS 9778: 53-64, 2016.
- Full version in Bulletin of Mathematical Biology (BMAB), 79(4): 920-938, 2017.
The role of planarity in connectivity problems parameterized by treewidth
Julien Baste and Ignasi Sau.
- arXiv version.
- Short version in Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC), LNCS 8894: 63-74, 2014.
- Full version in Theoretical Computer Science (TCS), 570: 1-14, 2015.

Events

Event	Place	From	To
JGA2019	Bruxelles, Belgium	13/11/2019	15/11/2019
BGW2019	Bordeaux, France	28/10/2019	31/10/2019
FraNorAC2019	Montpellier, France	19/09/2019	20/09/2019
Research meeting	Montpellier, France	16/07/2019	18/07/2019
GCCR2019	Paris, France	09/09/2019	10/09/2019
Research meeting	Lyon, France	08/07/2019	12/07/2019
Seminar	Paris, France	22/03/2019	22/03/2019
Seminar	Evry, France	21/03/2019	21/03/2019
Seminar	Dijon, France	19/03/2019	19/03/2019
Research meeting	Grenoble, France	12/03/2019	15/03/2019
SOFSEM2019	Nový Smokovec, Slovakia	27/01/2019	30/01/2019
Research meeting	Lyon, France	21/01/2019	25/01/2019
Seminar	Bordeaux, France	11/01/2019	11/01/2019
Research meeting	Montpellier, France	08/01/2019	10/01/2019
Seminar	Marseille, France	07/01/2019	07/01/2019
40 Years of Graphs and Algorithms	Paris, France	11/10/2018	12/10/2018
Seminar	Marne-la-Vallée, France	09/10/2018	09/10/2018
ALGO2018	Helsinki, Finland	20/08/2018	24/08/2018
CTW2018	Paris, France	18/06/2018	20/06/2018
SGT2018	Sète, France	11/06/2018	15/06/2018
Research meeting	Budapest, Hungary	20/05/2018	02/06/2018
Research meeting	Bergen, Norway	18/03/2018	31/03/2018
Recent Advances in Parameterized Complexity	Tel Aviv, Israel	03/12/2017	07/12/2017
ALGO2017	Vienna, Austria	04/09/2017	08/09/2017
PCSS2017	Vienna, Austria	01/09/2017	03/09/2017
WG2017	Eindhoven, The Netherlands	21/06/2017	23/06/2017
Research meeting	Ulm, Germany	30/01/2017	03/02/2017
Research meeting	Fortaleza, Brazil	21/11/2016	09/12/2016
JGA2016	Paris, France	16/11/2016	18/11/2016
AAIM2016	Bergamo, Italy	18/07/2016	20/07/2016
Research meeting	Istanbul, Turkey	26/06/2016	01/07/2016
ÉPIT2016	Marseille, France	09/05/2016	13/05/2016
JGA2015	Orléans, France	04/11/2015	06/11/2015
GROW 2015	Aussois, France	11/10/2015	15/10/2015
Research meeting	Lyon, France	07/07/2015	09/07/2015
SGT2015	Porquerolles, France	18/05/2015	22/05/2015
Research meeting	Barcelona, Spain	02/05/2015	08/08/2015
15èmes JCALM	Sophia-Antipolis, France	10/03/2015	11/03/2015
International Workshop on Graph Decomposition	CIRM, Marseille, France	19/01/2015	23/01/2015
JGA 2014	Dijon, France	12/11/2014	14/11/2014
IPEC'14	Wroclaw, Poland	10/09/2014	12/09/2014

Teaching

Year	University	UE code	UE	level
2017/2018	Sorbonne Université	PSTL	Projet M1	M1	8H eq. TD
192H		4I506	Composants	M1	20H TP
		4I505	Conception et Pratique de l'Algorithmique	M1	40H TP, 2H cours
		3I008	Modèles de programmation et interopérabilité des langages	L3	18H TP
		4I900	Complexité, Algorithmes Randomisés et Approchés	M1	20H TP
		3I014	Réseaux	L3	38,5H TD
		2I0I1	Orientation et Insertion Professionnelle	L2	44H TD
2016/2017	Université de Montpellier	HLIN102	Du binaire au web	L1	24H TP, 15H TD
62H		HLSE305	C2I	APESS	18H TP
		HLIN101	Introduction à l'algorithmique et à la programmation	L1	4H TD
2015/2016	Université de Montpellier	HLIN102	Du binaire au web	L1	22H TP, 14H TD
69H		HLSE305	C2I	L2	33H TP
2014/2015	Université de Montpellier	HLIN202	Programmation avancée	L1	18H TP
69H		HLIN101	Introduction à l'algorithmique et à la programmation	L1	24H TP, 27H TD

Internships

Spring 2014 : Internship of five months in Prague in Tcheque Republic.
Autumn 2014 : Internship in bioinformatics in Rennes in France. Poster.
Spring 2013 : Internship of five months in AlGCo in Montpellier in France. Master thesis.
Spring 2012 : Internship of five months in Bergen in Norway. Internship report.

Training

2014-2017 : Ph.D Student in the AlGCo team at LIRMM in Montpellier in France.
                    The thesis, Treewidth: algorithmic, combinatorial, and practical aspects, [Manuscript] [Slides]
                    was supervised by Ignasi Sau, and Dimitrios Thilikos and
                    was reviewed by Petr Golovach, Marcin Pilipczuk, and Ioan Todinca.
                    The jury was chaired by Vincent Berry.
                    The thesis was defended on September, 22nd, 2017.
2012-2013 : Second year of the MRI Master at ENS Cachan Bretagne in Rennes.
2011-2012 : First year of the MPRI Master at ENS Cachan near Paris.
2010-2011 : Degree at ENS Cachan near Paris.
2008-2010 : Two years of training school at Lycée Saint Louis in Paris. Preparation of the ENS Cachan entrance exam.
2008 : Baccalaureate at Lycée Évariste Gallois in Sartrouville.