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-incidence matrix of G such that its entries belong to {±1,⋯,±(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)-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)-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)-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)-graph G with n vertices has a zero-sum 3-flow, where the number of vertices of degree four is O(log⁡n). Furthermore, we show that it is NP-complete to determine whether a given (3,4)-semiregular graph has a zero-sum 3-flow.