[Solved]: How hard is this constrained $n$-rooks problem?

Problem Detail: 

I asked this over on math.stackexchange.com, then I found out about this forum.

Suppose you have an $(n\times n)$-chessboard, together with a constraining function $C : n \times n \to 2$ where $C(i,j) = 1$ iff you're allowed to place a rook in the $ij$-square. Consider the problem:

Can $n$ non-attacking rooks be placed on the board in squares allowed by $C$?

Is it NP-Hard?

Here's an alternative formulation: Let $x_1, \dots, x_n$ be elements (integers, say) and $P_1, \dots, P_n$ unary predicates such that $P_ix_j$ can be evaluated in constant time. Is there a permutation $\sigma \in S_n$ such that $P_ix_{\sigma(i)}$ for all $i$?

The equivalence can be seen by letting $C(i,j) = 1$ iff $P_i(x_j)$. Then a placement of rooks yields a witness to the permutation problem by letting $\sigma(i) = j$ iff there's a rook in square $ij$. $\sigma$ is a permutation because all $n$ rooks are placed in a non-attacking arrangement. $P_ix_{\sigma(i)}$ holds because $\sigma(i)=j$ implies theres'a rook in the $ij$ square, which implies $C(i,j) =1$, which, by definition, implies that $P_i(x_j)$.

Asked By : Amit Kumar Gupta

Answered By : D.W.

This problem can be solved in polynomial time, using bipartite matching.

For a bipartite graph with $n$ vertices on the left, corresponding to the $n$ rows, and $n$ vertices on the right, corresponding to the $n$ columns. Include an edge from $i$ to $j$ if $C(i,j)=1$, i.e., if you're allowed to place a rook in the $(i,j)$ square (in the $i$th row and $j$th column). Now check whether there exists a perfect matching of this bipartite graph. This can be done in polynomial time using standard algorithms.

Notice that there exists a perfect matching if and only if there exists a way to place the rooks so they are non-attacking. Each edge in the matching corresponds to a place where a rook should be placed. Two rooks can attack each other only if they share the same row or the same column. A matching cannot have two edges that share the same left-vertex (same row) or same right-vertex (column), which means that any matching containing $n$ edges corresponds to a way to place $n$ rooks so they don't attack each other.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28413

3.2K people like this

 Download Related Notes/Documents