The Setting
Let be a graph on a finite vertex set . A cycle-and-edge partition of is a partition of into parts, each the edge set of a cycle of or a single edge of , and the decomposition cost of is the least number of parts of such a partition. Such a partition can be assembled from partitions of smaller graphs among which the edges of are shared out, each sitting on a vertex set of its own: the parts of the partitions of the , taken together, form a cycle-and-edge partition of .
The library defines when a graph is supported on a vertex set, what a piece is, and when a sequence of graphs partitions .
Edge Multiplicity in a Sequence of Graphs
The edge multiplicity of a pair of vertices in a finite sequence of graphs on is the number of indices for which is an edge of : (1)✦
The Definition
Definition 1. Let be a vertex set.
A graph on is supported on a finite set when both ends of every edge of lie in : (2)✦
A piece on is a pair of a finite set , the vertex set of , and a graph on supported on : $$P = (A, H), \qquad A \subseteq V \text{ finite}, \qquad H \text{ satisfies \eqref{eq:claim1}}.$$(3)✦
A finite sequence of graphs on partitions a graph on when every pair of vertices has edge multiplicity one in if is an edge of , and zero otherwise: (4)✦
In the paper, the definition reads: a family of subgraphs of partitions when the edge sets assigned to them are pairwise disjoint with union , each carries only its assigned edges, and their vertex sets may overlap.
What Is Checked
The definitions (2), (3) and (4) are stated over graphs on a vertex set , finite subsets of and finite sequences of graphs on , the last through the edge multiplicity (1).