A Dynamic Programming Algorithm To Test A Signed Graph For Balance
Emmanuel Loukakis · International Journal of Computer Mathematics · 2003
A signed graph H =( V , E , σ ) consists of a graph G =( V , E ) together with a sign function σ : E M { m , +}. A fundamental concept in both, the theory and applications of signed graphs is that of balance . We present a new dynamic programming algorithm to detect balance in signed graphs which traverses each line of the signed graph at most once. Furthermore the computer implementation of the proposed algorithm requires three linear arrays of length | V | only, and the graph need not be stored in computer's memory. Thus the proposed algorithm is optimal with respect to both time and space complexities: The line index for balance of an unbalanced signed graph is the minimum number of lines needed to be removed to make the signed graph balanced. Barahona has proved that finding the line index for balance of a signed graph is an NP- complete problem. In this paper, we prove a stronger result, namely that the problem remains NP- complete even when restricted to signed graphs having negative signs only.