Ask Your Question

Find the induced matching

asked 2020-04-13 07:28:34 -0500

salam gravatar image

updated 2020-04-13 15:28:38 -0500

An induced matching in a graph G is a set of edges, no two of which meet a common node or are joined by an edge of G; that is, an induced matching is a matching which forms an induced subgraph.

Would you please tell me how I can find the max induced matching in a graph?

edit retag flag offensive close merge delete

4 answers

Sort by » oldest newest most voted

answered 2020-04-13 14:24:27 -0500

tmonteil gravatar image

updated 2020-04-15 17:07:21 -0500

slelievre gravatar image

Here is a suggestion using mixed integer linear programming, see this tutorial for explicit Sage implementation:

  • variables: to each edge $e$ of the graph $G$, we associate a boolean variables $m_e$ (telling whether $e$ belongs to the matching we are looking for)
  • constraints:
    • for each vertex $v$ of $G$, we want $\sum_{e \in N(v)} m_e \leq 1$ where $N(v)$ denotes the set of edges that are adjacent to the vertex $v$
    • for each edge $e$ of $G$, we want $\sum_{f \in N(e)} m_f \leq 1$ where $N(e)$ denotes the set of edges that are adjacent to the edge $e$
  • objective: we want to maximize the sum $\sum_{e\in G} m_e$

If you have any problem in writing this down into Sage code, do not hesitate to ask for details.

edit flag offensive delete link more


@tmonteil, I know how to find the matching number, but I am looking for the induced matching

salam gravatar imagesalam ( 2020-04-13 15:27:15 -0500 )edit

Oh i see, let me write a new answer, based on MILP.

tmonteil gravatar imagetmonteil ( 2020-04-13 19:27:21 -0500 )edit

@tmonteil, Thanks, I think it works, but I do not know how to write the code

salam gravatar imagesalam ( 2020-04-14 10:51:25 -0500 )edit

answered 2020-04-15 05:54:18 -0500

updated 2020-04-19 03:53:05 -0500

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.

edit flag offensive delete link more


Note that this is the same result as the one I obtain with dancing links which is apparently not an induced matching.

Sébastien gravatar imageSébastien ( 2020-04-15 06:32:20 -0500 )edit

Method square was returning G instead of H... I fixed that and the result makes more sense now.

David Coudert gravatar imageDavid Coudert ( 2020-04-16 02:50:27 -0500 )edit

Looks good now!

Sébastien gravatar imageSébastien ( 2020-04-16 03:29:39 -0500 )edit

The strong matching number of the Petersen graph is 3. It looks like you are getting 2. How is your answer [(7,9)] supposed to be interpreted?

dazedANDconfused gravatar imagedazedANDconfused ( 2020-04-16 18:02:52 -0500 )edit

Method square was not correct. Now it's ok.

David Coudert gravatar imageDavid Coudert ( 2020-04-19 03:53:09 -0500 )edit

answered 2020-04-13 21:46:06 -0500

dazedANDconfused gravatar image

updated 2020-04-14 12:29:20 -0500

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
            induced_matching = False

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

The result in a Sage Notebook is shown below.

image description

edit flag offensive delete link more


Please use python3 syntax in your answers.

FrédéricC gravatar imageFrédéricC ( 2020-04-14 03:16:27 -0500 )edit

@dazedANDconfused note that the agorthm used is brute force:

sage: from sage.graphs.generic_graph_pyx import SubgraphSearch
sage: SubgraphSearch??

Hence, it will likely not be able to handle medium-sized graphs.

tmonteil gravatar imagetmonteil ( 2020-04-14 05:09:38 -0500 )edit

The wikipedia page for induced matching that we were referred to says "...even finding a small induced matching of a given size k is unlikely to have an algorithm significantly faster than the brute force search approach of trying all k-tuples of edges.". I've used the Python3 syntax but you can see it doesn't print as you'd expect. I'm using the version of sage in my Linux versions repository. Python 2.7x print avoids that.

dazedANDconfused gravatar imagedazedANDconfused ( 2020-04-14 12:35:54 -0500 )edit

@dazedANDconfused -- regarding syntax, the following works in py2 and py3.

print("The strong matching number is {}".format(i - 1)")
slelievre gravatar imageslelievre ( 2020-04-15 17:03:32 -0500 )edit

answered 2020-04-14 02:52:59 -0500

Sébastien gravatar image

updated 2020-04-14 02:54:07 -0500

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]
        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})

image description

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.

edit flag offensive delete link more


@Sébastien you are showing a matching, not an induced matching, Indeed, since (0,1) and (6,9) are selected, (1,6) should be selected as well in the induced subgraph.

tmonteil gravatar imagetmonteil ( 2020-04-14 05:06:42 -0500 )edit

Oups! I needed to spend more time to understand the definition properly. Then, since we can not expect a perfect matching, it is more difficult to write as a tiling problem. I am now convinced the MILP is the way to go.

Sébastien gravatar imageSébastien ( 2020-04-14 05:32:54 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2020-04-13 07:28:34 -0500

Seen: 154 times

Last updated: Apr 19