Cut-obstacles and robust ear decompositions

Cut-obstacles and robust ear decompositions

-
Martin Loebl (Charles U, Prague)
Fine Hall 224

A directed cycle double cover (DCDC) of a graph G is a family of cycles of G, each provided with an orientation, such that every edge of G is covered by exactly two directed cycles traversing the edge in the opposite directions.

Cut-type objects called "bridges" are obviously obstructions to the existence of a directed cycle double cover in a graph. Jaeger conjectured in his strengthening of the Szekeres-Seymour Cycle Double Cover Conjecture that bridges are actually the only obstructions.

We study potential obstructions to extending a given set of orientations of edges in a mixed graph that contains both unoriented and oriented edges towards a DCDC. We are surprisingly able to characterise such obstructions for small edge-sets. The bridgeless graphs that can be decomposed into such small sets form a restricted class of the cubic bridgeless graphs, but we show that the existence of subsequent constructions of DCDCs avoiding a single cut-type obstruction in this restricted class of graphs encompasses the general Jaeger's conjecture. This leads us to introduce new notions of (1) cut obstacles in mixed graphs and of (2) reductions of robust networks.

We show that Jaeger's conjecture would follow if a certain subset of robust networks admits a reduction which avoids creating a cut obstacle in each of its consecutive steps.T his adds the problem of characterising well-reducible robust networks to the relatives of the DCDC.

This speaker was supported by the H2020 MSCA RISE grant CoSP GA No. 823748.