How to find k matching using MATLAB?

I have set of graphs for which i need to find k matchings i.e (2 matchings, 3 matchings,4 matchings etc). Do we have any MATLAB code to find the particular set of Matchings?

[KSSV]

Can you give any pictorial example?

[ANDREW B I]

These are my set of graphs, for each graphs i need to find particular number of matchings like 2 matchings, 3 matchings,4 matchings...etc.

Answer 1

[Nipun]

Hi Andrew,

I understand that you are looking for a toolbox or function to compute k matchings in graphs.

You can compute a max-matching using the Graph Theory toolbox. However there is no subroutine to return all k-matchings given a graph since even counting k-matchings is W[1]-hard for . Refer to this study for more details.

That said, you can try component reduction and extracting k-regular graphs from the original graph.

Hope this helps.

Regards,

Nipun