Objective

The proposal submitted and accepted for the Google Summer of Code 2024 at SageMath can be found here: Link.

In the initial proposal, all methods were presented as independent, standalone functions. However, after discussions with my mentor, Prof. David Coudert, we concluded that a more structured approach would be beneficial. Specifically, we decided to create a dedicated class, MatchingCoveredGraph, which would inherit from Graph (itself inheriting from GenericGraph). This class would encapsulate the methods as member functions.

This shift to a class-based approach requires overwriting some methods from both Graph and GenericGraph (that are new to the proposal). The purpose of these overrides is twofold:

• to simplify certain operations in the context of time complexity, and

• to ensure that the resulting graph is always matching covered, that is, an instance of the class MatchingCoveredGraph.

This ensures that any transformations or operations performed on a matching covered graph retain its defining properties.

The primary objective of this project is to implement and formalize the handling of matching covered graphs within SageMath by developing the MatchingCoveredGraph class and refining relevant methods to support these structures. In addition to the core objectives outlined above, there are several supplementary targets associated with this project. A comprehensive and detailed overview of the objectives is as follows:

1. Implementing methods for generating following families of matching covered graphs:

   • Möbius ladder graph

   • Staircase graph

   • Biwheel graph

   • Truncated biwheel graph

2. Implementing methods for generating some small graphs/ digraphs:

   • Bicorn graph

   • Tricorn graph

   • Murty graph

   • Cubeplex graph

   • Twinplex graph

   • KohTindell digraph

3. Implementing methods pertaining to matching:

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

4. Introducing the class MatchingCoveredGraph and implementing methods concerning matching covered graph:

   • Class related methods:

   __init__()	Check if the graph is matching covered.
   __hash__()	Compute a hash for the immutable matching covered graph.
   __repr__()	Return a string representation of the matching covered graph.
   _subgraph_by_adding()	Return the matching covered subgraph containing the given vertices and edges.
   _subgraph_by_deleting()	Return the matching covered subgraph containing the provided vertices and edges.
   _upgrade_from_graph()	Upgrade the given graph to a matching covered graph.

   • Methods concerning barriers and canonical partition:

   canonical_partition()	Return the canonical partition.
   maximal_barrier()	Return the (unique) maximal barrier containing the vertex.

   • Methods concerning bricks, braces and tight cut decomposition:

   bricks_and_braces()	Return the list of (the underlying simple) bricks and braces.
   is_brace()	Check if the matching covered graph is a brace.
   is_brick()	Check if the matching covered graph is a brick.
   number_of_braces()	Return the number of braces.
   number_of_bricks()	Return the number of bricks.
   number_of_petersen_bricks()	Return the number of Petersen bricks.
   tight_cut_decomposition()	Return a tight cut decomposition.

   • Methods concerning removability and ear decomposition:

   add_ear()	Add an ear to the matching covered graph.
   bisubdivide_edge()	bisubdivide an edge k times.
   bisubdivide_edge()	bisubdivide k times edges from an iterable container.
   ear_decomposition()	Return a matching covered ear decomposition computed efficiently.
   is_removable_double_ear()	Check whether the pair of ears form a removable double ear.
   is_removable_doubleton()	Check whether the pair of edges constitute a removable doubleton.
   is_removable_ear()	Check whether the ear is removable.
   is_removable_edge()	Check whether the edge is removable.
   optimal_ear_decomposition()	Return an optimal ear decomposition.
   removable_double_ears()	Return a list of removable double ears.
   removable_doubletons()	Return a list of removable doubletons.
   removable_ears()	Return a list of removable ears.
   removable_edegs()	Return an EdgesView of removable edges.
   retract()	Compute the retract of the matching covered graph.

   • Methods for generating bricks and braces:

   brace_generation_sequence()	Return a McCuaig brace generation sequence of the (provided) brace.
   brick_generation_sequence()	Return a Norine-Thomas brick generation sequence of the (provided) brick.
   is_mccuaig_brace()	Check if the brace is a McCuaig brace.
   is_norine_thomas_brick()	Check if the brick is a Norine-Thomas brick.

   • Overwritten methods:

   add_clique()	Add a clique to the graph with the provided vertices.
   add_cycle()	Add a cycle to the graph with the provided vertices.
   add_edge()	Add an edge from vertex u to vertex v.
   add_edges()	Add edges from an iterable container.
   add_vertex()	Add a vertex to the (matching covered) graph.
   add_vertices()	Add vertices from an iterable container of vertices.
   allow_loops()	Change whether loops are allowed in (matching covered) graphs.
   allows_loops()	Return whether loops are permitted in (matching covered) graphs.
   cartesian_product()	Return the cartesian product of self and other.
   clear()	Make the graph empty removing all associated informations.
   complement()	Return the complement of the graph.
   contract_edge()	Contract an edge from u to v.
   contract_edges()	Contract edges from an iterable container.
   degree_constrained_subgraph()	Return a degree-constrained matching covered subgraph.
   delete_edge()	Delete the edge from u to v.
   delete_edges()	Delete edges from an iterable container.
   delete_multiedge()	Delete all edges from u to v.
   delete_multiedge()	Delete all edges from u to v.
   delete_vertices()	Delete specified vertices form self.
   disjoint_union()	Return the disjoint union of self and other.
   disjunctive_product()	Return the disjunctive product of self and other.
   has_loops()	Return whether there are loops in the matching covered graph.
   has_perfect_matching()	Check whether the graph has a perfect matching.
   is_biconnected()	Check if the matching covered graph is biconnected.
   is_block_graph()	Check whether the matching covered graph is a block graph.
   is_cograph()	Check whether the matching covered graph is cograph.
   is_forest()	Check if the matching covered graph is a forest.
   is_matching_covered()	Check if the graph is matching covered.
   is_path()	Check whether the graph is a path.
   is_subgraph()	Check whether the matching covered graph is a subgraph of other.
   is_tree()	Check whether the matching covered graph is a tree.
   join()	Return the join of self and other.
   lexicographic_product()	Return the lexicographic product of self and other.
   load_afile()	Load the matching covered graph specified in the given file into the current object.
   loop_edges()	Return a list of all loops in the matching covered graph.
   loop_vertices()	Return a list of vertices with loops.
   merge_vertices()	Merge vertices.
   number_of_loops()	Return the number of edges that are loops.
   random_subgraph()	Return a random matching covered subgraph containing each vertex with probability p.
   remove_loops()	Remove loops on vertices in vertices.
   save_afile()	Save the graph to file in alist format.
   strong_product()	Return the strong product of self and other.
   subdivide_edge()	Subdivide an edge k times.
   subdivide_edges()	Subdivide k times edges from an iterable container.
   subgraph()	Return the matching covered subgraph containing the given vertices and edges.
   subgraph_search()	Return a copy of (matching covered) G in self.
   subgraph_search_count()	Return the number of labelled occurrences of matching covered G in self.
   subgraph_search_iterator()	Return an iterator over the labelled copies of (matching covered) G in self.
   tensor_product()	Return the tensor product of self and other.
   to_undirected()	Return an undirected Graph instance of the matching covered graph.
   transitive_closure()	Return the transitive closure of the matching covered graph.
   transitive_reduction()	Return a transitive reduction of the matching covered graph.
   union()	Return the union of self and other.

5. Implementing the Micali-Vazirani algorithm for finding a perfect matching in an undirected unweighted graph in \(\mathcal{O}(|E| \cdot \sqrt{|V|})\)