Julien Baste

Julien Baste

orcid

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 February 2022 in Artificial Intelligence
Verified
Journal Article
Closed access
JBJulien Baste
Julien Baste
MFMichael R. Fellows
Michael R. Fellows
LJLars Jaffke
Lars Jaffke
TMTomáš Masařík
Tomáš Masařík
MOMateus de Oliveira Oliveira
Mateus de Oliveira Oliveira
Frances  RosamondFrances Rosamond
Frances Rosamond

27 November 2019 in Algorithms
Verified
Journal Article
Open access
PDF file
JBJulien Baste
Julien Baste
LJLars Jaffke
Lars Jaffke
TMTomáš Masařík
Tomáš Masařík
GPGeevarghese Philip
Geevarghese Philip
GRGünter Rote
Günter Rote
In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in k + r for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of ‘base’ solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest.

20 July 2023 in SIAM Journal on Computing
Verified
Journal Article
Closed access
JBJulien Baste
Julien Baste
ISIgnasi Sau
Ignasi Sau
DTDimitrios M. Thilikos
Dimitrios M. Thilikos
For a fixed finite collection of graphs [Formula: see text] the [Formula: see text]-M-Deletion problem is as follows: given an [Formula: see text]-vertex input graph [Formula: see text] find the minimum number of vertices that intersect all minor models in [Formula: see text] of the graphs in [Formula: see text]. by Courcelle’s Theorem, this problem can be solved in time [Formula: see text] where [Formula: see text] is the treewidth of [Formula: see text] for some function [Formula: see text] depending on [Formula: see text]. In a recent series of articles, we have initiated the program of optimizing asymptotically the function [Formula: see text]. Here we provide an algorithm showing that [Formula: see text] for every collection [Formula: see text]. Prior to this work, the best known function [Formula: see text] was double-exponential in [Formula: see text]. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [ Proc. of the 25 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802–1811] for the particular case [Formula: see text] and of Kociumaka and Pilipczuk [ Algorithmica, 81 (2019), pp. 3655–3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [ Inform. Comput., 256 (2017), pp. 62–82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections [Formula: see text] [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135–152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56–77], our algorithm yields the following complexity dichotomy when [Formula: see text] contains a single connected graph [Formula: see text] assuming the Exponential Time Hypothesis: [Formula: see text] if [Formula: see text] is a contraction of the chair or the banner , and [Formula: see text] otherwise.

1 August 2019 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
JBJulien Baste
Julien Baste
DRDieter Rautenbach
Dieter Rautenbach
ISIgnasi Sau
Ignasi Sau

21 November 2018 in Journal of Graph Theory
Verified
Journal Article
Closed access
PDF file
JBJulien Baste
Julien Baste
DRDieter Rautenbach
Dieter Rautenbach
ISIgnasi Sau
Ignasi Sau

24 January 2022 in Algorithmica
Verified
Journal Article
Closed access
PDF file
JBJulien Baste
Julien Baste
DTDimitrios M. Thilikos
Dimitrios M. Thilikos