search

math1um / objects-invariants-properties

Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
GNU General Public License v3.0
14 stars 6 forks source link

fix property: matching_covered & variants #585

Open math1um opened 6 years ago

math1um commented 6 years ago

  1. should be renamed is_matching_covered

  2. the definition should be: matching covered iff every edge is in some perfect matching. (so the algorithm would be:

a. find the matching number nu b. check that nu = order/2 (and thus the graph has a perfect matching) c. for each edge vw, let G' be the graph formed by removing vertices v and w d. find the matching number of G': if it isn't nu-1 return False e. if it passes the test for each edge, return True

this definition is in Robin Thomas' lecture notes on matching: http://people.math.gatech.edu/~thomas/TEACH/7510/match.pdf

also used by Lovasz in: Lovász, László. "Ear-decompositions of matching-covered graphs." Combinatorica 3.1 (1983): 105-117.

  1. eliminate the #comment too - this definition is the SAME as 1-factor-covered ( a 1-factor is a perfect matching)

  2. update stored computations of is_matching_covered (these will not be the same - the existing algorithm doesn't capture the above definition).

  3. add a new property: is_generalized_matching_covered

a graph is_generalized_matching_covered iff every edge is in a maximum (so not necessarily perfect) matching. so, for example, C5 is not matching covered (it doesn't have a perfect matching) but is generalized_matching_covered. the matching number is 2, and every edge is in some matching with 2 edges.

nvcleemp commented 6 years ago

I would propose a slightly optimised algorithm. The function matching by default returns a maximal matching. When you compute the matching number using that function and you get a perfect matching, you already have a list of edges which are included in a perfect matching. Next you can proceed as described but just for the edges for which it is not yet known that they are in a perfect matching. In each step you can get new edges which are in a perfect matching. This will greatly reduce the number of times a subgraph has to be created and a matching number needs to be computed.

nvcleemp commented 6 years ago

An even better approach might be to never compute a subgraph. The matching function can handle weighted graphs. You can proceed as I mentioned before, but after the initial matching, mark some egdes as being in a perfect matching. Then pick an edge e that is not yet known to be in a perfect matching. Give it weight 2|E| and all other edges weight 1. If there is a perfect matching containing e, then it function will now have to return it, because it has maximal weight. There might again potentially be new edges, and they should also be marked as already in a perfect matching.

This approach avoids creating subgraphs which is an expensive process.

thenealon commented 6 years ago

The current matching_covered should become is_matching_robust, as-is. (For a robustness reference, see Sudakov; https://people.math.ethz.ch/~sudakovb/robustness-of-graph-properties.pdf )

math1um commented 6 years ago

The existing definition of matching_covered is still a useable concept. The current definition should be renamed matching_robust