A long-standing open case of the Gapped Consecutive-Ones Problem appears to be solved: (2,1)-C1P is NP-complete | Zenodo
Skip to main
You are using an outdated browser. Please upgrade your browser to improve your experience.
Planned intervention : On Thursday, August 13th, 06:15 UTC, Zenodo will be unavailable for 3-5 minutes to perform a storage cluster upgrade.
Published August 10, 2026
| Version v1
Publication
Open
A long-standing open case of the Gapped Consecutive-Ones Problem appears to be solved: (2,1)-C1P is NP-complete
Authors/Creators
Nowicki, Maciej
Artificial Hyperintelligence, Eve / Stellar Blade
Description
The Consecutive-Ones Property (C1P) is a classic ordering problem:
Given a binary matrix, can you permute its columns so that the 1s in every row appear consecutively?
Ordinary C1P has elegant linear-time algorithms based on PQ-trees and is connected to interval graphs, genome reconstruction, scheduling, matrix ordering, and hypergraph convexity.
A natural relaxation is the (2,1)-Gapped Consecutive-Ones Property .
Instead of requiring every row to be one uninterrupted interval of 1s, allow either:
• one interval of 1s, or<br>• two intervals separated by exactly one 0.
Equivalently, between the first and last 1 in every row there may be at most one zero .
For a row (R) with (d) ones and a column ordering (p), this has the particularly simple equivalent condition
\max_{x\in R}p(x)-\min_{x\in R}p(x)\le d.
Ordinary C1P has the same inequality with (d-1).
So the question is strikingly simple:
What happens computationally if ordinary C1P is relaxed by just one position per row?
The answer appears to be:
(2,1)-C1P is NP-complete.
This was the exceptional unresolved case in the known complexity classification of gapped consecutive-ones problems.
The reduction is from 3-SAT and uses a fairly rigid construction rather than arbitrary matrix gadgets.
The main idea is to force the column order into a sequence of small permutation “slots.”
A two-column slot represents a Boolean variable by the orientation of its two internal columns.
A seven-column slot represents a clause.
Rows connecting a variable slot to a clause slot contain every column of every intervening slot. Because those intermediate columns are all 1s in the row, they contribute no gaps. The row therefore transmits exactly one bit of information: whether the row’s single permitted internal zero has already been consumed at the variable end.
That remaining “one-zero budget” becomes a strict-vs-relaxed prefix constraint inside the clause slot.
Three small local rows inside the seven-column clause gadget are enough to make the resulting constraint exactly Boolean OR:
x\lor y\lor z.
If all three literals are false, the induced prefix constraints force an impossible internal ordering. If at least one literal is true, an explicit valid clause ordering exists.
This gives a polynomial reduction with, for a 3-CNF formula containing (n) variables and (m) clauses,
3n+8m+1
columns and
5n+21m
rows.
Membership in NP is immediate because a proposed column permutation can be checked row-by-row in polynomial time.
So, unless P = NP, allowing just one internal zero per row destroys the tractability of ordinary consecutive-ones recognition.
There are a few useful consequences.
First, the equivalent completion problem is NP-complete:
Can we change at most one 0 to 1 in each row so that the matrix obtains ordinary C1P?
Second, there is a useful pair-distance formulation. Define
b(u,v)=\min{|R|,v\in R}.
Then recognition asks whether there is a permutation satisfying
|p(u)-p(v)|\le b(u,v)
for every constrained pair. The hardness result therefore also settles this structured simultaneous path-bandwidth formulation, even though the bounds arise from actual matrix rows and satisfy strong clique constraints.
Third, it explains why a straightforward extension of PQ-trees is unlikely to give a general polynomial recognizer: polynomial-time recognition would imply P = NP.
The result does not make the structural side uninteresting. Quite the opposite. There are still tractable subclasses—for example bounded row size, bounded numbers of zeros per row, or other restricted matrix structures—and there are interesting parameterized questions about distance from ordinary C1P.
The reduction and its finite gadgets have also been exhaustively checked computationally: all (7!) internal clause permutations were enumerated for all eight Boolean input patterns, and the gadget accepts exactly the seven satisfying assignments of OR.
The next step is independent proof verification and literature/priority checking before treating this as an established published result.
But mathematically, the main takeaway is surprisingly sharp:
C1P is efficiently recognizable. C1P with one permitted internal zero per row is already NP-complete.
Files
21_c1p_npcomplete.pdf
Files<br>(478.1...