  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 2-core and the 2-core is
2-vertex-connected, 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 NP-complete 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 fixed-parameter-tractable algorithm when parameterized by
clique-width.
