BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Julien Baste

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDiscrete Mathematicsmath.COComputational ComplexitySocial and Information Networks

Catalog footprint

Research overview

8works
5topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

8 publications

preprint2022arXiv

Contraction Bidimensionality of Geometric Intersection Graphs

Given a graph GG, we define bcg(G){\bf bcg}(G) as the minimum kk for which GG can be contracted to the uniformly triangulated grid ΓkΓ_{k}. A graph class G{\cal G} has the SQGC{\bf C} property if every graph G∈GG\in{\cal G} has treewidth O(bcg(G)c)\mathcal{O}({\bf bcg}(G)^{c}) for some 1≤c<21\leq c<2. The SQGC{\bf C} property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQGC{\bf C} property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.

Open access
preprint2021arXiv

A Neighborhood-preserving Graph Summarization

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 graph. Our main aim is to simplify large graphs so that they can be analyzed and processed effectively while preserving as many of the node neighborhood properties as possible. Since many graph algorithms are based on the neighborhood information available for each node, the idea is to produce a smaller graph which can be used to allow these algorithms to handle large graphs and run faster while providing good approximations. Moreover, our compression allows users to control the size of the compressed graph by adjusting the amount of information loss that can be tolerated. The experiments conducted on various real and synthetic graphs show that our compression reduces considerably the size of the graphs. Moreover, we conducted several experiments on the obtained summaries using various graph algorithms and applications, such as node embedding, graph classification and shortest path approximations. The obtained results show interesting trade-offs between the algorithms runtime speed-up and the precision loss.

Open access
preprint2016arXiv

Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees

In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species XX; these relationships are often depicted via a phylogenetic tree -- a tree having its leaves univocally labeled by elements of XX and without degree-2 nodes -- called the "species tree". One common approach for reconstructing a species tree consists in first constructing several phylogenetic trees from primary data (e.g. DNA sequences originating from some species in XX), and then constructing a single phylogenetic tree maximizing the "concordance" with the input trees. The so-obtained tree is our estimation of the species tree and, when the input trees are defined on overlapping -- but not identical -- sets of labels, is called "supertree". In this paper, we focus on two problems that are central when combining phylogenetic trees into a supertree: the compatibility and the strict compatibility problems for unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of "containing as a minor" and "containing as a topological minor" in the graph community. Both problems are known to be fixed-parameter tractable in the number of input trees kk, by using their expressibility in Monadic Second Order Logic and a reduction to graphs of bounded treewidth. Motivated by the fact that the dependency on kk of these algorithms is prohibitively large, we give the first explicit dynamic programming algorithms for solving these problems, both running in time 2O(k2)⋅n2^{O(k^2)} \cdot n, where nn is the total size of the input.

Open access
preprint2016arXiv

Parameterized complexity dichotomy for (r,ℓ)(r,\ell)-Vertex Deletion

For two integers r,ℓ≥0r, \ell \geq 0, a graph G=(V,E)G = (V, E) is an (r,ℓ)(r,\ell)-graph if VV can be partitioned into rr independent sets and ℓ\ell cliques. In the parameterized (r,ℓ)(r,\ell)-Vertex Deletion problem, given a graph GG and an integer kk, one has to decide whether at most kk vertices can be removed from GG to obtain an (r,ℓ)(r,\ell)-graph. This problem is NP-hard if r+ℓ≥1r+\ell \geq 1 and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of (r,ℓ)(r,\ell)-Vertex Deletion was known for all values of (r,ℓ)(r,\ell) except for (2,1)(2,1), (1,2)(1,2), and (2,2)(2,2). We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of kk. We consider as well the version of (r,ℓ)(r,\ell)-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem.

Open access
preprint2016arXiv

The number of labeled graphs of bounded treewidth

We focus on counting the number of labeled graphs on nn vertices and treewidth at most kk (or equivalently, the number of labeled partial kk-trees), which we denote by Tn,kT_{n,k}. So far, only the particular cases Tn,1T_{n,1} and Tn,2T_{n,2} had been studied. We show that (c⋅k⋅2k⋅nlog⁡k)n⋅2−k(k+3)2⋅k−2k−2 ≤ Tn,k ≤ (k⋅2k⋅n)n⋅2−k(k+1)2⋅k−k, \left(c \cdot \frac{k\cdot 2^k \cdot n}{\log k} \right)^n \cdot 2^{-\frac{k(k+3)}{2}} \cdot k^{-2k-2}\ \leq\ T_{n,k}\ \leq\ \left(k \cdot 2^k \cdot n\right)^n \cdot 2^{-\frac{k(k+1)}{2}} \cdot k^{-k}, for k>1k > 1 and some explicit absolute constant c>0c > 0. The upper bound is an immediate consequence of the well-known number of labeled kk-trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most kk.

Open access
preprint2016arXiv

Uniquely restricted matchings and edge colorings

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 a number of articles. Our contribution is twofold. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs. In particular, we achieve a ratio of 9/59/5 for subcubic bipartite graphs, improving over a 22-approximation algorithm proposed by Mishra. Furthermore, we study the uniquely restricted chromatic index of a graph, defined as the minimum number of uniquely restricted matchings into which its edge set can be partitioned. We provide tight upper bounds in terms of the maximum degree and characterize all extremal graphs. Our constructive proofs yield efficient algorithms to determine the corresponding edge colorings.

Open access
preprint2013arXiv

The role of planarity in connectivity problems parameterized by treewidth

For some years it was believed that for "connectivity" problems such as Hamiltonian Cycle, algorithms running in time 2^{O(tw)}n^{O(1)} -called single-exponential- existed only on planar and other sparse graph classes, where tw stands for the treewidth of the n-vertex input graph. This was recently disproved by Cygan et al. [FOCS 2011], Bodlaender et al. [ICALP 2013], and Fomin et al. [SODA 2014], who provided single-exponential algorithms on general graphs for essentially all connectivity problems that were known to be solvable in single-exponential time on sparse graphs. In this article we further investigate the role of planarity in connectivity problems parameterized by treewidth, and convey that several problems can indeed be distinguished according to their behavior on planar graphs. Known results from the literature imply that there exist problems, like Cycle Packing, that cannot be solved in time 2^{o(tw logtw)}n^{O(1)} on general graphs but that can be solved in time 2^{O(tw)}n^{O(1)} when restricted to planar graphs. Our main contribution is to show that there exist problems that can be solved in time 2^{O(tw logtw)}n^{O(1)} on general graphs but that cannot be solved in time 2^{o(tw logtw)}n^{O(1)} even when restricted to planar graphs. Furthermore, we prove that Planar Cycle Packing and Planar Disjoint Paths cannot be solved in time 2^{o(tw)}n^{O(1)}. The mentioned negative results hold unless the ETH fails. We feel that our results constitute a first step in a subject that can be further exploited.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.