Source-linked AI summary
Characterizations and Complexity of Minimum Forward and Integer Cycle Bases
Gabor Riccardi, Niels Lindner
TL;DR
The paper tackles open questions about the structure and complexity of integral and forward cycle bases. It characterizes when relevant forward bases exist, proves hardness and minor-closedness results, and obtains the complete criterion that K_n is opt-in exactly for n ≤ 7.
Problem
The paper addresses unresolved complexity and structural questions for minimum-weight integral and forward cycle bases, including existence and optimization within restricted basis classes.
Method
The paper combines structural characterizations, polynomial-time constructions and tests, an L-reduction for hardness, and forbidden-minor analysis with a recursive recognition algorithm.
Results
K_n is opt-in if and only if n ≤ 7; additionally, forward fundamental bases are unique when they exist, while minimum-weight forward weakly fundamental bases are APX-hard.
Takeaways & Limitations
Opt-in graphs form a minor-closed family characterized by finitely many forbidden minors, and forward-basis existence can be decided through structural conditions.
Takeaways & Limitations
The hardness reduction requires metric weights, and the forbidden-minor characterization is non-constructive until the forbidden-minor set is determined.
Abstract
from arXiv · showhide
The cycle space of a directed graph is generated by a cycle basis, where, in general, cycles are allowed to have both forward and backward arcs. In a forward cycle, all arcs must follow the given direction. Several open questions remain regarding the complexity of the minimum cycle basis problem, in particular the minimum-weight integral cycle basis problem, and the minimum-weight weakly and strictly fundamental forward cycle basis problems. In this paper, we address these open questions. First, we study the existence, structure, and computational complexity of minimum-weight forward cycle bases. We give a complete structural characterization of digraphs that admit weakly fundamental (and hence integral) forward cycle bases. We further provide a characterization when a strongly connected digraph admits a forward fundamental cycle basis, proving that such a basis exists if and only if the set of directed cycles has cardinality equal to the cycle rank; in this case, the basis is unique. Lastly, we show that while minimum-weight forward fundamental cycle bases can be found in polynomial time whenever they exist, the minimum-weight forward weakly fundamental cycle basis problem is APX-hard via an L-reduction from the minimum-weight weakly fundamental cycle basis problem on digraphs with metric weights. Second, we introduce opt-in graphs, i.e., the family of graphs for which minimum cycle bases are integral for any weight function. We show that this family is minor-closed and hence, by the Robertson-Seymour theorem, is characterized by a finite set of forbidden minors, so that the opt-in recognition problem is solvable in polynomial time. Lastly, we present an algorithm to check whether a graph is opt-in, and if not, to identify which of its minors belong to the set of forbidden minors. Applying this algorithm, we show that the complete graph $K_n$ is opt-in if and only if $n \leq 7$.
1 Introduction
The paper addresses unresolved structural and computational questions about integral and forward cycle bases, motivated by their role in graph optimization. It develops characterizations, complexity results, and an opt-in graph framework for understanding when minimum cycle bases are integral.
- Motivation: Cycle bases compactly represent graph cycles and influence optimization applications including periodic scheduling, electrical network analysis, and pathway modeling.The choice of basis can significantly affect computational efficiency.
- Open questions: The minimum-weight integral cycle basis problem remains an open computational complexity question.
- Open questions: Forward cycle bases are less understood, despite established existence criteria and polynomial-time algorithms for general minimum-weight forward cycle bases.Prior work also showed their usefulness in branch-and-cut formulations and established forward integral bases for certain transit networks.
- Contributions: The paper studies forward-basis existence and complexity, opt-in graphs, forbidden minors, and algorithms for recognizing opt-in structure.Sections 3–7 cover forward-basis characterizations, APX-hardness, opt-in graphs, forbidden-minor properties, and recognition.
- Novelty: The article extends a conference paper, with the APX-hardness result and Sections 5–7 identified as new content.
2 Preliminaries and basic notions
The preliminaries define directed graphs, walks, paths, cycles, cycle spaces, and several nested classes of cycle bases. They also introduce forward cycles and separability, then use block decompositions and directed ear decompositions as structural tools.
- Directed graphs and walks: A directed walk follows the graph’s arc directions, while an undirected walk may traverse each arc either forward or backward; directed paths and cycles impose distinct vertex restrictions.A directed cycle is a closed directed walk whose vertices, except the first and last, are distinct.
- Cycle spaces: The cycle space is a vector subspace generated by cycle incidence vectors, and its dimension is the cycle rank µ(D).Incidence-vector coordinates record forward traversal as 1 and backward traversal as −1.
- Classes of cycle bases: Cycle bases are classified as directed, undirected, integral, weakly fundamental, or fundamental, with fundamental ⊆ weakly fundamental ⊆ integral ⊆ undirected ⊆ directed.These classes are defined through field bases, integer combinations, orderings with unique arcs, or spanning-forest constructions.
- Forward arcs: For a cycle vector, an arc is forward or backward according to the sign of its coordinate, and C ≥ 0 means every supported arc is forward.The set F(D) denotes the directed cycles of D.
- Forward cycle bases: A forward cycle basis is a cycle basis whose cycles are all directed, and forward bases can themselves have the same directed, undirected, integral, weakly fundamental, or fundamental classifications.
- Separability and blocks: A separable digraph has a vertex whose deletion destroys weak connectivity; its maximal non-separable subgraphs are blocks whose cycle spaces decompose as a direct sum.Cycle bases for the whole digraph can be assembled from corresponding bases of its blocks.
- Ear decompositions: Directed ear decompositions build a digraph from an initial directed cycle by successively adding directed ears, and strongly connected digraphs admit such decompositions.The decomposition has t = µ(D) stages and can be computed in O(min(|V(D)|, µ(D)) · (|V(D)| + |A(D)|)) time.
3 Results on the existence of forward cycle bases
The section characterizes when digraphs admit forward cycle bases, especially weakly fundamental and fundamental bases, and gives polynomial-time recognition and construction procedures. It also identifies the maximum possible number of directed cycles in a basis.
- Weakly fundamental forward cycle bases: A digraph admits a forward weakly fundamental cycle basis exactly when every block is strongly connected or a single arc.This condition is equivalent to admitting forward integral, undirected, and directed cycle bases.
- Weakly fundamental forward cycle bases: Every strongly connected digraph has a forward weakly fundamental cycle basis, constructible from a directed ear decomposition.The construction adds one basis cycle for each ear after the initial strongly connected subgraph.
- Maximum numbers of directed cycles: A maximum-directed-cycle basis contains at most the sum of the cycle ranks of the strongly connected components, and a weakly fundamental basis attaining this bound can be constructed.The construction replaces componentwise fundamental bases with forward weakly fundamental bases while preserving the componentwise maximum.
- Proof strategy: The proof that forward fundamental bases are unique uses the fact that nonnegative cycle-space elements lie in the cone generated by directed cycles, with integer coefficients available for integer vectors.Comparing chord coordinates forces the coefficients in the directed-cycle representation to be 0 or 1, yielding a single fundamental cycle.
- Fundamental forward cycle bases: A strongly connected digraph admits a forward fundamental cycle basis if and only if |F(D)| = µ(D), and then F(D) is the unique forward cycle basis.The condition equates the number of directed cycles with the cycle rank.
- Fundamental forward cycle bases: Forward fundamental cycle-basis existence and construction are decidable in polynomial time whenever the block condition holds.The algorithm first checks the block structure, constructs a forward weakly fundamental basis, and tests strict fundamentality; uniqueness certifies non-existence when the test fails.
4 APX-hardness of the Minimum-Weight Forward Weakly Fundamental Cycle Basis Problem
The section establishes the complexity of minimum-weight forward weakly fundamental cycle bases through a lifting-based L-reduction. The problem is APX-hard, including for metric and uniform weights, while the forward fundamental case is polynomial whenever a basis exists.
- Fundamental bases: A minimum-weight forward fundamental cycle basis, if it exists, can be computed and its nonexistence certified in polynomial time.Such a basis is unique, so optimization is immediate once existence has been determined.
- Reduction: The reduction replaces every arc with its reverse, creating a strongly connected counterpart with directed 2-cycles for the original arcs.Each added reverse arc receives the original arc's weight, and the transformed graph has polynomial size.
- Reduction: Any cycle basis of the original digraph can be lifted to a forward cycle basis of the transformed graph.The lifting uses directed counterparts of original cycles together with the family of directed 2-cycles.
- Reduction: The lifting construction preserves weak fundamentality and changes the total weight by an additive constant independent of the original basis.Conversely, a forward weakly fundamental basis containing the 2-cycles can be projected back to a weakly fundamental basis of the original digraph without losing optimality.
- Hardness: APX-hardness persists for metric or uniform weights in the minimum-weight forward weakly fundamental cycle basis problem.The result is obtained via an L-reduction from the non-forward problem, whose APX-hardness is known even for uniform weights.
5 Integrality of Minimum Cycle Bases
This section introduces opt-in graphs, whose minimum cycle bases remain integral under every edge-weight assignment. It proves minor closure, polynomial-time recognition, and a constructive route to integral minimum bases on such graphs.
- Opt-in graphs: Opt-in graphs are those for which every minimum directed cycle basis has the same weight as a minimum integral cycle basis under every edge-weight assignment.The property does not depend on arc orientation and is therefore a property of the underlying undirected graph.
- Algorithmic consequence: A greedy minimum cycle basis algorithm with fixed lexicographic arc tie-breaking returns an integral basis on every opt-in graph.This yields a polynomial-time method for solving the minimum integral cycle basis problem on opt-in graphs.
- Structural characterization: The class of opt-in graphs is minor-closed, so it has a finite characterization by forbidden minors.The finite forbidden-minor characterization follows from the Robertson–Seymour theorem.
- Minor closure: Edge deletion, vertex deletion, and edge contraction preserve the opt-in status relationship needed to prove minor closure.For edge deletion, assigning the deleted edge a sufficiently large weight forces minimum-basis selection to remain in the smaller graph.
- Recognition: Opt-in versus opt-out recognition is solvable in polynomial time.The existence of a finite forbidden-minor set supplies the complexity consequence, although its explicit identification is non-constructive in the general argument.
6 Basic results for graphs in X
The section identifies structural restrictions on minimal opt-out graphs and derives properties of the unique non-integral minimum cycle bases that witness them. These graphs are highly constrained: they are 2-connected, simple, and have minimum degree three.
- Forbidden minors: Proving that a graph belongs to X requires showing both opt-out behavior for one weight assignment and opt-in behavior for every proper deletion or contraction minor.The general polynomial-time recognition guarantee is non-constructive because it presupposes knowledge of the forbidden-minor set.
- Structural properties: Every graph in X is 2-connected and has minimum degree 3.Cut vertices decompose the cycle space across blocks, while vertices of degree at most two contradict minimality under deletion or contraction.
- Witnessing bases: Under strictly metric weights, every minimum-weight directed cycle basis consists entirely of chordless cycles.Replacing a cycle containing a chord with one of the two chord-split cycles yields a strictly cheaper basis.
- Structural properties: Every graph in X is simple.Parallel arcs would force an associated basis arc to occur in only one cycle, contradicting the structural requirements for a minimal opt-out graph.
- Witnessing bases: Each graph in X admits strictly metric weights with a unique, non-integral minimum directed cycle basis consisting only of chordless cycles.Strict metricity is necessary for the weight vector witnessing a unique non-integral minimum basis.
7 Determining membership in X
The paper develops a recursive algorithm for deciding membership in X, using domination certificates and parity-based candidate augmentation. Applying these methods classifies complete graphs and finds explicit opt-out examples.
- Algorithmic framework: The recursive algorithm decides whether a graph is opt-in or opt-out by determining membership in X.It uses a refined domination test and recursively constructs candidate certificates.
- Certificates: A graph is certified outside X when every non-integral cycle basis dominates a vector that is dominated by a convex combination of integral basis vectors.The certificate generalizes the role of the all-two vector and is checked through a domination linear program.
- Recursive parity-based domination test: The recursive parity dichotomy augments a candidate either by adding twice an arc vector or by adding the incidence vector of an undirected cycle.Even degree parity ensures that when the arc augmentation is unavailable, a simple cycle supplies the next candidate.
- Algorithmic framework: The refined domination test correctly decides whether a 2-connected simple graph is opt-out or not in X.Finite termination follows by restricting the search to bounded integral vectors, while column generation uses minimum cycle basis computations.
- Classification of complete graphs: K_n is opt-in exactly when n ≤7, while K_8 is opt-out and yields an eight-vertex graph with a non-integral minimum-weight cycle basis.The K_8-derived example has total weights 2490 for the unique non-integral minimum basis and 2491 for the minimum integral basis.
- Classification beyond complete graphs: The method also finds graphs in X from searches starting at P_7,2, whereas P_5,2 is opt-in.These results extend the classification beyond complete graphs to generalized Petersen graphs.
8 Conclusion and future directions
The paper resolves several existence and complexity questions for forward cycle bases and introduces opt-in graphs to study universally integral minimum cycle bases. It characterizes complete graphs up to K_7, while leaving the broader forbidden-minor structure open.
- Forward cycle bases: Forward weakly fundamental cycle bases are characterized by a simple block-structure condition, while forward fundamental bases in strongly connected digraphs exist exactly when directed-cycle count equals cycle rank.When a forward fundamental basis exists, it is unique, and existence and construction are decidable in polynomial time.
- Forward cycle bases: The minimum-weight forward weakly fundamental cycle basis problem is APX-hard, whereas the complexity of minimum-weight integral cycle bases remains open.The APX-hardness follows via an L-reduction from the non-forward problem with metric weights.
- Opt-in graphs: Opt-in graphs are graphs whose minimum cycle bases are integral for every edge-weight assignment, and this family is minor-closed.The Robertson–Seymour theorem therefore implies a finite forbidden-minor characterization and polynomial-time recognition.
- Opt-in graphs: An algorithm tests opt-in membership and identifies forbidden minors; applying it proves that K_n is opt-in if and only if n ≤ 7.A search seeded at the generalized Petersen graph P7,2 also found additional forbidden minors.
- Future directions: Beyond complete graphs, the forbidden-minor set X is not fully determined, and no useful structural characterization of X is currently known.The paper identifies this unresolved characterization as its primary open problem.