1

Nodes have values. Node n's value is denoted n.val. Two or more nodes can have the same value.

  • A node n is a category 0 node or more simply a '0' node iff n.val % 4 == 0.
  • A node n is a 1 node iff n.val % 4 == 1.
  • A node n is a 2 node iff n.val % 4 == 2.
  • A node n is a 3 node iff n.val % 4 == 3.

Nodes can be matched as follows:

  • Two nodes which have the same value cannot be matched.
  • a 0 node can be matched to a 1 node, a 2 node, or a 3 node. We will abbreviate this fact as (0 | 1,2,3 ).
  • a 1 node can be matched to a 0 node, a 2 node, or a 1 node as long as both nodes don't have the same value. Using our abbreviation, ( 1 | 0,1,2 ).
  • a 2 node can be matched to a 0 node, a 1 node, or a 3 node. Abbreviated as ( 2 | 0,1,3 ).
  • a 3 node can be matched to a 0 node, a 2 node, or a 3 node as long as both nodes don't have the same value. Using the abbreviation, ( 3 | 0,2,3 ).

Under these very specific circumstances, can you help me find an efficient maximal matching algorithm?

Whichever maximal matching we achieve, the following statements must be true:

  • If any 0 nodes are unmatched, then all 1, 2, and 3 nodes must be matched.
  • If any 2 nodes are unmatched, then all 0, 1, and 3 nodes must be matched.
  • If any 1 nodes are unmatched, then all 0 and 2 nodes must be matched. Furthermore, all the unmatched 1 nodes must have the same value. It is also possible for some 3 nodes to be unmatched (see next statement).
  • If any 3 nodes are unmatched, then all 0 and 2 nodes must be matched. Furthermore, all the unmatched 3 nodes must have the same value. It is also possible for some category 1 nodes to be unmatched (see previous statement).

I have tried matching in the following manner, but don't know if it is optimal:

While there are unmatched nodes, try first to match all '0' nodes to '1' nodes, then '2' nodes, then '3' nodes in that order. Once you do this, either some '0' nodes are unmatched, in which case you are done, or all '0' nodes are matched, in which case pick the next biggest category which has unmatched nodes and try matching the nodes in that category to nodes in the same or bigger categories. So for example, if you have unmatched '1' nodes, first try to match those to other '1' nodes, then either you have matched all '1' nodes and move on to the next category with unmatched nodes, or you still have some unmatched '1' nodes, in which case you try to match as many '1' nodes as possible to '2' nodes. After this, either all '1' nodes will be matched or all '2' nodes will be matched. Etc...

I just have not found a way to know whether this approach leads to a maximal matching or not.

If you have a better approach or can shed some light on the optimality of my current approach, I would really appreciate it.

josfervi
  • 11
  • 1
  • Your statement "Whichever maximal matching we achieve, the following statements must be true" is kind of strange and unneeded. It is just a reiteration of the matching rules. If any of those statements is violated then it is not a maximal matching, as we can just add the thing which violates those extra rules to increase our matching size. – lPlant Mar 09 '17 at 19:05
  • 1
    Also, A quick google search gives a lot of info on matching in graphs. Perhaps if you added an edge between two nodes if they are allowed to be matched and then use a maximum matching algorithm on the resulting graph – lPlant Mar 09 '17 at 19:11
  • 1
    Maximum matching on general graphs already has efficient algorithms. – Yuval Filmus Mar 09 '17 at 19:57
  • @YuvalFilmus, Thank you for your post. I was wondering if maybe we could come with an even more efficient algo given the circumstances. Best conceivable time complexity would be constant time - an algo based solely on how many nodes there are of each category. I know that's unlikely though. – josfervi Mar 10 '17 at 20:00
  • @IPlant Thanks for your post. Yes, the statements I made follow directly from the matching rules. Just thought I'd add them explicitly as any algo we come up would have to satisfy those statements too. – josfervi Mar 10 '17 at 20:01

0 Answers0