ICALP'25

Timothé Picavet (PhD student in the CombAlgo department, GO team) and his colleagues have a paper accepted at ICALP’25

ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS), on automata, languages and programming. It will take place this July in Aarhus (Denmark).

On this occasion, the paper by Pierre Aboulker, Édouard Bonnet, Timothé Picavet, and Nicolas Trotignon, entitled “Induced Disjoint Paths Without an Induced Minor”, has been selected.

What's it all about?
To connect two pairs of points without interference, the classic model consists in searching for two disjoint paths in the underlying graph. This historical problem is well understood. We are interested in a more recent variant (which is more generally part of approximate graph theory): an edge between the two paths creates interference, and we need to find two paths that are not only disjoint but also non-adjacent. We show that this problem is significantly more difficult than the community had hoped.

Read more about the article, here.  

Contacts