3
$\begingroup$

Problem Statement

Given a list of XY coordinates of length N ( e.g. [(1,2),(3,4)] ) check if there is a subset of coordinates of length S where each coordinate of this subset is diagonal to each other. More details below:

  • Coordinate A and Coordinate B are diagonal to each other if A's XY values are different to B's XY values. For example, (1,1) is diagonal to both (2,2) and (4,3), but not diagonal to (1,2)
  • I don't need to find the specified subset of length S, I only need to say if it's possible or not given the list N
  • If S=1, then every subset is valid.
  • N, S > 0
  • N >= S

For example, given the following list of length N=4 [(1,2), (2,2), (3,1), (4,5)], the following statements are true:

  • [(2,2), (3,1), (4,5)] is a valid subset of length S=3 where every coordinate is diagonal to each other.
  • [(2,2)] is a valid subset of length S=1.
  • [(1,2), (2,2)] is not a valid subset of length S=2.

The Issue

A brute-force approach would be to iterate through all possible subset combinations of length S until we find one that fulfills the criteria from the problem statement. In the worst case scenario when N=S, this would have a complexity of O(n!), which is way too inefficient I think.

Is there an an O(n^2) or better solution to this problem? This was a problem that a colleague came up with, so I'm not sure if this is a known problem with an efficient solution.

$\endgroup$
1
  • 1
    $\begingroup$ Please credit the original source of this problem. Where did you encounter it? Can you link to the source? Perhaps you can ask your colleague where they encountered it and what the context or motivation for the problem is. $\endgroup$
    – D.W.
    Sep 6 at 5:10
3
$\begingroup$

One way to solve this optimally is to model it as a maximum cardinality matching problem in a bipartite graph whose two parts consist of the occupied rows $r_i$ and the occupied columns $c_i$, where the edge $r_ic_j$ is present whenever $(c_j, r_i)$ appears in the input. A matching in this graph having $k$ edges maps a subset of $k$ rows to $k$ distinct columns, which is the same as choosing $k$ pairwise diagonal coordinate pairs from the input. Iff the largest possible matching has at least $S$ edges, the answer is YES.

Each input coordinate pair increases the number of occupied rows and columns by at most 1 each, so there are at most $n$ occupied rows and at most $n$ occupied columns. There are just $n$ edges (thanks Inuyasha Yagami for noticing this), so solving the problem using the $O(|E|\sqrt{|V|}))$-time Hopcroft-Karp algorithm will take $O(n^{1.5})$ time.

$\endgroup$
2
  • 1
    $\begingroup$ There are only $n$ edges in the graph, right? So, your algorithm should be better. $\endgroup$ Sep 7 at 10:15
  • $\begingroup$ @InuyashaYagami: You're right, thanks! I'll edit in a moment. $\endgroup$ Sep 7 at 10:20
2
$\begingroup$

The problem can be solved in $O(n^2 \log n)$ time by reducing the problem to the maximum independent set problem on claw-free graphs.

Reduction: For every XY coordinate $(x_i,y_i)$ in the list, create a vertex $v_i$ in the graph $G$. Two vertices $v_i = (x_i,y_i)$ and $v_j = (x_j,y_j)$ share an edge if and only if $x_i = x_j$ or $y_i = y_j$. Now, the problem is to simply find an independent set (or stable set) of size S in $V$. Also, note that the graph is claw-free. The proof is simple, as follows:

For the sake of contradiction assume that there is a claw in the graph. That is, there are four vertices $\{v_1,v_2,v_3,v_4\}$ and the subgraph spanned by these vertices only contain the edges: $(v_1,v_2), (v_1,v_3),$ and $(v_1,v_4)$. Without loss of generality, assume that $x_1 = x_2$. Then $x_1$ must not be the same as $x_3$ and $x_4$; otherwise there would be an edge $(v_2,v_3)$ or $(v_2,v_4)$ in the graph. Therefore, $y_1 = y_3$ and $y_1 = y_4$. In that case, there would be an edge between $v_3$ and $v_4$. It contradicts that $\{v_1,v_2,v_3,v_4\}$ forms a claw.

Solution: On the claw-free graphs, the maximum independent set problem can be solved in polynomial time. The current best polynomial-time algorithm is due to Nobili and Sassano. Here is the published and the arxiv version of the paper. The running time of the algorithm is $O(n^2 \log n)$.

$\endgroup$

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.