Recognizing a class of bicircular matroids (Q2367405)

Let \(G=(V,E)\) be a graph, and let \(P\) be the set of those subsets \(A\) of \(E\) having the property that each component of \(G[A]\) has at most one cycle. Then \(P\) is a collection of independent sets of a matroid on \(E\) which is called the bicircular matroid of \(G\) and is denoted by \(B(G)\). Now, a matroid \(M\) is called bicircular if there exists a graph \(G\) such that \(M=B(G)\). Three main results concerning bicircular matroids are given. First, for a given matroid \(M\) and a graph \(G\) a set of necessary and sufficient conditions is obtained for \(M\) to be a bicircular matroid of \(G\). Second, a polynomial-time algorithm that determines whether a given matroid is the bicircular matroid of a graph in a certain family of graphs has been developed. And third, the complexity result of \textit{V. Chandru}, \textit{C. R. Coulard} and \textit{D. K. Wagner} [Oper. Res. Lett. 4, 75-78 (1985; Zbl 0565.90078)] has been strengthened by proving that the recognition problem for bicircular matroids remains NP-hard for Halin graphs, which is a class of graphs closely related to generalized wheels.