BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Google Inc//Google Calendar 70.9054//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
DESCRIPTION:Graphes seminar of IRIF
NAME:Graphes
REFRESH-INTERVAL:PT4H
TIMEZONE-ID:Europe/Paris
X-WR-CALDESC:Graphes seminar of IRIF
X-WR-CALNAME: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: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:20191207T110301Z
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:20191207T110301Z
UID:417
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:20191207T110301Z
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:Simple Intrinsic Simulation of Cellular Automata in Oritatami Mole
cular Folding Model - Nicolas Schabanel\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191210T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191210T160000
DTSTAMP;VALUE=DATE-TIME:20191207T110301Z
UID:976
DESCRIPTION:The Oritatami model was introduced by Geary et al (2016) to st
udy the computational potential of RNA cotranscriptional folding as first
shown in wet-lab experiments by Geary et al (Science 2014). In Oritatami m
odel\, a molecule grows component by component (named beads) into the tria
ngular and folds as it grows. More precisely\, the δ last nascent beads a
re free to move and adopt the positions that maximizes the number of bonds
with the current structure. This dynamics captures the essence of cotrans
criptional folding to a considerable extent\, where an RNA sequence folds
upon itself into complex shapes and functions while being synthesized (tra
nscribed) out of its template DNA sequence.\n\nThe Oritatami model was pro
ven that it is capable of efficient Turing universal computation by Geary
et al (2018) thanks to a quite complicated construction that simulates Tur
ing machines via tag systems. We propose here a simple Oritatami system wh
ich intrinsically simulates arbitrary $1$D cellular automata. Being intrin
sic\, our simulation emulates the behavior of the cellular automata in a r
eadable way and in time linear in space and time of the simulated automato
n. Furthermore\, the number of bead types needed is quite modest (182 as o
pposed to 542)\, and the delay δ is 2 (instead of 3). The length of the
transcript is also only quadratic in the size of the cellular automata: $O
(rQ^{2(2r+1)}\\log Q)$ for a cellular automata with $Q$ states and radius
$r$ (whose size is thus $O(Q^{2r+1}\\log Q)$). \n\nOur construction relie
s on the development of new tools which are simple enough that we believe
that some simplification of them may be implemented in the wet lab. Our co
nstruction has been implemented and will be soon freely downloaded for tes
ting.\n\nJoint work with Daria Pchelina (ENS Paris)\, Shinnosuke Seki (UEC
Tokyo) and Yuki Ubukata (NTT Data Corp\, Japan)
LOCATION:Salle 3052
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:20191207T110301Z
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:20191207T110301Z
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
END:VCALENDAR