1
$\begingroup$

Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative solution which is $0/1$ solution but there could be other mixed signs solutions. If we represent $Ax=b$ as a polyhedral inequality $\tilde Ax\leq\tilde b$:

  1. The constraints $\tilde A,\tilde b$ are integer entry matrices.

  2. Every row of $\tilde A$ is $0/-1$ or $0/1$ ($1$ occurs iff $-1$ does not occur) and number of non-zero entries is $2,4,6$ per row.

  3. For $\tilde A$ two $4$-entry rows do not intersect, a $6$-entry row and a $4$-entry row intersect in $3$ columns, and $2$-entry rows intersect with other rows in $1$ or $2$ columns.

  4. For 4-entry rows of $\tilde A$ having no $-1$ the corresponding entries of $\tilde b$ contain $2$, for $2$-entry rows of $\tilde A$ having no $-1$ the corresponding entries of $\tilde b$ contain $1$, and for $6$-entry rows of $\tilde A$ having no $-1$ the corresponding entries of $\tilde b$ contain $4$.

  5. If row of $\tilde A$ is $-1$ replace the rules in 4. by entries of $\tilde b$ having negative $-2$ ,$-1$ and $-4$ correspondingly.

I could not identify a scenario where the system is not totally unimodular but I think it is not $TDI$ or totally unimodular.

Output: Either the unique non-negative solution or certify no solutions exist.

I. Is there a polynomial complexity solution for above problem?

II. If number of $0/1$ solutions is not $\leq1$ is it possible to count number of solutions mod $2$ in polynomial complexity of all non-negative solutions are $0/1$?

$\endgroup$
6
  • $\begingroup$ Isn't $b$ a vector rather than a matrix? Also, if a row of $A$ consists of $0/-1$, the corresponding entry of $b$ cannot be positive. $\endgroup$ Apr 27, 2021 at 19:32
  • $\begingroup$ Yes $b$ is a vector (I wrote matrix since it is $f(t)\times 1$ matrix). Yes $b$ has absolute value $2$. $\endgroup$
    – Turbo
    Apr 27, 2021 at 23:58
  • $\begingroup$ @MaxAlekseyev Do you think it could be totally unimodular? $\endgroup$
    – Turbo
    Apr 28, 2021 at 7:09
  • $\begingroup$ Why not just negate $0/-1$ rows of $A$, and assume it's a $0/1$ matrix? $\endgroup$ Apr 28, 2021 at 7:47
  • $\begingroup$ I was looking at $\leq$ since wrt inequalities you declare polyhedron but yes we can do it $0/1$. $\endgroup$
    – Turbo
    Apr 28, 2021 at 8:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.