1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.