Thursday, June 16, 2005

The Unitary graph null weight cycle detection problem

Problem: Given a matrix B of size (n+d)*m, with each element of B from the set {+1,-1,0}, find a column vector x of size m, with each element of x from the set Z+, such that the value of Bx is zero. If no such vector x exists, return and state that no such vector exists. This algorithm should run in logarithmic time in d and polynomial time in n and m.
Some questions and possibly, some answers:
  • B is not a network matrix. Can a network matrix be constructed from B?
  • Can we frame a SAT problem from the matrix, given that it is a graph with {\pm 1 ,0}. Better question: can this problem be posed as a coloring/independent set problem? The intuition for this is the ILP formulation of SAT. From the intuitiuon of SAT, the coloring and independent set naturally follow.
    Postscrip(on 19/6/2005): The unitarization seems to be pretty interesting because
  • Most unform dependences are in the small number range

  • We can possibly reason better with matrices which have all elements in a small range {+1,-1,0}

  • How does this effect memory optimization?
  • No comments: