B. Klocker, H. Fleischner, G. Raidl:

"A model for finding transition-minors";

Discrete Applied Mathematics,in press(2020), 1 - 39.

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

Created from the Publication Database of the Vienna University of Technology.