Find the induced matching

savecancel

Have you tried the alternative definition of taking an independent set in the square of the line graph ?

def square(G):
    H = copy(G)
    for u in G:
        H.add_edges([(u, v) for v in G.vertex_boundary(G.neighbors(u, closed=True))])
    return H

def induced_matching(G):
    L = G.line_graph(labels=False)
    return square(L).independent_set()

This gives

sage: G = graphs.PetersenGraph()
sage: induced_matching(G)
[(1, 6), (3, 4), (5, 7)]

EDIT: now method square returns H and not G... EDIT2: now method square is correct.

One solution is to use Knuth's dancing links algorithm which is implemented in Sage. Assuming the vertices of the graph are integers in the range(number_of_vertices), the method below will work:

from sage.combinat.matrices.dancing_links import dlx_solver
def find_matching(G):
    rows = [[a,b] for (a,b,_) in G.edges()]
    dlx = dlx_solver(rows)
    solution = dlx.one_solution(ncpus=1)
    if solution:
        return [rows[a] for a in solution]
    else:
        return None

Then, on the Petersen graph, it gives:

sage: G = graphs.PetersenGraph()
sage: matching = find_matching(G)
sage: matching
[[2, 7], [0, 1], [5, 8], [3, 4], [6, 9]]
sage: G.plot(edge_colors={'red':matching})

Another solution is to reduce the problem to SAT and use Sage SAT solvers or you may also review the ticket I wrote recently about the reduction of dancing links instance to SAT instance.

I'm unaware of anything built in to find the strong matching number. However, it's easy enough to put some code together. Sage is able to look for subraphs with subgraph_search. You can insist that the subgraph is induced as well. The Petersen graph has ten vertices so the strong matching number could be at most 5. The for loop has i run from 1 to 5, the forbidden subgraphs are set to i*graphs.CompleteGraph(2) and then Sage looks for that subgraph.

P = graphs.PetersenGraph()
i=1 #assumes graph has at least one edge
induced_matching = True

while induced_matching == True:
    forbidden_subgraphs = [i*graphs.CompleteGraph(2)]
    for H in forbidden_subgraphs:
        if P.subgraph_search(H,induced=True):
            induced_matching = True
            i += 1
        else:
            induced_matching = False

print("The strong matching number is: ",i-1)

The result in a Sage Notebook is shown below.