On Decompositions, Generation Methods and related concepts in the theory of Matching Covered Graphs

[janmenjayap]

Problem Description

Matchings and perfect matchings have received considerable attention in graph theory as well as in other related domains (such as, but not limited to, algorithms and optimization). There still remain many open problems — such as Barnette’s conjecture, Berge-Fulkerson conjecture, and so on — due to which it continues to remain an active area of research. For problems concerning perfect matchings, it is well-known that it suffices to solve them for matching covered graphs (that is, those connected graphs wherein each edge belongs to some perfect matching).

The objective of this issue is to implement efficient algorithms pertaining to the canonical partition, tight cut decomposition, dependency relations, (optimal) ear decomposition, brick and brace generation methods and related concepts in the theory of matching covered graphs, and to make all of these available freely to students, educators as well as researchers all across the world. This issue has been inspired by the book of C.L. Lucchesi and U.S.R. Murty: PERFECT MATCHINGS: A THEORY OF MATCHING COVERED GRAPHS ¹.

Proposed Solution

To create a new class: MatchingCoveredGraph, in the module sage.graphs.matching_covered_graph and to implement the following functions:

• maximal_barrier(): Return the (unique) maximal barrier of the (matching covered) graph containing the (provided) vertex.
• canonical_partition(): Return the canonical partition of the (matching covered) graph.
• tight_cut_decomposition(): Return <a maximal set of laminar nontrivial tight cuts, the vertex set partition as the shores wrt these cuts> of the (matching covered) graph.
• bricks_and_braces(): Return the list of (underlying simple graph of) the bricks and braces of the (matching covered) graph.
• number_of_bricks(): Return the number of bricks.
• number_of_braces(): Return the number of braces.
• number_of_petersen_bricks(): Return the number of Petersen bricks (the bricks the underlying simple graph of which is isomorphic to graphs.PetersenGraph()).
• is_brick(): Check if the (matching covered) graph is a brick.
• is_brace(): Check if the (matching covered) graph is a brace.
• is_removable_edge(): Check if the edge of the (matching covered) graph is removable.
• removable_edges(): Return the list of all removable edges of the (matching covered) graph.
• is_removable_doubleton(): Check if the pair of edges constitute a removable doubleton in the (matching covered) graph.
• removable_doubletons(): Return the list of all removable doubletons.
• retract(): Compute the retract of the (matching covered) graph.
• ear_decomposition(): Return an efficient or an optimal ear decomposition (aka a list of ears/ a list of graphs).
• is_b_invariant_edge(): Check if the edge is b-invariant.
• is_thin_edge(): Check if the edge is thin.
• is_strictly_thin_edge(): Check if the edge is strictly thin.
• is_mccuaig_brace(): Check if the brace is a McCuaig brace.
• is_norine_thomas_brick(): Check if the brick is a Norine-Thomas brick.
• brick_generation_sequence(): Return a Norine-Thomas brick generation sequence of the (given) brick.
• brace_generation_sequence(): Return a McCuaig brace generation sequence of the (given) brace.

The following two functions are proposed to be implemented under the class: Graph in sage.graphs.graph:

• is_matching_covered(): Check if the graph is matching covered.
• is_bicritical(): Check if the graph is bicritical.

We adopt the notations and definitions as described in the aforementioned book of C.L. Lucchesi and U.S.R. Murty ¹.

Alternatives Considered

NA

Additional Information

This implementation is a part of the project: link.

cc: @dcoudert.

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

---

References

1. C.L. Lucchesi, U.S.R. Murty. Perfect Matchings: A Theory of Matching Covered Graphs. Algorithms and Computation in Mathematics. Springer Cham, 1st edition, 2024, doi: 10.1007/978-3-031-47504-7.