Page 243 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 243
ALGORITHMIC GRAPH THEORY (MS-54)
yields a lower bound on the number of moplexes. Second, as our main structural result, we
show that graphs with at most two moplexes are cocomparability.
So, as the class of connected graphs with at most two moplexes is sandwiched between the
connected proper interval graphs and cocomparability graphs, this leads to the natural question
of whether the presence of at most two moplexes guarantees a sufficient amount of structure to
efficiently solve problems that are known to be intractable on cocomparability graphs, but not
on proper interval graphs. For two such problems, namely GRAPH ISOMORPHISM and MAX-
CUT, we show that they stay hard on the graphs with two moplexes. On the other hand, we
prove that every connected graph with two moplexes contains a Hamiltonian path.
Computing Weighted Subset Transversals in H-free Graph
Matthew Johnson, matthew.johnson2@durham.ac.uk
Durham University, United Kingdom
Coauthors: Nick Brettell, Daniël Paulusma
In graph transversal problems, one seeks, given a graph, to find a small subset of the vertex set
— a transversal — that intersects every subgraph of a specified kind. Examples include vertex
cover, feedback vertex set and odd cycle transversal. In subset versions of the problem, a subset
of the vertex set is also given and the transversal that is found must also intersect this subset. In
weighted versions, a vertex weighting is given and the aim is to find a transversal such that the
sum of the weights of the transversal vertices is small.
These problems are NP-hard in general. We discuss recent work on graph transversal prob-
lems for hereditary graph classes. We will focus in particular on the problems WEIGHTED
SUBSET ODD CYCLE TRANSVERSAL and WEIGHTED SUBSET FEEDBACK VERTEX SET for
graph classes that are H-free. We present new algorithms that lead us to classify the complexity
of the problems except in the cases where H is 2P1 +P3, P1 +P4 or 2P1 +P4. We note that in the
latter two cases the complexity remains open even for the unweighted non-subset versions of
the problem. One interesting aspect of our classification is the discovery that the complexities
of weighted and unweighted versions of SUBSET ODD CYCLE TRANSVERSAL do not coincide
for H-free graphs.
Interference-free Walks in Time: Temporally Disjoint Paths
Nina Klobas, nina.klobas@durham.ac.uk
Durham University, United Kingdom
Coauthors: George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche
We investigate the computational complexity of finding temporally disjoint paths or walks in
temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp.
walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are
temporally disjoint if they never use the same vertex or edge at the same time; otherwise, they
interfere.
We show that on general graphs the problem is computationally hard. The “walk version”
is W[1]-hard when parameterized by the number of routes. However, it is polynomial-time
solvable for any constant number of walks. The “path version” remains NP-hard even if we
241
yields a lower bound on the number of moplexes. Second, as our main structural result, we
show that graphs with at most two moplexes are cocomparability.
So, as the class of connected graphs with at most two moplexes is sandwiched between the
connected proper interval graphs and cocomparability graphs, this leads to the natural question
of whether the presence of at most two moplexes guarantees a sufficient amount of structure to
efficiently solve problems that are known to be intractable on cocomparability graphs, but not
on proper interval graphs. For two such problems, namely GRAPH ISOMORPHISM and MAX-
CUT, we show that they stay hard on the graphs with two moplexes. On the other hand, we
prove that every connected graph with two moplexes contains a Hamiltonian path.
Computing Weighted Subset Transversals in H-free Graph
Matthew Johnson, matthew.johnson2@durham.ac.uk
Durham University, United Kingdom
Coauthors: Nick Brettell, Daniël Paulusma
In graph transversal problems, one seeks, given a graph, to find a small subset of the vertex set
— a transversal — that intersects every subgraph of a specified kind. Examples include vertex
cover, feedback vertex set and odd cycle transversal. In subset versions of the problem, a subset
of the vertex set is also given and the transversal that is found must also intersect this subset. In
weighted versions, a vertex weighting is given and the aim is to find a transversal such that the
sum of the weights of the transversal vertices is small.
These problems are NP-hard in general. We discuss recent work on graph transversal prob-
lems for hereditary graph classes. We will focus in particular on the problems WEIGHTED
SUBSET ODD CYCLE TRANSVERSAL and WEIGHTED SUBSET FEEDBACK VERTEX SET for
graph classes that are H-free. We present new algorithms that lead us to classify the complexity
of the problems except in the cases where H is 2P1 +P3, P1 +P4 or 2P1 +P4. We note that in the
latter two cases the complexity remains open even for the unweighted non-subset versions of
the problem. One interesting aspect of our classification is the discovery that the complexities
of weighted and unweighted versions of SUBSET ODD CYCLE TRANSVERSAL do not coincide
for H-free graphs.
Interference-free Walks in Time: Temporally Disjoint Paths
Nina Klobas, nina.klobas@durham.ac.uk
Durham University, United Kingdom
Coauthors: George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche
We investigate the computational complexity of finding temporally disjoint paths or walks in
temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp.
walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are
temporally disjoint if they never use the same vertex or edge at the same time; otherwise, they
interfere.
We show that on general graphs the problem is computationally hard. The “walk version”
is W[1]-hard when parameterized by the number of routes. However, it is polynomial-time
solvable for any constant number of walks. The “path version” remains NP-hard even if we
241
