Home  Issues  About JGAA  Instructions for Authors 
Abstract A cycle basis in an undirected graph is a minimal set of simple cycles whose symmetric differences include all Eulerian subgraphs of the given graph.
We define a rooted cycle basis to be a cycle basis in which all cycles contain a specified root edge, and we investigate the algorithmic problem of constructing rooted cycle bases. We show that a given graph has a rooted cycle basis if and only if the root edge belongs to its 2core and the 2core is 2vertexconnected, and that constructing such a basis can be performed efficiently. We show that in an unweighted or positively weighted graph, it is possible to find the minimum weight rooted cycle basis in polynomial time. Additionally, we show that it is NPcomplete to find a fundamental rooted cycle basis (a rooted cycle basis in which each cycle is formed by combining paths in a fixed spanning tree with a single additional edge) but that the problem can be solved by a fixedparametertractable algorithm when parameterized by cliquewidth.

Submitted: February 2017.
Accepted: May 2017.
Final: May 2017.
Published: June 2017.
Communicated by
Dorothea Wagner

Journal Supporters
