A linear-time algorithm for computing the intersection of all odd cycles in a graph (Q674917)

The authors consider the problem of finding edges and vertices in a graph \(G\) that are contained in every odd cycle of \(G\). This problem is partially motivated by a fixed-parameter version of two well-known NP-complete problems. A characterization of the intersection of all odd cycles in a graph \(G\) is proposed by using the intersection of the \(T\)-spans of all monochromatic edges (\(T\) is a spanning tree of \(G\)) and the partial subgraph of \(G\) obtained by removing all monochromatic edges. Using this result, a linear-time algorithm is then exhibited. An application of this algorithm is given to a satisfiability problem, namely the minimum mono-valued 2SAT.