# Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix consisting of only -1, 0, 1 and it is ''almost total unimodular.'' There is no objective function and the existence of a feasible solution is all I am looking for, I do not even need the solution. Since I am not much familiar with this subject I seek your help on what papers to read and whether based on your experience this can be solved in polynomial time or not.

For a given $$k$$ ($$k \in O(n)$$, $$n$$ is the number of vertices.) I have the following IP and Matrix.

The Simple Matrix (not (-1,0,1)-coefficient matrix yet.):
Minimize:
Subject to:

1. $$\forall i \in [k]: \sum_{j=1}^{2k} x_{i,j}= 2$$
2. $$\forall j \in [2k]: \sum_{i=1}^{k} x_{i, j}= 1$$

3. $$\forall i \in [k]: \sum_{j=1}^{2k} j \times x_{i,j} \le C_i$$ (constant)
4. $$x_{i,j} \in \{0, 1\}$$

Using two $$\le$$ for each $$=$$, the coefficient matrix ($$C$$) is $$7k * 2k^2$$.
Line 1 and 2 describe some kind of permutation. Their corresponding rows in $$C$$ is totally unimodular.
Example k= 2:

+----+----+----+----+----+----+----+----+
| 1  | 1  | 1  | 1  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 1  | 1  | 1  | 1  |
+----+----+----+----+----+----+----+----+
| -1 | -1 | -1 | -1 | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | -1 | -1 | -1 | -1 |
+----+----+----+----+----+----+----+----+
| 1  | 0  | 0  | 0  | 1  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+
| 0  | 1  | 0  | 0  | 0  | 1  | 0  | 0  |
+----+----+----+----+----+----+----+----+
| 0  | 0  | 1  | 0  | 0  | 0  | 1  | 0  |
+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 1  | 0  | 0  | 0  | 1  |
+----+----+----+----+----+----+----+----+
| -1 | 0  | 0  | 0  | -1 | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+
| 0  | -1 | 0  | 0  | 0  | -1 | 0  | 0  |
+----+----+----+----+----+----+----+----+
| 0  | 0  | -1 | 0  | 0  | 0  | -1 | 0  |
+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | -1 | 0  | 0  | 0  | -1 |
+----+----+----+----+----+----+----+----+
| 1  | 2  | 3  | 4  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 1  | 2  | 3  | 4  |
+----+----+----+----+----+----+----+----+


Final Matrix:
To make it (-1,0,1)-coefficeint matrix, I introduce slack variables, replacing $$x_{i,j}$$ with $$j$$ variables $$x_{i,j,p}, 1 \le p \le j$$.

Minimize:
Subject to:

1. $$\forall i \in [k]: \sum_{j=1}^{2k} x_{i,j,1}= 2$$
2. $$\forall j \in [2k]: \sum_{i=1}^{k} x_{i, j,1}= 1$$
3. $$\forall i \in [k], j \in [2k], \forall p \in [j]: x_{i,j,1} = x_{i,j,p}$$

4. $$\forall i \in [k]: \sum_{j=1}^{2k} \sum_{p=1}^{j} x_{i,j,p} \le C_i$$ (constant)
5. $$x_{i,j,p} \in \{0, 1\}$$

Corresponding rows of lines 1, 2, and 3 on $$C$$ are total unimodular.
Example k= 2:

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 1  | 1  | 0  | 1  | 0  | 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 1  | 0  | 1  | 0  | 0  | 1  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| -1 | -1 | 0  | -1 | 0  | 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | -1 | 0  | -1 | 0  | 0  | -1 | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 1  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | -1 | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 1  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | -1 | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 1  | 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | -1 | 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 1  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | -1 | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 0  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | -1 | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | -1 | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 1  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | -1 | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 1  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | -1 | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 1  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | -1 | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 1  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0  | -1 |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | -1 | 0  | 0  | 1  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+


Given this total modularity and simplicity of the last $$k$$ row, is there any hope that this can be solved in polynomial time?

Thank you.