The complexity of the zero-sum 3-flows

A zero-sum k-flow for a graph G   is a vector in the null-space of the 0,1$0,1$-incidence matrix of G   such that its entries belong to {±1,?,±(k−1)}$\{\pm 1,?,\pm (k-1)\}$. Akbari et al. (2009) [5] conjectured that if G is a graph with a zero-sum flow, then G   admits a zero-sum 6-flow. (2,3)$(2,3)$-semiregular graphs are an important family in studying zero-sum flows. Akbari et al. (2009) [5] proved that if Zero-Sum Conjecture is true for any (2,3)$(2,3)$-semiregular graph, then it is true for any graph. In this paper, we show that there is a polynomial time algorithm to determine whether a given (2,3)$(2,3)$-graph G   has a zero-sum 3-flow. In fact, we show that, there is a polynomial time algorithm to determine whether a given (2,4)$(2,4)$-graph G with n   vertices has a zero-sum 3-flow, where the number of vertices of degree four is O(log?n)$O(\log ?n)$. Furthermore, we show that it is NP-complete to determine whether a given (3,4)$(3,4)$-semiregular graph has a zero-sum 3-flow.