Finding vertex-disjoint cycle cover of undirected graph using the least-squares method

• Date: 3. 11. 2022
• Time: 14:00 - 15:30
• Address:
  Sokolovská 83, Praha
• Room: K3
• Speaker: Jan Lamač

Finding a vertex-disjoint cycle cover (called a 2-factor) of a given undirected graph G consists in finding a set of disjoint cycles which are subgraphs of G and contain all vertices of G. It is well known that a 2-factor of an undirected 2-factorable graph can be found in polynomial time by transforming the problem into a problem of finding a perfect matching in a larger graph. When we prescribe further conditions on this cycle cover (e.g. number of components, minimal cycle length) the problem of finding a 2-factor becomes NP-hard. In the talk we investigate the properties of the least-squares solution of the system of equations with a matrix being the incidence matrix of the given undirected graph G and we propose an algorithm that uses this solution for finding a 2-factor of the graph G.