Finding even subgraphs even faster (Q1671994)

Three graph-theoretical optimization problems are investigated: given an undirected graph and an integer \(k\), the objective of the Undirected Eulerian Edge Deletion (UEED) problem is to decide on the existence of a set \(S\) of at most \(k\) edges such that \(G\setminus S\) is Eulerian, and the objective of the Undirected Connected Odd Edge Deletion (UCOED) problem is to decide on the existence of a set \(S\) of at most \(k\) edges such that \(G\setminus S\) is odd and connected. Finally, if a directed graph is given, we speak about the directed version of UEED -- Directed Eulerian Edge Deletion (DEED). By considering the solution as an independent set of a co-graphic matroid, the authors were able to design algorithms which solve these problems in time \(O(2^{(2+\omega)k}\cdot n^2m^3k^6) + m^{O(1)}\), where \(n = |V (G)|\), \(m = |E(G)|\) and \(\omega\) is the exponent of matrix multiplication.