Page 244 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 244
ALGORITHMIC GRAPH THEORY (MS-54)
want to find only two temporally disjoint paths. On the other extreme, restricting the underlying
graph to be a path, we find a polynomial-time algorithm for a relevant special case while the
problem remains NP-hard in general (for both paths and walks).
Shifting any path to an avoidable one
Matjaž Krnc, matjaz.krnc@upr.si
University of Primorska, Koper, Slovenia
Coauthors: Vladimir Gurvich, Mikhail Vyalyi, Martin Milanicˇ
A vertex v in a graph G is avoidable if every induced path on three vertices with middle vertex
v is contained in an induced cycle. Dirac’s classical result from 1961 on the existence of sim-
plicial vertices in chordal graphs is equivalent to the statement that every chordal graph has an
avoidable vertex. Beisegel, Chudovsky, Gurvich, Milanicˇ, and Servatius (2019) generalized the
notion of avoidable vertices to avoidable paths, and conjectured that every graph that contains
an induced k-vertex path also contains an avoidable induced k-vertex path; they proved the re-
sult for k = 2. The case k = 1 was known much earlier, due to a work of Ohtsuki, Cheung, and
Fujisawa in 1976. The conjecture was proved for all k in 2020 by Bonamy, Defrain, Hatzel, and
Thiebaut. This result generalizes the mentioned results regarding avoidable vertices, as well as
a result by Chvátal, Rusu, and Sritharan (2002) suggested by West on the existence of simplicial
k-vertex paths in graphs excluding induced cycles of length at least k + 3.
In this talk we discuss an adaptation of the approach by Bonamy et al. from a reconfigu-
ration point of view. We say that two induced k-vertex paths are shifts of each other if their
union is an induced path with k + 1 vertices and show that in every graph, every induced path
can be shifted to an avoidable one. We also present an analogous result about paths that are
not necessarily induced, where an efficient reconfiguration sequence relies on the properties of
depth-first search trees.
Model-checking in multilayer graphs
Kitty Meeks, kitty.meeks@glasgow.ac.uk
University of Glasgow, United Kingdom
Real-world networks often involve qualitatively different types of relationships between differ-
ent objects: for example, in order to understand a social network, we can consider both online
and face-to-face contact. Many computational questions we might want to answer about such
systems are intractable unless we have some additional information about the structure. The
different layers typically have different structural properties (for example, face-to-face contact
will be much more influenced by geography than online contact) and this talk will address the
following question: when can we make use of algorithmically useful structure in the individual
layers to solve problems efficiently on the whole system?
242
want to find only two temporally disjoint paths. On the other extreme, restricting the underlying
graph to be a path, we find a polynomial-time algorithm for a relevant special case while the
problem remains NP-hard in general (for both paths and walks).
Shifting any path to an avoidable one
Matjaž Krnc, matjaz.krnc@upr.si
University of Primorska, Koper, Slovenia
Coauthors: Vladimir Gurvich, Mikhail Vyalyi, Martin Milanicˇ
A vertex v in a graph G is avoidable if every induced path on three vertices with middle vertex
v is contained in an induced cycle. Dirac’s classical result from 1961 on the existence of sim-
plicial vertices in chordal graphs is equivalent to the statement that every chordal graph has an
avoidable vertex. Beisegel, Chudovsky, Gurvich, Milanicˇ, and Servatius (2019) generalized the
notion of avoidable vertices to avoidable paths, and conjectured that every graph that contains
an induced k-vertex path also contains an avoidable induced k-vertex path; they proved the re-
sult for k = 2. The case k = 1 was known much earlier, due to a work of Ohtsuki, Cheung, and
Fujisawa in 1976. The conjecture was proved for all k in 2020 by Bonamy, Defrain, Hatzel, and
Thiebaut. This result generalizes the mentioned results regarding avoidable vertices, as well as
a result by Chvátal, Rusu, and Sritharan (2002) suggested by West on the existence of simplicial
k-vertex paths in graphs excluding induced cycles of length at least k + 3.
In this talk we discuss an adaptation of the approach by Bonamy et al. from a reconfigu-
ration point of view. We say that two induced k-vertex paths are shifts of each other if their
union is an induced path with k + 1 vertices and show that in every graph, every induced path
can be shifted to an avoidable one. We also present an analogous result about paths that are
not necessarily induced, where an efficient reconfiguration sequence relies on the properties of
depth-first search trees.
Model-checking in multilayer graphs
Kitty Meeks, kitty.meeks@glasgow.ac.uk
University of Glasgow, United Kingdom
Real-world networks often involve qualitatively different types of relationships between differ-
ent objects: for example, in order to understand a social network, we can consider both online
and face-to-face contact. Many computational questions we might want to answer about such
systems are intractable unless we have some additional information about the structure. The
different layers typically have different structural properties (for example, face-to-face contact
will be much more influenced by geography than online contact) and this talk will address the
following question: when can we make use of algorithmically useful structure in the individual
layers to solve problems efficiently on the whole system?
242
