29 citations · 48 across the 20 of their papers we have counts for
28 papers
Zero Forcing Sets in Temporal Graphs
Julien Baste, Simon Dreyer, Clara Marcille +2
The Zero Forcing (or corruption) of a graph is the problem of finding a minimum-size ``corrupting'' set. It corresponds to a subset of its vertices that can corrupt the whole graph…
On the diversity problems parameterized by the size of the solutions
Julien Baste, Cléophée Robin, Marie-Emilie Voge
Diversity optimization seeks multiple high-quality solutions that are sufficiently different from one another, providing a richer representation of the solution space than a single…
A polynomial bound on the pathwidth of graphs edge-coverable by shortest paths
Julien Baste, Lucas De Meyer, Ugo Giocanti +2
Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by shortest paths has pathwidth at most . In this paper, we improve…
The Leafed Induced Subtree in chordal and bounded treewidth graphs
Julien Baste
In the Fully Leafed Induced Subtrees, one is given a graph and two integers and and the question is to find an induced subtree of with vertices and at least …
Contraction Bidimensionality of Geometric Intersection Graphs
Julien Baste, Dimitrios M. Thilikos
Given a graph , we define as the minimum for which can be contracted to the uniformly triangulated grid . A graph class has the SQG${\bf…
Hitting minors on bounded treewidth graphs. III. Lower bounds
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos
For a finite collection of graphs , the -M-DELETION problem consists in, given a graph and an integer , decide whether there exists wi…
Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos
For a finite collection of graphs , the -M-DELETION (resp. -TM-DELETION) problem consists in, given a graph and an integer , decide whether the…
A Neighborhood-preserving Graph Summarization
Abd Errahmane Kiouche, Julien Baste, Mohammed Haddad +1
We introduce in this paper a new summarization method for large graphs. Our summarization approach retains only a user-specified proportion of the neighbors of each node in the gra…
Non-monotone target sets for threshold values restricted to , , and the vertex degree
Julien Baste, Stefan Ehard, Dieter Rautenbach
We consider a non-monotone activation process on a graph , where , for ever…
Acyclic matchings in graphs of bounded maximum degree
Julien Baste, Maximilian Fürst, Dieter Rautenbach
A matching in a graph is acyclic if the subgraph of induced by the set of vertices that are incident to an edge in is a forest. We prove that every graph with v…
FPT Algorithms for Diverse Collections of Hitting Sets
Julien Baste, Lars Jaffke, Tomáš Masařík +2
In this work, we study the -Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of solutions of size at most each, which has…
Domination versus edge domination
Julien Baste, Maximilian Fürst, Michael A. Henning +2
We propose the conjecture that the domination number of a -regular graph with is always at most its edge domination number , which coincides with th…
Hitting minors on bounded treewidth graphs. IV. An optimal algorithm
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos
For a fixed finite collection of graphs , the -M-DELETION problem asks, given an -vertex input graph for the minimum number of vertices that intersect a…
Bounding and approximating minimum maximal matchings in regular graphs
Julien Baste, Maximilian Fürst, Michael A. Henning +2
The edge domination number of a graph is the minimum size of a maximal matching in . It is well known that this parameter is computationally very hard, and several…
Composing dynamic programming tree-decomposition-based algorithms
Julien Baste
Given two integers and as well as graph classes , the problems $\mathsf{GraphPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell,…
Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
Julien Baste, Michael R. Fellows, Lars Jaffke +4
When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instanc…
Linear programming based approximation for unweighted induced matchings --- breaking the barrier
Julien Baste, Maximilian Fürst, Dieter Rautenbach
A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (Approximating weighted induc…
Temporal Matching
Julien Baste, Binh-Minh Bui-Xuan, Antoine Roux
A link stream is a sequence of pairs of the form , where represents a time instant and . Given an integer , the -edge between vertices $…
Minimum Reload Cost Graph Factors
Julien Baste, Didem Gözüpek, Mordechai Shalom +1
The concept of Reload cost in a graph refers to the cost that occurs while traversing a vertex via two of its incident edges. This cost is uniquely determined by the colors of the…
Parameterized complexity of finding a spanning tree with minimum reload cost diameter
Julien Baste, Didem Gözüpek, Christophe Paul +3
We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirect…
Hitting minors on bounded treewidth graphs. I. General upper bounds
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos
For a finite collection of graphs , the -M-DELETION problem consists in, given a graph and an integer , deciding whether there exists …
Ruling out FPT algorithms for Weighted Coloring on forests
Júlio Araújo, Julien Baste, Ignasi Sau
Given a graph , a proper -coloring of is a partition of into stable sets . Given a weight function $w: V(G) \to \ma…
Degenerate Matchings and Edge Colorings
Julien Baste, Dieter Rautenbach
A matching in a graph is -degenerate if the subgraph of induced by the set of vertices incident with an edge in is -degenerate. Goddard, Hedetniemi, Hedetniem…
Uniquely restricted matchings and edge colorings
Julien Baste, Dieter Rautenbach, Ignasi Sau
A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein and studied in…