1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Kamil Kiełczewski Mar 8 at 8:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Gamow Mar 8 at 10:37
  • $\begingroup$ I found M. Yannakakis article here $\endgroup$ – Kamil Kiełczewski Mar 8 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.