A Dynamic Programming Algorithm To Test A Signed Graph For Balance (Q4807702)

A signed graph is a graph where every edge is assigned a value `\(-\)' or `\(+\)'. A signed graph \(G\) is balanced if every cycle in \(G\) is positive, i.e. has an even number of negative lines. Equivalently, any two paths between a pair of vertices in \(G\) have the same sign. Equivalently, the vertex set of \(G\) can be partitioned into two disjoint sets called coalitions, one of which may be empty, such that every positive line (edge) joins vertices of the same coalition and every negative line joins vertices of different coalitions. This paper presents a new dynamic programming algorithm to detect balance in signed graphs and which traverses each edge of the graph at most once. The line index for balance of an unbalanced signed graph is the minimum number of edges needed to be removed in order to make the signed graph balanced. Finding the line index for balance of a signed graph is NP-complete even if the graph has only negative signs.