[Back]

B. Klocker, H. Fleischner, G. Raidl:
"A model for finding transition-minors";
Discrete Applied Mathematics, 283 (2020), 242 - 264.

The well known cycle double cover conjecture in graph theory is strongly related to the compatible circuit
decomposition problem. A recent result by Fleischner et al. (2018) gives a su cient condition for the
existence of a compatible circuit decomposition in a transitioned 2-connected Eulerian graph, which is based
on an extension of the de nition of K5-minors to transitioned graphs. Graphs satisfying this condition are
called SUD-K5-minor-free graphs. In this work we formulate a generalization of this property by replacing
the K5 by a 4-regular transitioned graph H, which is part of the input. Furthermore, we consider the decision
problem of checking for two given graphs if the extended property holds. We prove that this problem is NP-
complete and xed parameter tractable with the size of H as parameter. We then formulate an equivalent
problem, present a mathematical model for it, and prove its correctness. This mathematical model is then
translated into a mixed integer linear program (MIP) for solving it in practice. Computational results show
that the MIP formulation can be solved for small instances in reasonable time. In our computations we
found snarks with perfect matchings whose contraction leads to SUD-K5-minor-free graphs that contain
K5-minors. Furthermore, we veri ed that there exists a perfect pseudo-matching whose contraction leads
to a SUD-K5-minor-free graph for all snarks with up to 22 vertices.
Keywords: Transition Minor, Cycle Double Cover, Compatible Circuit Decomposition, Integer
Programming

http://dx.doi.org/10.1016/j.dam.2020.01.006

https://publik.tuwien.ac.at/files/publik_288240.pdf