# 3 dimensional matching shortest solution NP-hard?

We have array of arbitrary number of elements - 3d vectors with positive integers components - for example

let a=[ [0,1,2], [1,0,2], [1,1,1], [1,2,0 ], [2,0,1 ], [2,1,0 ] ];


And we want to remove elements from that list, which have duplicate value on i-th index with other elements. This problem can have more than one solution:

• solution with 3 elements: [0,1,2],[1,2,0],[2,0,1]
• solution with 2 elements: [1,0,2],[2,1,0]

As you can see, the solution has this property that each solution element have unique value on i-th index (numbers on i-th position never duplicate) and if we add any other element from array a to that solution we loose this property.

Optimalization: from this wiki aricle I know that finding longest solution is NP-hard problem - but what about finding the shortest solution? Does exists algorithm which not use brute-force to find shortest solution (shortest 3-d matching)?

Here is interactive visualisation in javascript (works in browser, I put it also in wiki article). Here is implementation for find any solution in javascript.

Your problem is NP-complete, even in two dimensions. There is a straightforward reduction from MINIMUM MAXIMAL MATCHING in bipartite graphs:

MINIMUM MAXIMAL MATCHING in bipartite graphs
INSTANCE: a bipartite graph $$G=(V_1\cup V_2,E)$$ with $$E\subseteq V_1\times V_2$$; an integer $$k$$
QUESTION: Does $$G$$ possess a maximal matching $$E'$$ of cardinality at most $$k$$?

(A maximal matching is a subset $$E'\subseteq E$$ such that no two edges in $$E'$$ share a common endpoint, and such that every edge in $$E-E'$$ shares a common endpoint with some edge in $$E'$$.)

NP-hardness of MINIMUM MAXIMAL MATCHING in bipartite graphs has been shown in

M. Yannakakis, F. Gavril
Edge dominating sets in graphs.
SIAM J. Appl. Math. 38, 364–372 (1980)
https://epubs.siam.org/doi/10.1137/0138030

For the reduction, take the vertex set $$V_1\cup V_2$$ as ground set.
For every edge $$\{u,v\}\in E$$ with $$u\in V_1$$ and $$v\in V_2$$, create a corresponding vector $$[u,v]$$.
The equivalence to your problem is immediate.

(And if you insist on 3-dimensional vectors, then you should add a third component to these vectors and fill it with a lot of different values.)

• As is written in wikipedia on top of here and details here, the 2D version of this problem is NOT NP-hard. So the bug is in your answer, in wikipedia, or in my understanding? Please clarify this – Kamil Kiełczewski Mar 8 '19 at 8:42
• You are mixing up two very different questions: In the classical matching problem in the wikipedia, you want to find a matching of MAXIMUM cardinality. In the problem I am using, you want to find a matching that cannot be extended to a larger matching, and this matching should have minimum cardinality. – Gamow Mar 8 '19 at 10:37
• I found M. Yannakakis article here – Kamil Kiełczewski Mar 8 '19 at 11:29