BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Google Inc//Google Calendar 70.9054//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
DESCRIPTION:Algorithmique distribuée et graphes seminar of IRIF
NAME:Algorithmique distribuée et graphes
REFRESH-INTERVAL:PT4H
TIMEZONE-ID:Europe/Paris
X-WR-CALDESC:Algorithmique distribuée et graphes seminar of IRIF
X-WR-CALNAME:Algorithmique distribuée et graphes
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:Autour de la connexité dans les graphes avec conflits - Benjmain
Momege
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160329T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160329T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:21
DESCRIPTION:Nous nous intéresserons aux graphes avec conflits (un conflit
est une paire d'arêtes ne pouvant pas simultanément faire partie d'un s
ous-graphe)\, dans lesquels nous étudierons différents types de problèm
es\, de nature aussi bien algorithmique que combinatoire\, notre ligne dir
ectrice étant la notion de connectivité. Nous verrons que plusieurs rés
ultats\, simples sans conflit\, ne le sont plus lors de l'ajout de conflit
s. Nous présenterons : des algorithmes exacts (non polynomiaux)\, des ré
sultats de NP-complétude\, et des conditions suffisantes assurant l'exist
ence de certains objets (arbre couvrant\, chemin et cycle Hamiltonien) san
s conflits.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:TBA - Eujung Kim
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160524T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160524T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:22
DESCRIPTION:
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Folding Turing is hard but feasible - Nicolas Schabanel
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160412T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160412T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:23
DESCRIPTION:Nicolas Schabanel\, joint work with Cody Geary (Caltech)\, Pie
rre-Étienne Meunier (U. Aalto)\, et Shinnosuke Seki (U. Electro-Communica
tions\, Tokyo).\n\nWe introduce and study the computational power of Orita
tami\, a theoretical model to explore greedy molecular folding\, by which
the molecule begins to fold before waiting the end of its production. This
model is inspired by our recent experimental work demonstrating the const
ruction of shapes at the nanoscale by folding an RNA molecule during its t
ranscription from an engineered sequence of synthetic DNA. While predictin
g the most likely conformation is known to be NP-complete in other models\
, Oritatami sequences fold optimally in linear time. Although our model us
es only a small subset of the mechanisms known to be involved in molecular
folding\, we show that it is capable of efficient universal computation\,
implying that any extension of this model will have this property as well
.\n\nWe introduce general design techniques for programming these molecule
s. Our main result in this direction is an algorithm in time linear in the
sequence length\, that finds a rule for folding the sequence deterministi
cally into a prescribed set of shapes depending of its environment. This s
hows the corresponding problem is fixed-parameter tractable although we pr
oved it is NP-complete in the number of possible environments. This algori
thm was used effectively to design several key steps of our constructions.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Similarity-First Search: a new algorithm with application to Robin
sonian matrix recognition - Matteo Seminaroti
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160405T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160405T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:35
DESCRIPTION:We present a new efficient combinatorial algorithm for recogni
zing if a given symmetric matrix is Robinsonian\, i.e.\, if its rows and c
olumns can be simultaneously reordered so that entries are monotone nondec
reasing in rows and columns when moving toward the diagonal. As main ingre
dient we introduce a new algorithm\, named Similarity-First-Search (SFS)\,
which extends Lexicographic Breadth-First Search (Lex-BFS) to weighted gr
aphs and which we use in a multisweep algorithm to recognize Robinsonian m
atrices. Since Robinsonian binary matrices correspond to unit interval gra
phs\, our algorithm can be seen as a generalization to weighted graphs of
the 3-sweep Lex-BFS algorithm of Corneil for recognizing unit interval gra
phs. This new recognition algorithm is extremely simple and\, for an n×n
nonnegative matrix with m nonzero entries\, it terminates in n−1 SFS swe
eps\, with overall running time O(n^2+nmlogn).
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Variants of Hadwiger's conjecture - Sang-il Oum\, KAIST
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160119T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160119T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:36
DESCRIPTION:Hadwiger conjectured that every graph with no K_t minor is (t-
1)-colorable\; in other words\, every graph with no K_t minor admits a par
tition of its vertex set into t-1 independent sets. This conjecture is sti
ll widely open and if true\, it implies the four color theorem. Gerards an
d Seymour made a stronger conjecture claiming that every graph with no K_t
odd minor is (t-1)- colorable\, commonly called the odd Hadwiger's conjec
ture. We prove variants of Hadwiger's conjecture. First\, we prove that ev
ery graph with no K_t minor admits a partition of its vertex set into t-1
sets\, each inducing a subgraph of bounded maximum degree. Secondly\, we p
rove that every graph with no K_t minor admits a partition of its vertex s
et into 3(t-1) sets\, each inducing a subgraph having no large components.
\n\nWe also prove variants of the odd Hadwiger's conjecture as follows: Ev
ery graph with no odd K_t minor admits a partition of its vertex set into
7t-10 sets\, each inducing a subgraph of bounded maximum degree. As a coro
llary\, we prove that every graph with no odd K_t minor admits a partition
of its vertex set into 16t-19 sets\, each inducing a subgraph with no lar
ge components. The last result improves the result of Kawarabayashi\, who
showed it with 496t sets.\n\nThis talk is a combination of three works\; f
irst with K. Edwards\, D. Kang\, J. Kim\, and P. Seymour\, second with C.
Liu\, and third with D. Kang.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Roots of the chromatic polynomial\, spanning trees and minors - Th
omas Perrett\, Technical University of Denmark
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160209T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160209T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:37
DESCRIPTION:The real and complex roots of chromatic polynomials\, which we
call chromatic roots\, have been studied since the 1940s yet it is not we
ll understood how structural properties of graphs affect their chromatic r
oots. In this talk we survey some results and open problems\, and present
recent work on the following question: For a minor- closed class of graphs
\, what is the infimum of the non-trivial real chromatic roots of the grap
hs in that class?
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:New proof of Seymour's 6-flow theorem - Edita Rollova\, University
of West Bohemia\, Pilsen\, Czech republic
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160517T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160517T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:51
DESCRIPTION:We will provide (two) new proof(s) of Seymour's 6-flow\ntheore
m (both) using induction.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tree-Like Structures in Graphs: A Metric Point of View - Feodor Dr
agan\, Kent State University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160609T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160609T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:68
DESCRIPTION:Recent empirical and theoretical work has suggested that many
real-life complex networks and graphs arising in Internet applications\, i
n biological and social sciences\, in chemistry and physics have tree-like
structures from a metric point of view. A number of graph parameters tryi
ng to capture this phenomenon and to measure these tree-like structures we
re proposed\; most notable ones being the tree-stretch\, tree-distortion\,
tree-length\, tree-breadth\, Gromov’s hyperbolicity of a graph\, and cl
uster-diameter and cluster-radius in a layering partition of a graph. If s
uch a parameter is bounded by a constant on graphs then many optimization
problems can be efficiently solved or approximated for such graphs. We dis
cuss these parameters and recently established relationships between them
for unweighted and undirected graphs\; it turns out that all these paramet
ers are at most constant or logarithmic factors apart from each other. We
give inequalities describing their relationships and discuss consequences
for some optimization problems.
LOCATION:Salle 2015
END:VEVENT
BEGIN:VEVENT
SUMMARY:Locating any two vertices on Hamiltonian cycles - Qiang Sun\, LRI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160621T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160621T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:88
DESCRIPTION:We give a proof of Enomoto's conjecture for graphs of sufficie
ntly large order.\nEnomoto's conjecture states that: if G is a graph of or
der n with minimum degree at least n/2+ 1\,\nthen for any pair x\,y of ver
tices of G\, there is a Hamiltonian cycle C of G such that\nthe distance b
etween x and y in C is n/2.\n\nThe main tools of our proof are Regularity
Lemma of Szemeredi and Blow-up Lemma of Koml os et al..\n\nThis is a joint
work with Weihua He and Hao Li.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Space-Optimal Counting in Population Protocols - Janna Burman\, LR
I - Université Paris Sud
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160628T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160628T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:89
DESCRIPTION:We study the fundamental problem of counting\,\nwhich consists
in computing the size of a system. The considered model\nare population p
rotocols\, which is the model of finite state\, anonymous and asynchronous
\nmobile devices (agents) communicating in pairs (according to a fairness
condition).\nWe significantly improve the previous results known for count
ing in this model\,\nin terms of (exact) space complexity. Specifically\,
we give the first space optimal\nprotocols solving the problem for two cla
ssical types of fairness\,\nglobal and weak. Both protocols require no ini
tialization of the counted\nagents.\nThe protocol designed for global fair
ness\, surprisingly\, uses only one\nbit of memory (two states) per counte
d agent. The protocol\, functioning\nunder weak fairness\, requires the ne
cessary log P bits (P states\, per\ncounted agent) to be able to count up
to P agents. Interestingly\, this protocol\nexploits the intriguing Gros s
equence of natural numbers\, which is\nalso used in the solutions to the C
hinese Rings and the Hanoi Towers\npuzzles.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Role of Mantras in (Distributed-Computing) Research - Eli Gafn
i\, UCLA
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160707T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160707T110000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:92
DESCRIPTION:A Research-Mantra is something "cosmic" one believes holds in
the area of research at hand.\nIt is then a "pillar of fire" in front that
leads the way. The Mantra is to be followed as long as it is not refuted
by facts.\\\\\nIn this talk I'll present some Mantras I followed during th
e years starting with one that says that Distributed-Computing Theory (DCT
) is \nthe Mathematical Study of Interleaving. Consequently\, DCT research
ers should have Mathematical\nsensibilities rather than Engineering ones.
Thus\, DCT should poses the beauty\nof Mathematics\, and should not be be
"hacked" as an Engineering Domain.\nIn particular any paper that points to
"anomalies" or "paradoxes" does not point to faults in the domain\nbut to
faults in the thinking of the authors.\nI'll show some Mantras I use and
where they led\, and\nI'll end up with the ramification of recent Mantra t
hat holds that deterministic state-machines capture interleaving\nas well
as message-passing interleaving.
LOCATION:Salle 1016
END:VEVENT
BEGIN:VEVENT
SUMMARY:Algorithms for computing the rank of divisors on some classes of g
raphs. - Ha Duong Phan\, Institute of Mathematics\, VAST\, Vietnam.
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160927T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160927T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:107
DESCRIPTION:The notion of rank of divisor on graph was introduced by Baker
and Norine in 2007 in showing the link with the similar notion on Riemann
surface. Moreover\, the authors have developed a theorem for divisors on
graph analogue to the classical Riemann-Roch theorem. Since then\, many wo
rks have studied for computing the rank of divisors on graph. A very impor
tant is the new theorem on the NP-hardness complexity of the Problem of c
omputing the rank of divisor on general graph. The proof of this result wa
s based on the proof of the NP-hardness of the Problem of finding the mini
mum recurrent configurations of Chip Firing Game on directed graphs (by Pe
rrot and Pham). In this talk\, we will present some (linear) algorithms fo
r computing the rank of divisors on some classes of graphs.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Self-stabilizing Metric Graphs - Jonas Lefevre\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161025T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161025T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:134
DESCRIPTION:Je présenterai un algorithme autostabilisant pour réseaux ov
erlay construisant le graphe d'une métrique donnée par oracle. L'algorit
hme fonctionne sous les daemons synchrones et asynchrones. Sous daemon syn
chrone le temps de convergence est linéaire. Dans tout les cas\, la compl
exité en messages et celle en mémoire sont aussi faibles que possible.
Cette construction peut être utilisée pour construire pour de la constru
ction d'un graphe arbitraire.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cocomparability graphs and greedy algorithms - Michel Habib\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161129T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161129T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:147
DESCRIPTION:Joint work with Derek Corneil\, Jérémie Dusart and Ekkehard
Kh\\"oler\n\nA cocomparability graph is a graph whose complement admits a
transitive orientation. An interval graph is the intersection graph of a f
amily of intervals on the real line. In this paper we investigate the rela
tionships between interval and cocomparability graphs. I will first presen
t some recent algorithms we obtained on cocomparability graphs. They show
that for some problems\, the algorithm used on interval graphs can also
be used with small modifications on cocomparability graphs. Many of these
algorithms are based on graph searches that preserve cocomparability order
ings. \n\nThen I will propose a characterization of cocomparability graph
s via a lattice structure on the set of their maximal cliques. Using this
characterization we can prove that every maximal interval subgraph of a c
ocomparability graph $G$ is also a maximal chordal subgraph of $G$.\n\nTh
is characterization also has interesting algorithmic consequences and we s
how that a new graph search\, namely Local Maximal Neighborhood Search (
LocalMNS) leads to an $O(n+mlogn)$ time algorithm to find a maximal interv
al subgraph of a cocomparability graph. Similarly I propose a linear time
algorithm to compute all simplicial vertices in a cocomparability graph. I
n both cases we improve on the current state of knowledge.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Problems and Results in Kempe Equivalence of Colorings - Carl Fegh
ali\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170110T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170110T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:148
DESCRIPTION:Given a graph G with a coloring\, a Kempe chain of G is a maxi
mal connected subgraph of G in which each vertex has one of two colors. A
Kempe change is the operation of swapping the colors of a Kempe chain. Two
colorings are Kempe equivalent if one can be obtained from the other by a
sequence of Kempe changes. In this talk\, we survey some of the existing
results\, open problems and common proof techniques in this area.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Graph Reconstruction and Verification - Hang Zhou\, Max Planck Ins
titute for Informatics
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161213T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161213T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:166
DESCRIPTION:How efficiently can we find an unknown graph using shortest pa
th queries between its vertices? This is a natural theoretical question fr
om the standpoint of recovery of hidden information. This question is rela
ted to discovering the topology of Internet networks\, which is a crucial
step for building accurate network models and designing efficient algorith
ms for Internet applications. \n\nIn this talk\, I will introduce the prob
lems of graph reconstruction and verification via oracles. I will investig
ate randomized algorithms based on a Voronoi cell decomposition. I will al
so analyze greedy algorithms\, and prove that they are near-optimal. \n\nT
he talk is based on joint work with Claire Mathieu and Sampath Kannan.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Towards real-world graph algorithmics - Maximilien Danisch\, Telec
om Paris Tech
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170124T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170124T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:168
DESCRIPTION:Real-world graphs (a.k.a. complex networks) are ubiquitous: th
e web\, Facebook\, Twitter\, brain networks\, protein interaction networks
\, etc. Studying these graphs and solving computational problems on them (
say maximum clique\, partitioning or dense subgraph) has applications in m
any fields.\nI will first show that the structure of some real-world graph
s is special. In particular\, they are not adversarial and some difficult
problems (say NP-complete or NP-hard problems) can be solved on some huge
real-world graphs (say 2G edges or more).\nI will then present two works a
long the lines of "understanding and leveraging the structure of real-worl
d graphs in order to build better algorithms": (i) Enumerating all k-cliqu
es and (ii) Computing the density-friendly graph decomposition.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Reed's conjecture and strong edge coloring - Marthe Bonamy\, Labri
- CNRS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170103T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170103T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:178
DESCRIPTION:The chromatic number of a graph is trivially bounded from abov
e by the maximum degree plus one\, and from below by the size of a largest
clique. Reed proved in 1998 that compared to the trivial upper bound\, we
can always save a number of colors proportional to the gap between the ma
ximum degree and the size of a largest clique. A key step in the proof dea
ls with how to spare colors in a graph whose every vertex "sees few edges"
in its neighborhood. We improve the existing approach\, and discuss its a
pplications to Reed's theorem and strong edge coloring. \n\nThis is joint
work with Thomas Perrett (Technical University of Denmark) and Luke Postle
(University of Waterloo).
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Beyond Highway Dimension: Small Distance Labels Using Tree Skeleto
ns - Laurent Viennot\, INRIA - IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170228T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170228T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:183
DESCRIPTION:Joint work with Adrian Kosowski\n\nThe goal of a hub-based dis
tance labeling scheme for a network $G = (V\, E)$ is to assign a small sub
set $S(u) \\subseteq V$ to each node $u \\in V$\, in such a way that for a
ny pair of nodes $u\, v$\, the intersection of hub sets $S(u) \\cap S(v)$
contains a node on the shortest $uv$-path. The existence of small hub sets
\, and consequently efficient shortest path processing algorithms\, for ro
ad networks is an empirical observation. A theoretical explanation for thi
s phenomenon was proposed by Abraham et al. (SODA 2010) through a network
parameter they called highway dimension\, which captures the size of a hit
ting set for a collection of shortest paths of length at least $r$ interse
cting a given ball of radius $2r$. In this talk\, we revisit this explanat
ion\, introducing a more tractable (and directly comparable) parameter bas
ed solely on the structure of shortest-path spanning trees\, which we call
skeleton dimension. We show that skeleton dimension admits an intuitive d
efinition for both directed and undirected graphs\, provides a way of comp
uting labels more efficiently than by using highway dimension\, and leads
to comparable or stronger theoretical bounds on hub set size.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fine-grained complexity of coloring geometric intersection graphs.
- Edouard Bonnet\, Middlesex University\, London
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170207T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170207T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:189
DESCRIPTION:We are interested in the following problem: Given a collection
of n objects in the plane and an integer k\,\nis there a proper k-colorin
g of its intersection graph (i.e.\, such that two overlapping objects get
different colors).\nHere we think of k as a function of n\; it can be cons
tant\, linear\, or anything in between.\nFrom an application of a known se
parator theorem\, if the input objects are fat (i.e.\, have bounded diamet
er/width ratio)\,\nthen this problem can be solved in time 2^{O(\\sqrt{n k
} \\log n)}.\nWe will show that this running time is essentially optimal u
nder the Exponential Time Hypothesis (ETH).\nWe then move to intersection
graphs of segments (which are quintessentially non fat) and show that the
situation is quite \ndifferent than with fat objects. \nWe end on a surpri
sing note: 3-coloring and 4+-coloring of segments have significantly diffe
rent behaviors.\n\nThe guideline and motivation of the talk is to go beyon
d the NP-hardness of coloring those geometric graphs\, \nand precise what
is the best (hopefully subexponential) running time that we can get.\n\nTh
is is based on a joint work with Csaba Biró\, Dániel Marx\, Tillmann Mil
tzow\, and Paweł Rzążewski\, and an ongoing project with Stéphan Thoma
ssé and a subset of the aforementioned authors.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Linear search by a pair of distinct-speed robots - Evangelos Bampa
s\, LIF - Université Aix Marseille
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170321T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170321T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:206
DESCRIPTION:We will present algorithms for the evacuation problem by a pai
r of distinct-speed robots on an infinite line. In this problem\, two mobi
le robots with different maximal speeds are initially placed at the same p
oint on an infinite line. The robots need to find a stationary target (i.e
.\, the exit)\, which is placed at an unknown location on the line. The se
arch is completed when both robots arrive at the exit and the goal is to c
onclude evacuation in as little time as possible. The robot that discovers
the exit first may communicate it to the other robot. We consider two mod
els of communication between the robots\, namely wireless communication an
d face-to-face communication. We present an optimal algorithm for any comb
ination of robot speeds in the case of face-to-face communication. In the
case of wireless communication\, our algorithm is optimal if the slow robo
t is at most 6 times slower than the fast robot.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Recent developments in the theory of distributed graph algorithms
- Juho Hirvonen\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170328T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170328T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:207
DESCRIPTION:I will survey and try to explain the intuition behind several
recent developments in the theory of distributed graph algorithms. I will
focus on the LOCAL model\, where the measure of interest is how far inform
ation has to be propagated in a communication network in order solve a giv
en problem. The problems of interest will be locally checkable labelling p
roblems (LCLs)\, a natural class of problems that allow distributed verifi
cation of proposed solutions.\n\nI will discuss two recent papers in this
field. First\, we gave a lower bound showing that there exist LCL problems
of ”intermediate” complexity\, that is\, complexity strictly between
known complexity classes (Brandt et al.\, STOC 2016). The proof is by a ne
w kind of simulation argument. Second\, Chang et al. (FOCS 2016) showed th
at this lower bound implies an exponential separation between the randomiz
ed and deterministic LOCAL models. Chang et al. also show further connecti
ons between the randomized and deterministic models\, and establish a usef
ul speed-up simulation for the deterministic LOCAL model.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Time and Homonyms Considerations over Community Protocols - Mikael
Rabie\, LIX
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170418T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170418T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:223
DESCRIPTION:Guerraoui and Ruppert introduced the model of Community Protoc
ols. This Distributed System works with agents having a finite memory and
unique identifiers (the set of identifiers being ordered). Each agent can
store a finite number of identifiers they heard about. The interactions ar
e asynchronous and pairwise\, following a fair scheduler.\nThe computation
power of this model is fully characterized: it corresponds exactly to wha
t non deterministic Turing Machines can compute on a space O(n\\log n).\nI
n this talk\, I will focus on two restrictions of the model:\nThe first is
what happens when agents may share identifiers\, the population admitting
homonyms. I will introduce a hierarchy\, with characterizations depending
on the rate of unique identifiers present in the population. The main res
ult is that with log n identifiers\, a Turing Machine with a polylogarithm
ic space can be simulated.\nThe second considers the following time restri
ction: what can be computed in a polylogarithmic number of parallel intera
ctions. This version is not yet characterized\, but I will provide some im
possibility results\, some computable protocols\, and I will give the tigh
ter bound we found.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:From chromatic number to dichromatic number - Pierre Aboulker\, UL
B
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170502T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170502T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:226
DESCRIPTION:A k-dicolouring of a digraph is a partition of its vertex seti
nto k acyclic subdigraphs. The dichromatic number of a \ndigraph D is the
minimum k such that D has a k-dicolouring.\n\nWe first give some properti
es related to the dichromatic number in order to show why and how it gener
alizes the chromatic number of non-oriented graphs. Then we investigate th
e following questions: What can we say about subgraphs\, induced subgraphs
and topological minors of a digraph with large dichromatic number?
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:(Méta)-noyaux constructifs et linéaires dans les graphes peu den
ses - Valentin Garnero\, INRIA Sophia Antipolis
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170404T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170404T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:231
DESCRIPTION:Dans cet exposé je vous présenterai les résultats obtenus a
u cours de ma thèse\, laquelle traite de noyaux et de complexité paramé
trée. \nLa complexité paramétrée est une branche de l'algorithmie qui
analyse la complexité d'un problème en fonction de la taille des donnée
s n et d'un paramètre k (arbitraire). L'objectif est de pouvoir attaquer
des problèmes difficiles (NPc) et de montrer que l’exposition combinato
ire n'est fonction que du paramètre (et pas de la taille des données)\,
cad\, trouver des algorithmes en f(k)+p(n). L'extraction de noyau est une
méthode qui permet d'obtenir des algorithmes avec un telle complexité. I
l s'agit d'un pré-calcul (une réduction polynomiale) qui réduit la tail
le des données en temps polynomial\, tout en garantissant que la taille d
u noyau (l'instance réduite) est bornée par une fonction du paramètre g
(k). Il suffit de résoudre le problème dans le noyau\, de n'importe quel
le façon\, pour obtenir un algorithme en f(g(k)) + p(n).\n\nLa méthode d
e décomposition en régions [Alber\, Fellows\, Niedermeier] est un résul
tat majeur dans le domaine des noyaux. Elle a permis de construire de nomb
reux noyaux linaires pour des variantes de la Domination dans les graphes
planaires. J'illustrerai cette méthode avec le cas de la Domination Rouge
Bleu\, qui consiste à trouver\, dans un graphe bicoloré\, un ensemble d
e sommets bleus tel que tous les sommets rouges sont à distance au plus 1
de la solution.\n\nCette méthode a ensuite été généralisée par des
méta-résultats [ex: Bodlaender\, Fomin\, Lokshtanov\, Penninkx\, Saurabh
\, Thilikos]\, qui prouve l'existence de noyaux (dans des graphes peu dens
es) pour tout problème vérifiant certaines conditions génériques. Je p
résenterai un de ses méta-résultats\, qui se base sur la programmation
dynamique et sur la décomposition en protrusion\, et qui a le mérite d
’être constructif.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Entropy Compression and the Lovasz Local Lemma - Mike Molloy\, Uni
versity of Toronto and Ecole Normale Superieure Paris
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170425T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170425T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:241
DESCRIPTION:The Lovasz Local Lemma\, a cornerstone of the probabilistic me
thod\, is a powerful and widely used proof technique. In 2009\, Moser intr
oduced a technique called entropy compression to provide efficient algorit
hms which construct objects that the Local Lemma guarantees to exist. Rece
ntly\, entropy compression has been used to develop more powerful versions
of the Local Lemma which provide existence proofs in settings where the o
riginal Local Lemma does not apply. I will illustrate this technique with
applications to graph colouring: (a) colouring triangle-free graphs\, and
(b) frugal colouring\, where no colour can appear too many times in any ne
ighbourhood.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matching and covering in cubic graphs - Afshin Behmaram
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170613T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170613T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:271
DESCRIPTION:In this talk\, i will present first some theorems and observat
ions about matching in cubic graphs and about covering the edges of cubic
graphs by perfect matchings. Then I will present some interesting open pro
blems in this area.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Topological Algorithm for Determining How Road Networks Evolve O
ver Time - Siddarth Gupta
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170620T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170620T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:272
DESCRIPTION:We provide an efficient algorithm for determining how a road n
etwork has evolved over time\, given two snapshot instances from different
dates. To allow for such determinations across different databases and ev
en against hand drawn maps\, we take a strictly topological approach in th
is paper\, so that we compare road networks based strictly on graph-theore
tic properties. Given two road networks of same region from two different
dates\, our approach allows one to match road network portions that remain
intact and also point out added or removed portions. We analyze our algor
ithm both theoretically\, showing that it runs in polynomial time for non-
degenerate road networks even though a related problem is NP-complete\, an
d experimentally\, using dated road networks from the TIGER/Line archive o
f the U.S. Census Bureau.\n\nCan you tell me how long should be the talk?
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aspects of Distributed Verification - Mor Perry
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170912T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170912T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:293
DESCRIPTION:In this talk\, we focus on two different aspects of verificati
on of boolean predicates over distributed networks. Given a network config
uration\, the proof-labeling scheme (PLS) model defines a distributed proo
f in the form of a label that is given to each node\, and all nodes locall
y verify that the network configuration satisfies the desired boolean pred
icate by exchanging labels with their neighbors. The complexity measure of
the scheme\, a.k.a. the proof size\, is defined to be the maximum size of
a label.\n\n1. Space-time tradeoffs for distributed verification\, joint
work with Rafail Ostrovsky and Will Rosenbaum. In this work\, we introduce
the notion of a t-PLS\, which allows the verification procedure to run fo
r super-constant time. Our work analyzes the tradeoffs of t-PLS between ti
me\, label size\, message length\, and computation space. We construct a u
niversal t-PLS and prove that it uses the same amount of total communicati
on as a known one-round universal PLS\, and t factor smaller labels. In ad
dition\, we provide a general technique to prove lower bounds for space-ti
me tradeoffs of t-PLS. We use this technique to show an optimal tradeoff f
or testing that a network is acyclic (cycle free). Our optimal t-PLS for a
cyclicity uses proof size\, message size and computation space O( ( log n)
/t).\n\n2. Approximate proof-labeling schemes\, joint work with Keren Cens
or-Hillel and Ami Paz. In this work we extend the PLS model by defining th
e approximate PLS (APLS) model. In this new model\, the predicates for ver
ification are of the form f(G)\\le f'(G)\, where f\, f': F -> N for a fam
ily of configurations F and the set of natural numbers N. Informally\, the
predicates considered in this model are a comparison between two values o
f the configuration. As in the PLS model\, nodes exchange labels in order
to locally verify the predicate\, and all must accept if the network satis
fies the predicate. The soundness condition is relaxed with an approximati
on ration alpha\, so that only if f(G) > alpha*f'(G) some node must reject
. We show that in the APLS model\, the proof size can be much smaller than
the proof size of the same predicate in the PLS model. Moreover\, we prov
e that there is a tradeoff between the approximation ratio and the proof s
ize.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tight Lower Bounds for the Cops and Robbers Game - Jara Uitto\, ET
H Zurich
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170926T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170926T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:302
DESCRIPTION:For the game of cops and robbers\, it is known that in 1-cop-w
in graphs\, the cop can capture the robber in O(n) time and that there exi
st graphs in which this capture time is tight. When k ≥ 2\, a simple cou
nting argument shows that in k-cop-win graphs\, the capture time is at mos
t O( n^(k+1) )\, however\, no non-trivial lower bounds were previously kno
wn\; indeed\, in their 2011 book\, Bonato and Nowakowski ask whether this
upper bound can be improved. We answer the question of Bonato and Nowakows
ki on the negative\, proving that the O(n^(k+1) ) bound is asymptotically
tight for any constant k ≥ 2. This yields a surprising gap in the captur
e time complexities between the 1-cop and the 2-cop cases.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Online k-compaction - Claire Mathieu\, DI - ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171017T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171017T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:323
DESCRIPTION:Given\, at each time t = 1\, 2\, …\, n\, a new file of lengt
h l(t) and a read rate r(t)\, an\nonline k-compaction algorithm must maint
ain a collection of at most k files\, choosing (at each time t\, without k
nowing future inputs) some of the files to merge into one\, thereby incurr
ing a merge cost equal to the total length of the merged files and a read
cost equal to the read rate r(t) times the number of files present at time
t. The goal is to minimize the total cost over time. K-compaction algorit
hms are a key component of log-structured merge trees\, the file-based dat
a structure underlying NoSQL databases such as Accumulo\, Bigtable\, Cassa
ndra\, HBase\,and others. We initiate the theoretical study of k-compactio
n algorithms. We formalize the problem\, consider worst-case\, average-cas
e and competitive analysis (per-instance optimality)\, and propose new alg
orithms that are optimal according to these metrics. \n\nThis is joint wor
k with Carl Staelin\, Neal E. Young\, and Arman Yousefi.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Incremental Update for Graph Rewriting - Jean Krivine\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171212T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171212T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:415
DESCRIPTION:Graph rewriting formalisms are well-established models for the
representation of biological systems such as protein-protein interaction
networks. The combinatorial complexity of these models usually prevents an
y explicit representation of the variables of the system\, and one has to
rely on stochastic simulations in order to sample the possible trajectorie
s of the underlying Markov chain. The bottleneck of stochastic simulation
algorithms is the update of the propensity function that describes the pro
bability that a given rule is to be applied next. In this talk we present
an algorithm based on a data structure\, called extension basis\, that can
be used to update the counts of predefined graph observables after a rule
of the model has been applied. \n\nReference: Boutillier P.\, Ehrhard T.\
, Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (e
ds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Compute
r Science\, vol 10201. Springer\, Berlin\, Heidelberg
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Width parameters of graphs and structured graph classes - Jan Arne
Telle\, University of Bergen
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180220T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180220T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:517
DESCRIPTION:Tree-width and clique-width are well-known graph parameters of
algorithmic use. Clique-width is a stronger parameter in the sense that i
t is bounded on more classes of graphs. In this talk we will present an ev
en stronger graph parameter called mim-width (maximum induced matching-wid
th). Several nicely structured graphs\, like interval graphs\, permutation
graphs and leaf power graphs\, have mim-width 1. Given a decomposition of
bounded mim-width of a graph G we can solve many interesting problems on
G in polynomial time. We will mention also a yet stronger parameter\, sim-
width (special induced matching-width)\, of value 1 even for chordal and c
o-comparability graphs.\n\nParts of the talk are based on joint work with
O.Kwon and L.Jaffke\, to appear at STACS 2018.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Obstructions pour certaines classes de matroides linéaires - Mama
dou Kante\, ISIMA
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180313T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180313T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:518
DESCRIPTION:Savoir qu’une classe de structures est caractérisée par un
e liste finie d’obstructions n’est pas toujours satisfaisante pour rec
onnaître les membres de la classe et il est souvent désirable pour un al
gorithme de reconnaissance de fournir un certificat de non appartenance. D
ans cet exposé\, j’expliquerai quelques aspects de mes travaux sur le c
alcul des obstructions pour certaines classes de matroides.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Local Search for Geometric Optimization Problems. - Nabil Mustafa\
, ESIEE
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180212T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180212T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:519
DESCRIPTION:Local-search is an intuitive approach towards solving combinat
orial optimization problems: start with any feasible solution\, and try to
improve it by local improvements. Like other greedy approaches\, it can f
ail to find the global optimum by getting stuck on a locally optimal solut
ion. In this talk I will present the ideas and techniques behind the use o
f local-search in the design of provably good approximation algorithms for
some combinatorial problems\, such as independent sets\, vertex cover\, d
ominating sets in geometric intersection graphs. The key unifying theme is
the analysis of local expansion in planar graphs. Joint work with Norbert
Bus\, Shashwat Garg\, Bruno Jartoux and Saurabh Ray.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nombre chromatique et la méthode topologique - Matej Stehlik\, Un
iversité Grenoble Alpes - GSCOP
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180327T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180327T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:536
DESCRIPTION:La méthode topologique est la seule méthode connue pour dét
erminer le nombre chromatique de certaines classes de graphes\, et un prob
lème classique est d’obtenir des preuves alternatives plus élémentair
es. Après une brève introduction à la méthode topologique\, je présen
terai certains de mes travaux qui y sont liés et j’expliquerai pourquoi
le recours à la topologie est parfois difficilement évitable.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Induced minors and well-quasi-ordering - Marcin Kaminski
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180403T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180403T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:537
DESCRIPTION:A graph H is an induced minor of a graph G if it can be obtain
ed from an induced subgraph of G by contracting edges. Otherwise\, G is sa
id to be H-free. \n\nWe show that the class of H-free graphs is well-quasi
-ordered by induced minors if and only if H is an induced minor of the gem
(=the path on 4 vertices plus a dominating vertex) or the graph obtained
by adding a vertex of degree 2 to the K4 (= the complete graph on 4 vertic
es). \n\nThis generalizes a a result of Robin Thomas who proved that K4-fr
ee graphs are well-quasi-ordered by induced minors and complements similar
dichotomy theorems proved by Guoli Ding for subgraphs and Peter Damaschke
for induced subgraphs.\n\nThis is joint work with Jarosław Błasiok\, Je
an-Florent Raymond\, and Théophile Trunck.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aspects des Graphes Aléatoires - Dieter Mitsche\, Université Nic
e
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180227T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180227T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:546
DESCRIPTION:Dans cet exposé j'expliquerai plusieurs de mes travaux sur di
fférents modèles de graphes aléatoires : en particulier\, je vais expli
quer les périodes de connexité d'un modèle dynamique des graphes géom
étriques Euclidiens\, la rigidité et l'orientabilité du graphe G(n\,p)\
, et je parlerai (de résultats sur) des graphes aléatoires hyperboliques
et d'applications pour des grands réseaux.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing node centrality in large graphs: from theory to practice
and back - Pierluigi Crescenzi\, Universite de Pise
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180320T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180320T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:550
DESCRIPTION:The computation of several graph measures\, based on the dista
nce between nodes\, is very often part of the analysis of real-world compl
ex networks. The diameter\, the betweenness and the closeness centrality\,
and the hyperbolicity are typical examples of such measures. In this talk
\, we will focus on the computation of one specific measure\, that is\, th
e node closeness centrality which is basically the inverse of the average
distance of a node from all other nodes of the graph. Even though polynomi
al-time algorithms are available for the computation of this measure\, in
practice these algorithms are not useful\, due to the huge size of the net
works to be analysed. One first theoretical question is\, hence\, whether
better algorithms can be designed\, whose worst-case complexity is (almost
) linear in the size of the input graph. We will first show that\, unfortu
nately\, for the closeness centrality no such algorithm exists (under reas
onable complexity theory assumptions). This will lead us back to the pract
ical point of view: we will then describe a heuristics that allows us to c
ompute the above measure in (practical) linear time\, even though its wors
t-case complexity is (in practice) intractable. This result will finally m
otivate our return to theory in order to understand the reason why\, in pr
actice\, this heuristics works so well: we will indeed conclude by showing
that\, in the case of several random graph generating models\, the averag
e time complexity of the heuristics is indeed (almost) linear. This talk w
ill summarise the research work that I have done in collaboration with Eli
sabetta Bergamini\, Michele Borassi\, Michel Habib\, Andrea Marino\, Henni
ng Meyerhenke\, and Luca Trevisan\, and will be mostly based on two papers
presented at ALENEX 2016\, and SODA 2017.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Steiner trees with edge capacities. - Cédric Bentz
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180406T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180406T110000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:578
DESCRIPTION:Abstract : Assume we are given a graph G=(V\,E) (directed or n
ot) with\ncapacities and costs on the edges\, a vertex r of G called root\
, and a set\nX of terminal vertices. The problem we consider is the follow
ing: find in\nG a minimum-cost tree rooted at r\, spanning all the vertice
s in X\, and\nsuch that\, for each edge of this tree\, the number of paths
going from r to\nterminals and containing this edge does not exceed its c
apacity. When all\ncapacities are at least |X|\, then this is the classica
l Steiner tree\nproblem\, with a given root. The generalization we are int
erested in has\nseveral relevant applications\, including the design of wi
nd farm\ncollection networks. We study the complexity of this problem in d
ifferent\nsettings: for instance\, the graph may be directed or not\, |X|
may be fixed\nor not\, the costs may be 0 or not. Whenever this is possibl
e\, we also\ndesign approximation algorithms to solve the problem.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fractional chromatic number of small degree graphs and girth. - Fr
ançois Pirot\, Université de Strasbourg
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180522T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180522T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:595
DESCRIPTION:It is well known that you can color a graph G of maximum degre
e d greedily with d+1 colors. Moreover\, this bound is tight\, since it is
reached by the cliques. Johansson proved with a pseudo-random coloring sc
heme that you can color triangle-free graphs of maximum degree d with no m
ore than O(d/log d) colors. This result has been recently improved to (1+
ε)(d/log d) for any ε>0 when d is big enough. This is tight up to a mult
iplicative constant\, since you can pseudo-randomly construct a family of
graphs of maximum degree d\, arbitrary large girth\, and chromatic number
bigger than d / (2 log d). Although these are really nice results\, they a
re only true for big degrees\, and there remains a lot to say for small de
gree graphs.\nWhen the graphs are of small degree\, it is interesting to c
onsider the fractional chromatic number instead\, since it has infinitely
many possible values -- note that cubic graphs are either bipartite\, the
clique K4\, or of chromatic number 3. It has already been settled that the
maximum fractional chromatic number over the triangle-free cubic graphs i
s 14/5. I will present a systematic method to compute upper bounds for the
independence ratio of graphs of given (small!) degree and girth\, which c
an sometimes lead to upper bounds for the fractional chromatic number\, an
d can be adapted to any family of small degree graphs under some local con
straints.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stable Outcomes in Modified Fractional Hedonic Games - Yllka Velaj
\, CWI Amsterdam
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181023T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181023T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:691
DESCRIPTION:In coalition formation games\, self-organized coalitions are c
reated as a result of the strategic interactions of independent agents. Fo
r each couple of agents $(i\,j)$\, weight $w_{i\,j}=w_{j\,i}$ reflects how
much agents $i$ and $j$ benefit from belonging to the same coalition. We
consider the modified fractional hedonic game\, that is a coalition format
ion game in which agents' utilities are such that the total benefit of age
nt $i$ belonging to a coalition (given by the sum of $w_{i\,j}$ over all o
ther agents $j$ belonging to the same coalition) is averaged over all the
other members of that coalition\, i.e.\, excluding herself. Modified fract
ional hedonic games constitute a class of succinctly representable hedonic
games.\n\nWe are interested in the scenario in which agents\, individuall
y or jointly\, choose to form a new coalition or to join an existing one\,
until a stable outcome is reached. To this aim\, we consider common stabi
lity notions\, leading to strong Nash stable outcomes\, Nash stable outcom
es or core stable outcomes: we study their existence\, complexity and perf
ormance\, both in the case of general weights and in the case of 0-1 weigh
ts.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rank Based Approach on Graphs with Structured Neighborhood - Bergo
ugnoux Benjamin\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181218T153000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181218T163000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:701
DESCRIPTION:In this talk\, I will present a framework combining the rank-b
ased approach with the notion of $d$-neighbor equivalence. The rank-based
approach is a technique introduced by Bodlaender et al. in 2015 to obtaine
d $2^{O(k)}\\cdot n$ time algorithms\, $k$ the treewidth of the input grap
h\, for a wide range of connectivity problems.\n\nThe $d$-neighbor equival
ence is a tools introduced by Bui-Xuan et al. in 2013 to obtained efficien
t parameterized algorithms for many width measures (clique-width\, rank-wi
dth\, mim-width\,...) and for many problems with a locally checkable const
raint (Dominating Set\, Independent Set\,...).\n \nBy combining these two
notions\, we obtain efficient algorithms for several connectivity problems
such as Connected Dominating Set\, Node Weighted Steiner Tree\, Maximum I
nduced Tree\, Longest Induced Path\, and Feedback Vertex Set. For all thes
e problems\, we obtain $2^{O(k)}\\cdot n^{O(1)}$\, $2^{O(k \\log(k))}\\cdo
t n^{O(1)}$\, $2^{O(k^2)}\\cdot n^{O(1)}$ and $n^{O(k)}$ time algorithms p
arameterized respectively by clique-width\, $\\mathbb{Q}$-rank-width\, ran
k-width and maximum induced matching width. Our approach simplifies and un
ifies the known algorithms for each of the parameters and match asymptotic
ally also the best time complexity for Vertex Cover and Dominating Set.\n
\nPaper available on HAL :\n https://hal.archives-ouvertes.fr/hal-01799573
v2/document
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Set operads and decomposition theory - Miguel Mendez
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181127T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181127T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:730
DESCRIPTION:Informally\, a set operad is a family of combinatorial structu
res plus 1) an (associative) mechanism that creates larger structures from
smaller using as assembler an external structure in the same family 2) Id
entity structures over singleton sets. We give the precise definition of s
et operads in the context of Joyal’s combinatorial species. Interesting
examples of set operads are Graphs\, directed graphs\, posets\, Boolean fu
nctions\, monotone Boolean functions\, simple multiperson games\, simplici
al complexes\, etc. We show that Decompositions theory of combinatorial st
ructure can be formulated in the general context of set operads by using t
he operation of amalgam (coproduct) of operads.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:A random graph model based on the Modular decomposition of graphs
- Carenne Ludeña\, Universidad Jose Tadeo Lozano
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181129T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181129T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:731
DESCRIPTION:We consider Gallai's graph Modular Decomposition theory for\nn
etwork analytics. On the one hand\, by arguing that this is a choice\ntool
for understanding structural and functional similarities among\nnodes in
a network. On the other\, by proposing a model for random\ngraphs based on
this decomposition. Our approach establishes a well\ndefined context for
hierarchical modeling and provides a solid\ntheoretical framework for prob
abilistic and statistical methods. Theoretical and\nsimulation results sho
w the model acknowledges scale free networks\,\nhigh clustering coefficien
ts and small diameters all of which are\nobserved features in many natural
and social networks.
LOCATION:Salle 3014
END:VEVENT
BEGIN:VEVENT
SUMMARY:Some results and problems on unique-maximum colorings of plane gra
phs - Riste Škrekovski\, University of Ljubljana
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181211T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181211T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:744
DESCRIPTION:A \\textit{unique-maximum} coloring of a plane graph is a prop
er vertex coloring by natural numbers where on each face $\\alpha$ the max
imal color appears exactly once on the vertices of $\\alpha$.\nFabrici and
G\\"{o}ring proved that six colors are enough for any plane graph and con
jectured that four colors suffice. Thus\, this conjecture is a strengtheni
ng of the Four Color Theorem.\nWendland later decreased the upper bound fr
om six to five.\n\nWe first show that the conjecture holds for various sub
classes of planar graphs but then we disprove it for planar graphs in gene
ral. So\, we conclude that the facial unique-maximum chromatic number of t
he sphere is not four but five.\n\nAdditionally\, we will consider a facia
l edge-coloring analogue of the aforementioned coloring\, and we will conc
lude the talk with various open problems.\n\n(Joint work with Vesna Andova
\, Bernard Lidick\\'y\, Borut Lu\\v{z}ar\, and Kacy Messerschmidt)
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing Giant Diameters with Breadth-First Search and Range Quer
ies - Guillaume Ducoffe\, ICI Roumanie
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190122T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190122T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:755
DESCRIPTION:A well-known problem for which it is difficult to improve the
textbook algorithm is computing the graph diameter. We present two version
s of a simple algorithm (one being Monte Carlo and the other deterministic
) that for every fixed $h$ and unweighted undirected graph $G$ with $n$ ve
rtices and $m$ edges\, either correctly concludes that $diam(G) < hn$ or o
utputs $diam(G)$\, in time ${\\cal O}(m+n^{1+o(1)})$. The algorithm combin
es a simple randomized strategy for this problem (Damaschke\, {\\it IWOCA'
16}) with a popular framework for computing graph distances that is based
on range trees (Cabello and Knauer\, {\\it Computational Geometry'09}). We
also prove that under the Strong Exponential Time Hypothesis (SETH)\, we
cannot compute the diameter of a given $n$-vertex graph in truly subquadra
tic time\, even if the diameter is an $\\Theta(n/\\log{n})$.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Spectral embedding for graph classification - Marc Lelarge\, Inria
& ENS Paris
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190306T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190306T120000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:775
DESCRIPTION:Learning on graphs requires a graph feature representation abl
e to discriminate among different graphs while being amenable to fast comp
utation. The graph isomorphism problem tells us that no fast representatio
n of graphs is known if we require the representation to be both invariant
to nodes permutation and able to discriminate two non-isomorphic graphs.
Most graph representations explored so far require to be invariant. We exp
lore new graph representations by relaxing this constraint. We present a g
eneric embedding of graphs relying on spectral graph theory called Spectra
l Graph Embedding (SGE). We show that for a large family of graphs\, our e
mbedding is still invariant. To evaluate the quality and utility of our SG
E\, we apply them to the graph classification problem. Through extensive e
xperiments\, we show that a simple Random Forest based classification algo
rithm driven with our SGE reaches the state-of-the-art methods.\n\nAlthoug
h our SGE is handcrafted\, we also show how our generic embedding techniqu
e can be learned and built in a data-driven manner opening the way to new
learning algorithms and deep learning architectures with some invariant co
nstraints built-in.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Around Brooks' theorem - Marthe Bonamy\, CNRS - LABRI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190219T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190219T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:799
DESCRIPTION:In this talk\, we will discuss various results around Brooks'
theorem: a graph has chromatic number at most its maximum degree\, unless
it is a clique or an odd cycle. We will consider stronger variants and loc
al versions\, as well as the structure of the solution space of all corres
ponding colorings.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Distributed Shortest Paths\, Exactly - Danupon Nanongkai\, KTH
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190219T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190219T120000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:804
DESCRIPTION:This talk concerns the problem of quickly computing distances
and shortest paths on distributed networks (the CONGEST model). There have
been many developments for this problem in the last few year\, resulting
in tight approximation schemes. This left open whether exact algorithms ca
n perform equally well. In this talk\, we will discuss some recent progres
s in answering this question. Most recent works that this talk is based on
are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv 2018
).
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Token Sliding on Split Graphs - Rémy Belmonte
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190312T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190312T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:823
DESCRIPTION:We consider the complexity of the \\textsc{Independent Set\nRe
configuration} problem under the Token Sliding rule. In this problem we ar
e\ngiven two independent sets of a graph and are asked if we can transform
one to\nthe other by repeatedly exchanging a vertex that is currently in
the set with\none of its neighbors\, while maintaining the set independent
. Our main result is\nto show that this problem is PSPACE-complete on spli
t graphs (and hence also on\nchordal graphs)\, thus resolving an open prob
lem in this area. We then go on to consider\nthe $c$-\\textsc{Colorable Re
configuration} problem under the same rule\, where the\nconstraint is now
to maintain the set $c$-colorable at all times.\n\nJoint work with Eun-Jun
g Kim\, Michael Lampis\, Valia Mitsou\, Yota Otachi and Florian Sikora.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hitting minors on bounded treewidth graphs - Julien Baste\, Univer
sität Ulm\, Ulm\, Germany
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190322T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190322T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:839
DESCRIPTION:For a fixed collection of graphs F\, the F-DELETION problem\nc
onsists in\, given a graph G and an integer k\, decide whether there\nexis
ts S\, subset of V(G)\, with |S| <= k such that G-S does not contain\nany
of the graphs in F as a minor. This NP-hard problem is a\ngeneralization o
f some well known graph problems as VERTEX COVER\n(F={K_2})\, FEEDBACK VER
TEX SET (F={K_3})\, or VERTEX PLANARIZATION\n(F={K_5\,K_{3\,3}}). We are i
nterested in its parameterized complexity\nwhen the parameter is the treew
idth of G\, denoted by tw. Namely\, the\nobjective is to determine\, for a
fixed F\, the (asymptotically) smallest\nfunction f_F: N -> N such that F
-DELETION can be solved in time\nf_F(tw)*n^{O(1)} on n-vertex graphs. In t
his talk we will provide the\nbasic definitions of parameterized complexit
y\, motivate the problem\,\nand then\, review some of the lower and upper
bounds on the function f_F\nfor several instantiations of F.\n\nThe presen
ted results are joint work with Ignasi Sau and Dimitrios \nThilikos and ca
n be found in\n.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Temporal matching - Binh-Minh Bui-Xuan\, LIP6
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190409T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190409T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:854
DESCRIPTION:When mining data collected from human activities\, graph edges
come\nordered by the time instants where they are recorded\, e.g. with we
b logs\, phone\ncalls\, email exchanges\, ... We call this kind of data a
link stream. We\nintroduce the notion of a temporal matching (an independe
nt temporal edge set)\nin a link stream. In a link stream where the time d
imension is reduced to one\nunique time instant\, our new definition is eq
uivalent to that of a matching in\nclassical graph theory.\n\nIn contrast
to classical graph theory\, we show that the problem of computing a\ntempo
ral matching of maximum size in a link stream is in general NP-hard. We\nt
hen depict a kernelization algorithm parameterized by the solution size fo
r the\nproblem\, producing quadratic kernels. As a byproduct we also give
a\n2-approximation algorithm. Both algorithms are implemented and confront
ed to\nlink streams collected from real world graph data:\n\nhttps://githu
b.com/antoinedimitriroux/Temporal-Matching-in-Link-Streams\n\nWe observe f
rom the experiments that the kernelization algorithm can perform\nvery wel
l in practice\, reducing the instance size downto 10-20% on realistic\nmin
ing parameters. In contrast\, the 2-approximation gives rather mixed resul
ts.\nWe conjecture that the approximation factor can be improved.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Graph query languages - Amélie Gheerbrant\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190509T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190509T160000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:872
DESCRIPTION:Graph databases use graph structure to represent and query dat
a. The talk will survey some graph query languages used in this context\,
with a focus on regular path queries (RPQs) and conjunctive regular path q
ueries (CRPQs). We will present the different semantics that graph databas
e systems use for them (every path\, simple path\, trail)\, and recall com
putational complexities of query evaluation and query containment. We will
finally discuss some issues related to querying not only the topology but
also the data of the graph and present a few open problems that could be
of interest both to the graph and algorithms group and to the automata gro
up.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Eternal domination in graphs - Ben Seamone\, Université de Montr
éal and Dawson College
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190521T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190521T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:874
DESCRIPTION:Given a graph\, how can one distribute resources to vertices i
n order to be able to respond to any infinite sequences of demands? This i
s the fundamental question which the study of eternal domination in graphs
attempts to answer. I will give a brief survey of what is known about ete
rnal domination\, followed by recent progress on some eternal domination p
roblems. Notably\, we refute a conjecture of Klostermeyer and Mynhardt on
eternal domination in prisms over graphs\, and introduce a fractional vers
ion of eternal domination which to our knowledge has not yet been studied.
Results were jointly obtained with D. Khatri\, A. Krim-Yee\, N. Kumar\, G
. MacGillivray\, V. Virgile\, and A. Xu.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Enumerating minimal dominating sets in $K_t$-free graphs - Jean-Fl
orent Raymond\, TU Berlin
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190528T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190528T160000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:891
DESCRIPTION:In algorithmic enumeration\, one is typically asked to output
the set of\nall objects of a certain type related to an input (e.g. all th
e cycles\nof a graph\, all its maximal cliques\, etc.)\, rather than findi
ng just\none. The problem of enumerating all the minimal dominating sets o
f a\ngraph received an important attention\, partly because of its strong\
nlinks with a fundamental hypergraph problem. A long standing open\nquesti
on is whether the above problem can be solved in (output-)\npolynomial tim
e.\nIn this talk\, I will introduce the problem and present an\noutput-pol
ynomial algorithm for Kt-free graphs. This is joint work with\nMarthe Bona
my\, Oscar Defrain\, and Michał Pilipczuk.\n\nLink to the article: https:
//arxiv.org/abs/1810.00789
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Evolutionary Algorithms -- From Theory to Practice and Back - Caro
la Doerr\, CNRS\, LIP6 Sorbonne University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190624T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190624T120000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:895
DESCRIPTION:Most real-world optimization problems do not have an explicit
problem formulation\, but only allow to compute the quality of selected so
lution candidates. Solving such black-box optimization problems requires i
terative procedures which use the feedback gained from previous evaluation
s to determine the strategy by which the next solution candidates are gene
rated. Many black-box optimization algorithms\, such as Simulated Annealin
g\, Evolutionary Algorithms\, Swarm Intelligence Algorithms\, are randomiz
ed -- making it very difficult to analyze their performances mathematicall
y.\n\nIn the last 15 years\, the theory of randomized black-box optimizati
on has advanced considerably\, and has contributed to efficient optimizati
on by providing insights into the working principles of black-box optimiza
tion which are hard or impossible to obtain by empirical means. On the oth
er hand\, empirically-guided benchmarking has opened up new research direc
tions for theoretical investigations.\n\nIn this presentation we will disc
uss the state of the art in the theory of randomized black-box optimizatio
n algorithms. As part of this critical survey we will also mention a numbe
r of open questions and connections to other fields of Computer Science.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Algorithms for generalized modular decomposition - Fabien De Montg
olfier\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191008T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191008T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:949
DESCRIPTION:Modular decomposition is a graph decomposition that can be com
puted in linear time and allows to solve many problems efficiently when th
e width of the decomposition tree is bounded. In this talk we survey how t
o generalize it to some other objects: bipartite graphs\, tournaments\, an
d hypergraphs (for the latter three variations have been proposed). Algori
thmic approaches and tools to compute them are presented: top-down method\
, bottom-up method\, and orthogonals.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Finer Tight Bounds for Coloring on Clique-Width - Michael Lampis\,
Universite Paris Dauphine
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191022T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191022T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:959
DESCRIPTION:We revisit the complexity of Coloring with respect to two\npar
ameters: the number of given colors k\; and the "width" of the input\ngrap
h w. Here\, by width we mean a measure of complexity of the graph.\nWhen t
he notion of width in question is treewidth\, the problem is very\nwell-un
derstood: there exists a simple k^w algorithm\, and no algorithm\ncan do s
ignificantly better under the Strong Exponential Time\nHypothesis (SETH)\,
even if we replace treewidth by much more\nrestrictive notions\, such dis
tance to linear forest. In this talk we\nwill consider the notion of cliqu
e-width\, which is the most\nwell-studied generalization of treewidth for
dense graphs. We will\nsketch an algorithm and a matching lower bound (und
er the SETH) which\ncompletely determine the complexity of coloring as a f
unction of\nclique-width\, for any fixed k>=3.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Distance labeling\, Ruzsa-Szemeredi graphs and SumIndex communicat
ion complexity problem - Laurent Viennot
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191106T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191106T120000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:972
DESCRIPTION:A distance labeling consists in coding the distances in a grap
h by assigning a label L_u to each vertex u\, such that the distance betwe
en two nodes u and v can be computed from L_u et L_v. We will see that the
minimum size of labels in a constant degree graph is related to other par
ameters coming from combinatorics and communication complexity. The first
one is the Ruzsa-Szemeredi number that measures the maximum number of edge
s in an n-node graph that can be decomposed into n induced matchings (an e
dge of one matching cannot be incident to two edges of another matching).
The second one is the minimum size of messages in the SumIndex problem whe
re Alice knows an n-bit vector X and an index a\, Bob knows X and an index
b\, and where they both send a message to a referee that should compute t
he bit of X in position a+b mod n from the two messages (the referee does
not know X).\n\nJoint work with Adrian Kosowski and Przemyslaw Uznanski.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Flows in signed graphs - Denis Cornaz\, Université Paris Dauphine
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191126T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191126T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:974
DESCRIPTION:Packing negative cycles in signed graphs has application to mu
ltiflow problem.\nIt allows to predict when the cut condition is sufficien
t for the existence of a multiflow satisfying the demand. Here the signed
edges play the role of the demand\, and the unsigned edges play the role o
f the links. We investigate a min-max relation in this context related to
the notion of box totally-dual-integral linear systems.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Strong chromatic index of unitary Cayley graphs - Suchismita Mishr
a\, IITM
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191112T153000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191112T163000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:997
DESCRIPTION:A strong edge coloring of a graph is an assignment of colors t
o edges such that every color class induces a matching. The smallest numbe
r of colors for which a strong edge coloring of a graph G exists is known
as the strong chromatic index and it is denoted by $\\chi′_s(G)$. It is
already known that the problem of finding the strong chromatic index for a
rbitrary graphs is NP-complete. In this talk\, we will discuss strong edge
coloring of unitary Cayley graphs.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Counting independent sets in strongly orderable graphs - Marc Hein
rich
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191203T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191203T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1017
DESCRIPTION:We are interested in counting problems which consists in compu
ting the number of solutions to a given instance of the problem. \nThis ki
nd of question has strong connexions\, in particular in the case of indepe
ndent sets\, with problems from statistical physics and what is called the
hard core distribution. As many counting problems\, counting exactly the
number of independent sets of a graphs is difficult (i.e.\, #P-complete) e
ven on bipartite graphs\, and even difficult to approximate for general gr
aphs. On the other hands\, it was shown to be polynomial time solvable for
more restricted classes of graphs such as chordal graphs\, cographs or mo
notone bipartite graphs. We show that the number of independent sets can a
lso be computed in polynomial time for strongly orderable graphs which is
a super-class of chordal bipartite and strongly chordal graphs.\nThis is j
oint work with Haiko Muller.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Time for coloring - Ana Silva\, Departamento de Matemática - Univ
ersidade Federal do Ceará
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200128T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200128T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1060
DESCRIPTION:A temporal graph with lifetime $T$ is a pair $(G\,\\lambda)$ w
here $G$ is a simple graph with $n$ nodes and $\\lambda:E(G)\\rightarrow [
T]$ is a function of discrete-timed labels telling the snapshots where an
edge is active. As recently defined\, a temporal coloring of $(G\,\\lambda
)$ is a coloring of each snapshot that properly colors each edge at least
once throughout its lifetime\; and the \\emph{temporal chromatic number of
$(G\,\\lambda)$} is the minimum number $t\\chi(G\,\\lambda)$ of colors th
at can be used to get a temporal coloring.\n\nIn this talk\, I will presen
t the results\, obtained in collaboration with Andrea Marino\, in which we
focus on temporal graphs whose edges remain active for at least $t$ times
tamps (these are called $t$-persistent temporal graphs). Among other thing
s\, we:\n1) give some upper bounds for the minimum number of colors needed
in terms of $t$ and of the chromatic number of the underlying static grap
h $G$\; \n2) prove that $k$ colors are always sufficient when $t$ is at le
ast $\\log_k n$\, and that if $t$ is smaller\, then it is NP-complete to d
ecide whether $k$ colors are enough\; \n3) prove that the problem is NP-co
mplete even when $G$ has bounded treewidth\, and each snapshot is planar a
nd has constant size\; and \n4) give an FPT algorithm with parameters the
treewidth of $G$ and $T$. \n\nOur results also imply many interesting fact
s: for instance\, we know that if $G$ is planar and 2-persistent\, then 2
colors are always sufficient
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fixed-parameter algorithms for finding small separators in graphs
- Pierre Berge
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200407T153000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200407T163000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1123
DESCRIPTION:In this talk\, I introduce some results obtained during my Ph.
D. All of them deal with cut and connectivity problems in graphs. I presen
t the parameterized complexity of the Partial One-Target Cut (POTC) proble
m\, where the objective is to identify the smallest edge cutset separating
a certain proportion r of sources into an input set S={s_1\,...\,s_k} wit
h a single target t. I provide the proof that POTC is fixed-parameter trac
table (FPT) parameterized by the cutset size p. This means that an algorit
hm finds an exact solution in time f(p)P(n)\, where f is an arbitrary func
tion\, P a polynomial function\, and n the instance size. The algorithm is
based on the random sampling of important separators. This result highlig
hts a surprising complexity gap between the edge and the vertex versions o
f the problem. Indeed\, when the cutset is made up of vertices\, POTC is u
nlikely to be FPT.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:Temporal Closeness in Temporal Networks - Pierluigi Crescenzi\, IR
IF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200414T153000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200414T163000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1125
DESCRIPTION:The closeness centrality measure associates to each node of a
graph its average distance from all the other nodes. In this talk\
, we will consider a temporal version of this measure\, which have been re
cently introduced and analysed in the case of temporal graphs (that is\, g
raphs in which edges can appear and disappear during time). In particular\
, we will show how this measure can be efficiently approximated by using a
“backward” temporal breadth-first search algorithm and a classical sa
mpling technique. We will then introduce a “temporally global” closene
ss centrality measure of a node in a temporal graph\, which is quite simil
ar to the notion of AUC (Area Under Curve)\, and we will show how this glo
bal measure can also be efficiently approximated. We conclude by presentin
g several experimental results in the case of medium/large real-world temp
oral networks. This is a joint work with Clémence Magnien and Andrea Mari
no.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:Diameter computation on H-minor free graphs and graphs of bounded
(distance) VC-dimension - Guillaume Ducoffe
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200529T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200529T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1157
DESCRIPTION:Under the Strong Exponential-Time Hypothesis\, the diameter of
general unweighted graphs cannot be computed in truly subquadratic time.
Nevertheless there are several graph classes for which this can be done su
ch as bounded-treewidth graphs\, interval graphs and planar graphs\, to na
me a few. We propose to study unweighted graphs of constant distance VC-di
mension as a broad generalization of many such classes – where the dista
nce VC-dimension of a graph G is defined as the VC-dimension of its ball h
ypergraph: whose hyperedges are the balls of all possible radii and center
s in G. In particular for any fixed H\, the class of H-minor free graphs h
as distance VC-dimension at most |V(H)|− 1.\n\n• Our first main result
is a Monte Carlo algorithm that on graphs of distance VC-dimension at mos
t d\, for any fixed k\, either computes the diameter or concludes that it
is larger than k in time O(k · mn^{1−εd})\, where εd ∈ (0\; 1) only
depends on d. We thus obtain a truly subquadratic-time parameterized algo
rithm for computing the diameter on such graphs.\n• Then as a byproduct
of our approach\, we get a truly subquadratic-time randomized algorithm fo
r constant diameter computation on all the nowhere dense graph classes. Th
e latter classes include all proper minor-closed graph classes\, bounded-d
egree graphs and graphs of bounded expansion.\n• Finally\, we show how t
o remove the dependency on k for any graph class that excludes a fixed gra
ph H as a minor. More generally\, our techniques apply to any graph with c
onstant distance VC-dimension and polynomial expansion (or equivalently ha
ving strongly sublinear balanced separators). As a result for all such gra
phs one obtains a truly subquadratictime randomized algorithm for computin
g their diameter.\n\nWe note that all our results also hold for radius com
putation. Our \napproach is based on the work of Chazelle and Welzl who pr
oved the \nexistence of spanning paths with strongly sublinear stabbing nu
mber for every hypergraph of constant VC-dimension. We show how to compute
such paths efficiently by combining known algorithms for the stabbing num
ber problem with a clever use of ε-nets\, region decomposition and other
partition techniques.\n\nIf time allows\, I will also mention recent impro
vements of the above results\, to eccentricity and distance oracle computa
tions.\n\nThis is joint work with Michel Habib and Laurent Viennot.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:Diversity of Solutions: An Exploration Through the Lens of Fixed-P
arameter Tractability Theory - Julien Baste\, Universität Ulm
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200602T153000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200602T163000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1160
DESCRIPTION:When modeling an application of practical relevance as an inst
ance of a combinatorial problem X\, we are often interested not merely in
finding one optimal solution for that instance\, but in finding a sufficie
ntly diverse collection of good solutions. In this work we initiate a syst
ematic study of diversity from the point of view of fixed-parameter tracta
bility theory. First\, we consider an intuitive notion of diversity of a c
ollection of solutions which suits a large variety of combinatorial proble
ms of practical interest. We then present an algorithmic framework which -
-automatically-- converts a tree decomposition-based dynamic programming a
lgorithm for a given combinatorial problem X into a dynamic programming al
gorithm for the diverse version of X. Surprisingly\, our algorithm has a p
olynomial dependence on the diversity parameter.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:Multiple list colouring of $3$-choice critical graphs - Rongxing X
u
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200922T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200922T160000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1173
DESCRIPTION:A graph $G$ is called $3$-choice critical if $G$ is not $2$-ch
oosable but any proper subgraph is $2$-choosable. A characterization of $
3$-choice critical graphs was given by Voigt in 1998. Voigt conjectured th
at if $G$ is a bipartite $3$-choice critical graph\, then $G$ is $(4m\, 2m
)$-choosable for every integer $m$. It is true if $G=\\Theta_{2\,2\,2\,2}$
\, which was proved by Voigt and Tuza in 1996. However\, this conjecture w
as disproved by Meng\, Puleo\, and Zhu in 2017. They showed that if $G=\
\Theta_{r\,s\,t}$ where $r\,s\,t$ have the same parity and $\\min\\{r\,s\,
t\\} \\ge 3$\, or $G=\\Theta_{2\,2\,2\,2p}$ with $p \\ge 2$\, then $G$ is
bipartite $3$-choice critical\, but not $(4\,2)$-choosable. On the othe
r hand\,\nall the other bipartite 3-choice critical graphs are $(4\,2)$-ch
oosable. \nThis paper strengthens the result of Meng\, Puleo\, and Zhu a
nd shows that all the other bipartite $3$-choice critical graphs are $(4m\
,2m)$-choosable for every integer $m$.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Vizing's edge colouring question - Marthe Bonamy\, CNRS\, LaBRI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201006T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201006T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1183
DESCRIPTION:In his 1965 seminal paper on edge colouring\, Vizing proved th
at a (Delta+1)-edge colouring can be reached from any given proper edge co
louring through a series of Kempe changes\, where Delta is the maximum deg
ree of the graph. He concludes the paper with the following question: can
an optimal edge colouring be reached from any given proper edge colouring
through a series of Kempe changes? In other words\, if the graph is Delta-
edge-colourable\, can we always reach a Delta-edge-colouring? If true\, th
is would imply a more recent conjecture of Mohar (2006) that in any graph\
, all (Delta+2)-edge-colourings are equivalent up to a series of Kempe cha
nges. We discuss recent progress around these questions.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Distributed Certification of Graph Classes - Pierre Fraigniaud\, I
RIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201020T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201020T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1193
DESCRIPTION:Distributed certification is a sub-topic of distributed comput
ing aiming at providing tools for enabling a set of autonomous computing e
ntities (a.k.a. processes) to coordinate for deciding whether the distribu
ted system at hand satisfies a given correctness certificates. Among many
scenarios\, one important aspect of this line of study is certifying that
the actual network of processes satisfies some given graph properties (e.g
.\, being 3-colorable\, being acyclic\, being planar\, etc.). The main con
straint for deciding whether the property holds is that computation must b
e local\, that is\, every process may interact only once with its neighbor
s in the network. Not all graph properties are decidable under this constr
aint. For those “locally undecidable“ classes\, it is however possible
to distribute a proof that the network satisfies the property\, by assign
ing small certificates to the nodes\, which can then be checked locally. N
evertheless\, some properties (e.g.\, non 3-colorability) may require huge
certificates. To decrease the size of the certificates\, interactive proo
fs have been considered\, where every process interacts first with an exte
rnal entity (e.g.\, the “cloud“) before interacting locally with its n
eighbors for forging its opinion regarding whether the graph satisfies the
property or not. The talk will present these different mechanisms. It wil
l illustrate them using specific graph properties like planarity and bound
ed genus\, and will discuss the ability to certify graph excluding a speci
fic given minor.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Graph classes and forbidden patterns on three and four vertices -
Laurent Feuilloley\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201124T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201124T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1248
DESCRIPTION:In this talk\, I will present some results on the characteriza
tion and the recognition of graph classes. \n\nA popular way to characteri
ze a graph class is to list a minimal set of forbidden induced subgraphs.
Unfortunately\, this strategy hardly ever leads to a very efficient recogn
ition algorithm. On the other hand\, many graph classes can be efficiently
recognized by techniques that use some ordering of the nodes\, such as th
e one given by a traversal. \n\nWe study specifically graphs that have an
ordering avoiding some ordered structures that we call *patterns*. Several
well-known classes such as chordal\, bipartite\, interval\, and comparabi
lity graphs have a characterization in terms of forbidden patterns. It is
also known that any class defined by a set of forbidden patterns on three
nodes can be recognized in polynomial time. In a recent paper\, we've char
acterized systematically all the classes defined by sets of forbidden patt
erns (on three nodes). Surprisingly there is a relatively small number of
them\, and they are all well-known. Also\, almost all of them can actually
be recognized in linear time. I will talk about these results and about t
he rich structure of the classes defined by patterns. I will also talk abo
ut on-going work in building bridges between intersection graphs and patte
rns on four vertices.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Pseudoforest Nine Dragon Tree conjecture is true - Benjamin R.
Moore\, University of Waterloo
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210112T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210112T160000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1273
DESCRIPTION:I will give an overview of the following result. Let k and d b
e integers. Let G be a graph with maximum average degree at most 2k + 2d/(
k+d+1). Then G decomposes into k+1 pseudoforests such that one of the pseu
doforests has each connected component containing at most d edges. Here a
pseudoforest is a graph where each component contains at most one cycle\,
and a decomposition is a partition of the edge set into edge disjoint subg
raphs. By a result of Fan et al.\, the bound is best possible for all k an
d d\, even when you ask for one pseudoforest with maximum degree at most d
. This is joint work with Logan Grout.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:Density of C_{-4}-critical signed graphs - Zhouningxin Wang\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210202T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210202T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1289
DESCRIPTION:By extending the notion of indicator to signed graphs\, we sho
w the problem of 4-coloring is captured by the problem of C_{-4}-coloring
(mapping signed graphs to a negative 4-cycle). Moreover\, we extend the no
tion of H-critical to (H\, \\pi)-critical. In this talk\, we prove that an
y C_{-4}-critical signed graph on n vertices\, except for one particular s
igned bipartite graph on 7 vertices and 9 edges\, must have at least 4n/3
edges. As an application to planarity\, we conclude that every signed bipa
rtite planar graph of negative girth at least 8 admits a homomorphism to C
_{-4} and show that this bound is the best possible\, which is relevant to
a bipartite analog of Jaeger-Zhang conjecture.
LOCATION:Salle 3052 and [[ https://u-paris.zoom.us/j/89408898417?pwd=bTNp
VXJXc085MzJabWZ6YVJFRFUwZz09|ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sweeps\, polytopes\, oriented matroids\, and allowable graphs of p
ermutations - Arnau Padrol\, Institut de Mathématiques de Jussieu
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210223T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210223T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1305
DESCRIPTION:A sweep of a point configuration is an ordered partition induc
ed by a linear functional. These orders are at the core of several applica
tions in discrete and computational geometry\, and also appear naturally i
n linear programming. The set of orderings obtained this way is highly str
uctured: isomorphic to the face lattice of a convex polytope. In the plane
\, they were formalized and abstracted by Goodman and Pollack under the th
eory of allowable sequences of permutations\, but a high dimensional gener
alization was missing. I will present an overview of the theory\, discuss
polytopal constructions\, and introduce combinatorial generalizations in t
erms of oriented matroids and allowable graphs of permutations. \n\nThis i
s based on joint work with Eva Philippe.
LOCATION:Online\, via [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJX
c085MzJabWZ6YVJFRFUwZz09 |Zoom]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:Critical subgraphs of Kneser graphs - Matej Stehlik\, G-SCOP
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210225T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210225T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1306
DESCRIPTION:The Kneser graph KG(n\,k) is the graph whose vertex set consis
ts of all k-subsets of an n-set\, with edges joining pairs of disjoint sub
sets. Kneser graphs arise naturally in various contexts\, and play a centr
al role in fractional colouring. In 1978\, Lovasz used tools from algebrai
c topology to prove that KG(n\,k) is (n-2k+2)-chromatic\, proving a long-s
tanding conjecture of Kneser and laying the foundations of topological com
binatorics. Shortly thereafter\, Schrijver defined an induced subgraph SG(
n\,k) of KG(n\,k)\, known as the Schrijver graph\, and showed that SG(n\,k
) is also (n-2k+2)-chromatic. Moreover\, he showed that SG(n\,k) is vertex
-critical\, in the sense that the chromatic number decreases if any vertex
is deleted. However\, Schrijver graphs are in general not edge-critical:
certain edges can be deleted without any effect on the chromatic number. I
n this talk\, I will define an (n-2k+2)-chromatic edge-critical subgraph o
f SG(n\,k)\, thereby sharpening the classical results of Lovasz and Schrij
ver.\n\nJoint work with Tomas Kaiser.
LOCATION:Online\, via [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJX
c085MzJabWZ6YVJFRFUwZz09 |Zoom]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:Self-stabilizing Systems in Spite of High Dynamics - Stephane Devi
smes\, VERIMAG U. Grenoble Alpes
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210302T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210302T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1320
DESCRIPTION:A self-stabilizing distributed system\, regardless its initial
\nconfiguration\, converges within finite time to a configuration from\nwh
ich its behavior is correct. By essence\, self-stabilization is a\nnon-ma
sking fault tolerant approach since the arbitrary initial\nconfiguration c
an be seen as the result of arbitrary transient faults.\n\nIn this talk\,
we will consider self-stabilization in highly dynamic\nnetworks\, i.e.\, n
etworks suffering from unexpected and frequent\ntopological changes. Preci
sely\, assuming that nodes are uniquely\nidentified\, we study the self-st
abilizing leader election problem in\nthree important classes of dynamic n
etworks to obtain solutions\ntolerating both transient faults (such as mem
ory corruption) and\nfrequent topological changes.\n\nWe first study condi
tions under which our problem can be solved and\nthen propose several algo
rithms. Our results reveal that the\nassumption on the knowledge of the nu
mber N of processes is\ncentral. Indeed\, we show that\, as soon as there
is no strong\nguarantees on the temporal connectivity in the network\, the
knowledge\nof the exact value of N is required. Finally\, the convergenc
e time of\nself-stabilizing leader election cannot be bounded in some impo
rtant\ncases. In those cases\, we show that our solutions are speculative\
nsince their convergence time can be still bounded in a subset of more\npr
obable executions.
LOCATION:Online Via [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc0
85MzJabWZ6YVJFRFUwZz09 | ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Computing Pareto Optimal Paths in Weighted Time-Dependent Netwo
rks - Filippo Brunelli\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210316T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210316T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1344
DESCRIPTION:A weighted point-availability time-dependent network is a list
of\ntemporal edges\, where each temporal edge has an appearing time value
\,\na travel time value\, and a cost value. We consider the single source\
nPareto problem in weighted point-availability time-dependent networks\,\n
which consists of computing\, for any destination $d$\, all Pareto\noptima
l pairs $(t\,c)$\, where $t$ and $c$ are the arrival time and the\ncost of
a path from $s$ to $d$\, respectively (a pair $(t\,c)$ is Pareto\noptimal
if there is no path with arrival time smaller than $t$ and\ncost no worse
than $c$ or arrival time no greater than $t$ and better\ncost). We design
and analyse a general algorithm for solving this\nproblem\, whose time co
mplexity is $O(M\\log P)$\, where $M$ is the\nnumber of temporal edges and
$P$ is the maximum number of Pareto\noptimal pairs for each node of the n
etwork. This complexity\nsignificantly improves the time complexity of the
previously known\nsolution. Our algorithm can be used to solve several di
fferent minimum\ncost path problems in weighted point-availability time-de
pendent\nnetworks with a vast variety of cost definitions\, and it can be
easily\nmodified in order to deal with the single destination Pareto probl
em.
LOCATION:[[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6Y
VJFRFUwZz09| ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:Null Decomposition of Graphs - Adrian Pastine\, Universidad Nacion
al de San Luis
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210413T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210413T160000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1367
DESCRIPTION:Given a vector $\\vec{x}$ in the null space of the adjacency m
atrix of a graph $G$\, the support of $\\vec{x}$ are the vertices which co
rrespond to non-zero coordinates of $\\vec{x}$. The support of $G$\, $\\Su
pp{G}$\, is the union of the supports of all vectors in the null space of
its adjacency matrix. The null decomposition of $G$\, first introduced by
Jaume and Molina in 2018\, studies two subgraphs of $G$\, $C_S(G)$\, induc
ed by the vertices in $\\Supp{G}$ and their neighbours\, and $C_N(G)$\, in
duced by the remaining vertices.\n\nIn this talk\, we study the null decom
position of bipartite graphs without cycles of length $0$ modulo $4$. We s
how that $C_S(G)$ contains a unique maximum independent set and that $C_N(
G)$ contains a unique maximum matching. We use the decomposition to show t
hat $\\Supp{G}$ is the intersection of all maximum independent sets of $G$
\, and the union of the unmatched vertices over all maximum matchings. As
an application\, we present an algorithm that finds a sparse basis for the
null space of adjacency matrix of forests in optimal time.\n\nThis talk i
s based on joint work with Daniel Jaume and Gonzalo Molina\, from Universi
dad Nacional de San Luis\, and Martin Safe\, from Universidad Nacional del
Sur.
LOCATION:[[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6Y
VJFRFUwZz09| ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:Colouring with conditions on distances - Daniel Adolfo Quiroz
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210427T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210427T160000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1382
DESCRIPTION:A natural variant of proper vertex colorings\, consists in con
sidering colorings which require different colours for vertices at distanc
e (exactly) p\, for some fixed p. For that type of colouring\, the answer
to the question "how many colours suffice?"\, can depend greatly on the pa
rity of p. In the talk I will give an overview of the results on this type
of colouring\, focusing particularly in the case of planar graphs.
LOCATION:[[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6Y
VJFRFUwZz09| ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:Parking trees - Bérénice Delcroix-Oger
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210511T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210511T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1391
DESCRIPTION:In 1980\, Edelman defined a poset on objects called noncrossin
g\n2-partitions\, made of a partition and a noncrossing partition\, with a
\nbijection linking parts of the same size in both partitions. Studying\nt
his poset\, he proved that the number of noncrossing 2-partitions is\ngive
n by (n+1)^{n-1}. This is also the number of classical\ncombinatorial obje
cts called parking functions. After introducing\nnoncrossing partitions\,
noncrossing 2-partitions and parking\nfunctions\, we will draw the link be
tween parking functions and\nnoncrossing 2-partitions\, describing Edelman
's poset in terms of\nparking functions. Afterwards\, we will (recall and)
use the notion of\nspecies introduced in the early 1980s by Joyal to des
cribe the action\nof the symmetric group on a poset on parking trees. \n\n
This is a joint work with Matthieu Josuat-Vergès and Lucas Randazzo.
LOCATION:[[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6Y
VJFRFUwZz09 |ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:Null Decomposition of Graphs - Adrian Pastine\, Universidad Nacion
al de San Luis
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210525T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210525T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1396
DESCRIPTION:Given a vector $\\vec{x}$ in the null space of the adjacency m
atrix of a graph $G$\, the support of $\\vec{x}$ are the vertices which co
rrespond to non-zero coordinates of $\\vec{x}$. The support of $G$\, $\\Su
pp{G}$\, is the union of the supports of all vectors in the null space of
its adjacency matrix. The null decomposition of $G$\, first introduced by
Jaume and Molina in 2018\, studies two subgraphs of $G$\, $C_S(G)$\, induc
ed by the vertices in $\\Supp{G}$ and their neighbours\, and $C_N(G)$\, in
duced by the remaining vertices.\n\nIn this talk\, we study the null decom
position of bipartite graphs without cycles of length $0$ modulo $4$. We s
how that $C_S(G)$ contains a unique maximum independent set and that $C_N(
G)$ contains a unique maximum matching. We use the decomposition to show t
hat $\\Supp{G}$ is the intersection of all maximum independent sets of $G$
\, and the union of the unmatched vertices over all maximum matchings. As
an application\, we present an algorithm that finds a sparse basis for the
null space of adjacency matrix of forests in optimal time.\n\nThis talk i
s based on joint work with Daniel Jaume and Gonzalo Molina\, from Universi
dad Nacional de San Luis\, and Martin Safe\, from Universidad Nacional del
Sur.
LOCATION:[[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6Y
VJFRFUwZz09| ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:Quantum isomorphism and counting homomorphisms from planar graphs
- David Roberson\, Department of Applied Mathematics and Computer Science\
, Technical University ofDenmark
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210624T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210624T110000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1419
DESCRIPTION:In the "isomorphism game"\, two separated but collaborating pl
ayers attempt to convince a referee that a given pair of graphs are isomor
phic. Any perfect classical strategy for this game corresponds to an isomo
rphism of the graphs. Thus two graphs are said to be "quantum isomorphic"
if the players can win the corresponding isomorphism game using a quantum
strategy\, i.e.\, one in which the players can make local measurements on
a shared quantum state. Surprisingly\, two graphs are quantum isomorphic i
f and only if they admit the same number of homomorphisms from any planar
graph. This can be viewed as a quantum analog of a classical theorem of Lo
vasz stating that two graphs are isomorphic if and only if they admit the
same number of homomorphisms from any graph. A notable aspect of this char
acterization of quantum isomorphism is that its proof relies heavily on to
ols from quantum group theory\, and thus it provides a link between this f
ield and those of quantum information and combinatorics. Additionally\, th
is characterization can be used to show that the Four Color Theorem is equ
ivalent to every planar graph having a homomorphism to a particular graph
on 24 vertices. It remains to be seen whether this last result is actually
interesting.\n\nThis is joint work with Laura Mančinska.
LOCATION:3052 and [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085
MzJabWZ6YVJFRFUwZz09 | ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:Segment representation of planar graphs - Daniel Gonçalves\, CNRS
\, Université de Montpellier
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211005T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211005T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1449
DESCRIPTION:A segment intersection representation of a graph is a set of s
egments such that each vertex corresponds to a segment\, and such that two
segments intersect if and only if the corresponding vertices are adjacent
. There exists several proofs that bipartite planar graphs admit segment i
ntersection representation\, whose segments are either horizontal or verti
cal. Furthermore\, the representation is such that parallel segments corre
spond to an independent set.\n\nIn his PhD Thesis E.R. Scheinerman conject
ured that every planar graph has a segment intersection representation\, a
nd he also conjectured that in the case of 3-colorable planar graphs\, suc
h a representation exists where only 3 slopes appear\, one for each color
class. We proved both of these conjectures\, and we also proved that such
a representation with 4 slopes\, one per color class\, does not always exi
st. This last proof relies on the fact that planar signed graphs are not a
lways four colorable\, for some signed version of colorings. During the ta
lk we will provide the general idea of these proofs.\n\nThese works were j
oint works with J. Chalopin\, L. Isenmann\, and C. Pennarun
LOCATION:[[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6Y
VJFRFUwZz09| ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:On limits-from the finite to the countable and very much uncountab
le graphs - Mirna Džamonja\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211019T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211019T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1476
DESCRIPTION:We survey several different methods of constructing infinite g
raphs out of the families of finite graphs\, among the Fraîssé limits\,
the morasses\, the ultraproducts and the graphons/measurings. Concentratin
g on a couple of them\, we talk about various colourings and the generalis
ed Ramsey theory.
LOCATION:Salle 1007 and via [[https://u-paris.zoom.us/j/89408898417?pwd=bT
NpVXJXc085MzJabWZ6YVJFRFUwZz09| ZOOM]]
END:VEVENT
BEGIN:VEVENT
SUMMARY:On homomorphisms of simple signed graphs of some families - Sagnik
Sen\, IIT Dharwad\, India
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211026T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211026T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1496
DESCRIPTION:A signed graph $(G\, \\sigma)$ is a graph $G$ along with a fun
ction $\\sigma: E(G)\\to\\{+\,-\\}$. A closed walk of a signed graph is po
sitive (resp.\, negative) if it has an even (resp.\, odd) number of negati
ve edges\, counting repetitions. A homomorphism of a (simple) signed graph
to another signed graph is a vertex-mapping that preserves adjacencies an
d signs of closed walks. The chromatic number (this is one of the many not
ions of chromatic number for signed graphs available in literature) of a s
igned graph $(G\, \\sigma)$ is the minimum number of vertices $|V(H)|$ of
a signed graph $(H\, \\pi)$ to which $(G\, \\sigma)$ admits a homomorphism
.\n\nHomomorphisms of signed graphs have been attracting growing attention
in the last decades\, especially due to their strong connections to the t
heories of graph coloring and graph minors. These homomorphisms have been
particularly studied through the scope of the chromatic number. In this wo
rk\, we provide new results and bounds on the chromatic number of several
families of signed graphs (planar graphs\, triangle-free planar graphs\, $
K_n$-minor-free graphs\, and bounded-degree graphs).\n\nJoint work with: B
ensmail\, Das\, Nandi\, Pierron\, Sopena
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chromatic art gallery problems for point and vertex guards - Subir
Kumar Ghosh\, RKMVERI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211109T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211109T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1505
DESCRIPTION:The art gallery problem is to determine the number of guards (
or surveillance cameras) sufficient to cover or see every point in the int
erior of an art gallery. An art gallery can be viewed as a polygon P (with
or without holes) with a total of n vertices\, and guards as points in P.
Any point z in P is said to be visible from a guard g if the line segment
joining z and g does not intersect the exterior of P. This problem was fi
rst posed by Victor Klee in a conference in 1973\, and in the course of ti
me\, it has become an important problem in computational geometry with ext
ensive applications to surveillance of buildings like airport terminals\,
railway stations etc. A polygon is said to be guarded by a set of chosen g
uards if every interior point of P is visible from some guard within the g
uard set.\n\nChromatic art gallery problems arise from applications in are
as like landmark-based robot navigation and wireless networks. One such pr
oblem is the weak-conflict free guarding of polygons\, where the objective
is to colour a chosen guard set S for P using the minimum number of colou
rs such that each point within P sees at least one guard from S with a uni
que colour. Note that the objective here is to minimize the number of colo
rs rather than the number of guards in S. We present an algorithm for weak
conflict-free guarding of P (without holes) where the point guard set is
coloured using only O(log n) colours. If the guards are allowed to place o
nly on vertices of P\, the corresponding algorithm for weak conflict-free
vertex guarding problem uses O(log^2 n) colours. This algorithm uses funne
l structures of weak visibility polygons for placing coloured guards. \n\n
Finally\, we discuss a few open problems on weak conflict-free guarding of
P\nfor both point and vertex guards.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hitting and packing squares - Marco Caoduro\, G-Scop
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211130T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211130T150000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1544
DESCRIPTION:Let $\\mathcal{S}$ be a family of (not necessarily axis parall
el) squares in the plane. The \\emph{transversal number} of $\\mathcal{S}$
\, denoted by $\\tau(\\mathcal{S})$\, is the minimum number of points need
ed to hit all the squares in $\\mathcal{S}$\, and the \\emph{independence
number} of $\\mathcal{S}$\, denoted by $\\nu(\\mathcal{S})$\, is the maxim
um number of pairwise disjoint squares in $\\mathcal{S}$.\n\nClearly\, $\\
tau(\\mathcal{S})$ is at least $\\nu(\\mathcal{S})$. We prove that $\\tau(
\\mathcal{S}) \\leq 10 \\nu(\\mathcal{S})$ and present a family where $\\t
au(\\mathcal{S}) = 3\\nu(\\mathcal{S})$.\n\nDuring the talk\, we will sket
ch the proof of the main result and remark how to extend our approach to f
amilies of rectangles with \\emph{bounded aspect ratios}.\n\nThis is joint
work with András Sebő.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Of points and lines - Laurent Beaudou\, HSE
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211214T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211214T160000
DTSTAMP;VALUE=DATE-TIME:20220119T060300Z
UID:1562
DESCRIPTION:Given n points in the Euclidean plane\, they are either all co
llinear or define at least n distinct lines. This result is a corollary of
the Sylvester-Gallai theorem. Its combinatorial generalization was proven
by de Bruijn and Erdös in the forties. In 2008\, Chen and Chvátal descr
ibed a generalization of the notion of a line to any metric space and conj
ectured that the same result remains true in that framework. Since then\,
a growing community of researchers has been investigating this question. I
t remains open for metric spaces and even for those specific metric spaces
generated by graphs. In this talk\, we shall see a broad overview of the
state of research on the matter: results and (many!) remaining open questi
ons.
LOCATION:Salle 1007
END:VEVENT
END:VCALENDAR