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

<blockquote>
  <p>MINIMUM MAXIMAL MATCHING in bipartite graphs<br>
  INSTANCE: a bipartite graph <span class="math-container">$G=(V_1\cup V_2,E)$</span> with <span class="math-container">$E\subseteq V_1\times V_2$</span>; an integer <span class="math-container">$k$</span><br>
  QUESTION: Does <span class="math-container">$G$</span> possess a maximal matching <span class="math-container">$E'$</span> of cardinality at most <span class="math-container">$k$</span>?</p>
</blockquote>

<p>(A maximal matching is a subset <span class="math-container">$E'\subseteq E$</span> such that no two edges in <span class="math-container">$E'$</span> share a common endpoint, and such that every edge in <span class="math-container">$E-E'$</span> shares a common endpoint with some edge in <span class="math-container">$E'$</span>.)</p>

<p>NP-hardness of MINIMUM MAXIMAL MATCHING in bipartite graphs has been shown in </p>

<blockquote>
  <p>M. Yannakakis, F. Gavril<br>
  Edge dominating sets in graphs.<br>
  SIAM J. Appl. Math. 38, 364–372 (1980)<br>
  <a href="https://epubs.siam.org/doi/10.1137/0138030" rel="nofollow noreferrer">https://epubs.siam.org/doi/10.1137/0138030</a></p>
</blockquote>

<p>For the reduction, take the vertex set <span class="math-container">$V_1\cup V_2$</span> as ground set.<br>
For every edge <span class="math-container">$\{u,v\}\in E$</span> with <span class="math-container">$u\in V_1$</span> and <span class="math-container">$v\in V_2$</span>, create a corresponding vector <span class="math-container">$[u,v]$</span>.<br>
The equivalence to your problem is immediate.</p>

<p>(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.)</p>

CC BY-SA 4.0
2019-03-08T08:42:17.570Z
As is written in wikipedia on top of [here](https://en.wikipedia.org/wiki/3-dimensional_matching) and details [here](https://en.wikipedia.org/wiki/Matching_(graph_theory)#Bipartite_matching), 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
CC BY-SA 4.0
2019-03-08T10:37:12.453Z
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
CC BY-SA 4.0
2019-03-08T11:29:48.903Z
I found M. Yannakakis [article here](http://cgi.di.uoa.gr/~vassilis/co/dominating-sets.pdf)
Kamil Kiełczewski
CC BY-SA 4.0
2019-03-07T20:18:01.370Z
2019-03-07T20:18:01.370Z
Gamow
<p>We have array of arbitrary number of elements - 3d vectors with positive integers components - for example</p>

<pre><code>let a=[ [0,1,2], [1,0,2], [1,1,1], [1,2,0 ], [2,0,1 ], [2,1,0 ] ];
</code></pre>

<p>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:</p>

<ul>
<li>solution with 3 elements: <code>[0,1,2],[1,2,0],[2,0,1]</code></li>
<li>solution with 2 elements: <code>[1,0,2],[2,1,0]</code></li>
</ul>

<p>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 <code>a</code> to that solution we loose this property.</p>

<p>Optimalization: from this <a href="https://en.wikipedia.org/wiki/3-dimensional_matching" rel="nofollow noreferrer">wiki aricle</a> 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)?</p>

<p><a href="https://jsfiddle.net/Lamik/6z4agLue/embedded/result/" rel="nofollow noreferrer">Here</a> is interactive visualisation in javascript (works in browser, I put it also in wiki article). Here is implementation for find any solution in <a href="https://stackoverflow.com/a/54999617/860099">javascript</a>.</p>

<np-hardness><optimization>
3 dimensional matching shortest solution NP-hard?
Kamil Kiełczewski
# 3 dimensional matching shortest solution NP-hard?

(Asked by: username_0 on 2019-03-07)

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.

**Tags:** np-hardness, optimization


---

## 1 answers

### Answer by username_1 on 2019-03-07. Score: 3 | Accepted answer

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.)

> **Comments:**
> **username_0**: As is written in wikipedia on top of [here](https://en.wikipedia.org/wiki/3-dimensional_matching) and details [here](https://en.wikipedia.org/wiki/Matching_(graph_theory)#Bipartite_matching), 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  
> **username_1**: 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.  
> **username_0**: I found M. Yannakakis [article here](http://cgi.di.uoa.gr/~vassilis/co/dominating-sets.pdf)  

---

