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

<p>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$.</p>

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

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

CC BY-SA 3.0
2016-09-27T21:38:06.563Z
$k$ is not constant but it is an interesting reduction still thinking.
Turbo
CC BY-SA 3.0
2016-09-28T04:11:17.190Z
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.
domotorp
CC BY-SA 3.0
2016-09-27T20:43:53.433Z
2016-09-27T20:43:53.433Z
domotorp
<p>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. </p>

<blockquote>
  <p>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.</p>
</blockquote>

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

CC BY-SA 3.0
2016-09-19T08:29:45.603Z
different ofcourse
Turbo
CC BY-SA 3.0
2016-09-19T12:50:26.153Z
Do you have an example of a matrix that can't be permuted to have only one component?
Andrew Morgan
CC BY-SA 3.0
2016-09-19T15:48:35.333Z
@AndrewMorgan I dont but it is easy to prove by counting arguments.
Turbo
CC BY-SA 3.0
2016-09-26T14:01:59.563Z
Related MO question with proof of existence of matrices with more than one component: http://mathoverflow.net/questions/190981/connected-components-0-1-matrices
John Machacek
CC BY-SA 3.0
2016-09-27T04:35:10.627Z
@domotorp thank you edited query. should be at least since YES instances have a short certificate.
Turbo
CC BY-SA 3.0
2016-09-27T16:14:46.103Z
@domotorp corrected (you are right)
Turbo
<cc.complexity-theory><ds.algorithms><complexity-classes><matrices><ramsey-theory>
Complexity involving connected components of 0/1 matrix
Turbo
# Complexity involving connected components of 0/1 matrix

(Asked by: username_0 on 2016-09-19)

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.

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, matrices, ramsey-theory

> **Comments:**
> **username_0**: different ofcourse  
> **username_1**: Do you have an example of a matrix that can't be permuted to have only one component?  
> **username_0**: @AndrewMorgan I dont but it is easy to prove by counting arguments.  
> **username_2**: Related MO question with proof of existence of matrices with more than one component: http://mathoverflow.net/questions/190981/connected-components-0-1-matrices  
> **username_0**: @username_3 thank you edited query. should be at least since YES instances have a short certificate.  
> **username_0**: @username_3 corrected (you are right)  

---

## 1 answers

### Answer by username_3 on 2016-09-27. Score: 2 | Accepted answer

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?

> **Comments:**
> **username_0**: $k$ is not constant but it is an interesting reduction still thinking.  
> **username_3**: 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.  

---

