Find a set of maximal matching edges

Question

Consider a connected undirected graph. A matching set of edges on this graph is defined as a set of edges such that no two edges in the set share a common vertex. For example, the left figure denotes a matching set in green, while the right figure denotes a non-matching set in red.

A matching set is said to be maximally matching, or a maximal matching if it is impossible to add another edge of the graph to the matching set. So both examples above are not maximal matching sets, but both of the sets below in blue are maximal matchings. Note that maximal matchings are not necessarily unique. Furthermore, there's not requirement that the size of each possible maximal matching for a graph is equal to another matching.

The goal of this challenge is to write a program/function to find a maximal matching of a graph.

Input

Assume all vertices of the input graph have some consecutive integer numbering starting at any beginning integer value of your choice. An edge is described by an unordered pair of integers denoting the vertices the edge connects. For example, the graph shown above could be described with the following unordered set of edges (assuming the numbering of vertices starts at 0):

[(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]

An alternative way to describe a graph is via an adjacency list. Here is an example adjacency list for the above graph:

[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]

Your program/function must take as input a graph from any source (stdio, function parameter, etc.). You may use any notation desired so long as the no additional non-trivial information is communicated to your program. For example, having an extra parameter denoting the number of input edges is perfectly acceptable. Similarly, passing in an unordered multiset of edges, adjacency list, or adjacency matrix is fine.

You may assume:

1. The graph is connected (e.g. it is possible to reach any vertex given any starting vertex).
2. There is at least one edge.
3. An edge never connects a vertex directly to itself (ex. the edge (1,1) will not be given as input). Note that cycles are still possible (ex.: the above graphs).
4. You may require that the input vertices start at any index (e.g. the first vertex can be 0, 1, -1, etc.).
5. Vertex numbering is sequentially increasing from your chosen starting index (ex.: 1,2,3,4,..., or 0,1,2,3,...).

Output

Your program/function should output a list of edges denoting a maximal matching set. An edge is defined by the two vertices which that edge connects. Ex. output for the left blue set (using the example input vertex ordering):

[(1,4), (2,3), (5,6)]

Note that the order of the vertices are not important; So the following output describes the same matching set:

[(4,1), (2,3), (6,5)]   

Output may be to stdout, a file, function return value, etc.

Examples

Here are a few example inputs (using the adjacency list format). These examples happen to start counting vertices at 0.

Note that no example outputs are given, instead I've included a Python 3 validation code.

[0:(1), 1:(0)]

[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]

[0:(1,2), 1:(0,2,3,4,5), 2:(0,1), 3:(1), 4:(1), 5:(1)]

[0:(1,2), 1:(0,2,3), 2:(0,1,4), 3:(1,4,5), 4:(2,3), 5:(3)]

Validation Python 3 code

Here's a Python 3 validation code which takes in a graph and set of edges and prints out whether that set is maximally matching or not. This code works with any vertex start index.

def is_maximal_matching(graph, edges):
    '''
    Determines if the given set of edges is a maximal matching of graph
    @param graph a graph specified in adjacency list format
    @param edges a list of edges specified as vertex pairs

    @return True if edges describes a maximal matching, False otherwise.
    Prints out some diagnostic text for why edges is not a maximal matching
    '''

    graph_vtxs = {k for k,v in graph.items()}
    vtxs = {k for k,v in graph.items()}

    # check that all vertices are valid and not used multiple times
    for e in edges:
        if(e[0] in graph_vtxs):
            if(e[0] in vtxs):
                vtxs.remove(e[0])
            else:
                print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[0]))
                return False
        else:
            print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
            return False
        if(e[1] in graph_vtxs):
            if(e[1] in vtxs):
                vtxs.remove(e[1])
            else:
                print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[1]))
                return False
        else:
            print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
            return False
        if(e[1] not in graph[e[0]]):
            print('edge (%d,%d): edge not in graph'%(e[0],e[1]))
            return False

    # check that any edges can't be added
    for v in vtxs:
        ovtxs = graph[v]
        for ov in ovtxs:
            if(ov in vtxs):
                print('could add edge (%d,%d) to maximal set'%(v,ov))
                return False

    return True

Example usage:

graph = {0:[1,2], 1:[0,3,4], 2:[0,3], 3:[1,2,4,5], 4:[1,3], 5:[3,6], 6:[5]}
candidate = [(0,1),(2,3)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6),(0,1)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6)]
is_maximal_matching(graph, candidate) // True

Scoring

This is code golf; shortest code wins. Standard loopholes apply. You may use any built-ins desired.

Answer 1

CJam (16 chars)

{M\{_2$&!*+}/2/}

Online demo

This is a greedy approach which accumulates edges which don't have any vertex in common with the previously accumulated edges.

Answer 2

Pyth, 8 bytes

ef{IsTty
       y  power set (gerenate all set of edges)
      t   remove the first one (the first one is
          empty and will cause problems)
 f        filter for sets T satisfying:
     T        T
    s         flatten
  {I          is invariant under deduplicate, i.e. contains no
              duplicating vertices, as the elements represent vertices
e         pick the last one (the power set is ordered from
          smallest to largest)

Try it online!

Specs

• Input: [(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]
• Output: [(1, 4), (2, 3), (5, 6)]

Answer 3

Wolfram Language, 25 22 bytes

Saved 3 bytes thanks to @MartinEnder

FindIndependentEdgeSet

This takes input as a Graph object (defined as Graph[{1<->2,2<->3,1<-3>}] etc.)

Answer 4

Brachylog, 5 bytes

 ⊇.c≠∧

?⊇.cL≠   implicit ? at the beginning;
         ∧ breaks implicit . at the end;
         temporary variable inserted.
?⊇.      input is a superset of output
  .cL    output concatenated is L
    L≠   L contains distinct elements

Try it online!

This is guaranteed to be maximal, since Brachylog searches from the largest subset.

Answer 5

JavaScript (ES6), 67 bytes

let f =
a=>a.map(b=>r.some(c=>c.some(d=>~b.indexOf(d)))||r.push(b),r=[])&&r

let g = a => console.log("[%s]", f(a).map(x => "[" + x + "]").join(", "))
g([[0,1]])
g([[0,1], [0,2], [1,3], [1,4], [2,3], [3,4], [3,5], [5,6]])
g([[0,1], [0,2], [1,2], [1,3], [1,4], [1,5]])
g([[0,1], [0,2], [1,2], [1,3], [2,4], [3,4], [3,5]])

Uses the greedy approach for maximal golfiness.

Answer 6

JavaScript (ES6), 68 66 bytes

f=a=>a[0]?[a[0],...f(a.filter(b=>!a[0].some(c=>~b.indexOf(c))))]:a
f=([b,...a])=>b?[b,...f(a.filter(c=>!c.some(c=>~b.indexOf(c))))]:a

I thought I'd give the recursive approach a go, and by stealing @ETHproduction's set intersection trick I managed to undercut his answer!

I was not the first to misread the original question, and I was about to submit the following recursive function which finds a maximal set of matching edges, rather than a set of maximal matching edges. Subtle difference, I know!

f=a=>a.map(([b,c])=>[[b,c],...f(a.filter(([d,e])=>b-d&&b-e&&c-d&&c-e))]).sort((d,e)=>e.length-d.length)[0]||[]

Simple recursive approach. For each input element, deletes all conflicting edges from the set and finds the maximal set of matching edges of the remaining subset, then finds the maximal result over each input element. Somewhat inefficient for large sets (9-byte speed-up possible).

Answer 7

Jelly, 12 11 bytes

FQ⁼F
ŒPÇÐfṪ

Try it online!

Sample input: [0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]

Sample output: [[1, 4], [2, 3], [5, 6]]

How it works

FQ⁼F    - Helper function, returns 1 if a set of edges is non-matching
F       - Flatten input
 Q      - Remove repeated elements
  ⁼     - Return boolean value. Is this equal to
   F    - The flattened input list

ŒPÇÐfṪ - Main link.
ŒP     - Power set of input list of edges
   Ðf  - Remove all elements which return 1 if
  Ç    - (Helper function) it is a non-matching set
     Ṫ - Get the last element in the resultant list (the longest). 
           Always maximal because it is the longest, so any
           edge added would not be in this list (not matching)