Assume a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where each step you take you step on another $1$ and one can shown there that there are matrices that cannot be brought to one component.

Is the decision problem "Can a given matrix $A$ be permuted into at most $k$ components?" in $coNP$ (it is clearly in $NP$ ("YES" certificate is a permutation with $\leq k$ components)) and could it be $NP$-complete (I think this problem is in $NPI$)? $k$ is part of input.

I do not have explicit matrices but a counting argument will easily give you existence.

  • $\begingroup$ "permuted into" by applying the same permutation to the rows and columns, or by applying $\hspace{.81 in}$ possibly-different permutations to the rows and columns? ​ ​ $\endgroup$ – user6973 Sep 19 '16 at 8:19
  • $\begingroup$ different ofcourse $\endgroup$ – T.... Sep 19 '16 at 8:29
  • 2
    $\begingroup$ Do you have an example of a matrix that can't be permuted to have only one component? $\endgroup$ – Andrew Morgan Sep 19 '16 at 12:50
  • $\begingroup$ @AndrewMorgan I dont but it is easy to prove by counting arguments. $\endgroup$ – T.... Sep 19 '16 at 15:48
  • 2
    $\begingroup$ Related MO question with proof of existence of matrices with more than one component: mathoverflow.net/questions/190981/… $\endgroup$ – John Machacek Sep 26 '16 at 14:01

So I give a sketch why the problem is NP-complete. It is very sketchy, which you can take as a sign of trust that you're a smart guy, and not at all a sign of laziness on my part. We will reduce a variant of PLANAR-SAT, where we also require that the edges connecting the variable to its negated and unnegated occurrences form adjacent intervals in the rotation of the vertex of the variable; e.g., if each variable occurs at most once negated.

The matrix will have a small top-left corner that will contain the important information, and many additional rows and columns to impose a structure on this part. In particular, I claim that with properly chosen additional rows and columns, we can achieve that instead of arbitrary permutations, we can restrict the problem to permutations that do not change the rows and can swap only given pairs of adjacent columns, or otherwise the number of components would be larger than $k$.

If we can achieve this, then in the top-left corner we "draw" the graph of our PLANAR-SAT, such that at the heart of each vertex there is a pair of swappable columns. Every other row is constant on these two columns, so only the neighborhood of the vertex is effected. And at this vertex the negated clause-edges come from one side, the unnegated from the other, the swappable column decides which ones are connected to some main component. Therefore, the CNF is satisfiable if and only if all clauses can be connected to the main component.

Since I didn't provide any details about the additional part, it is not clear how $k$ depends on $n$. Can $k$ be kept constant?

| cite | improve this answer | |
  • $\begingroup$ $k$ is not constant but it is an interesting reduction still thinking. $\endgroup$ – T.... Sep 27 '16 at 21:38
  • $\begingroup$ I think it is quite possible that you can make the additional part such that $k$ becomes a constant, if that's what you want. $\endgroup$ – domotorp Sep 28 '16 at 4:11

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.