Problems in Signed, Gain, and Biased Graphs

Compiled by Thomas Zaslavsky

This is a fairly miscellaneous and incomplete selection of problems that I happen to have taken an interest in -- not necessarily an active interest. Some are open and some are solved or partially solved -- as for example a problem may have been shown to be NP-complete but special cases could still be solved exactly or algorithmically.

This list is intended to supplement the many problems in the Bibliography. There is just a small amount of duplication.

For the present, the problems here all concern signed graphs. However, many of them have obvious generalizations.

References are as cited in the Bibliography. All the terms employed should be defined in the Glossary. If you find any missing, or if you have suggestions for this page, please notify me!

NOTE: A PostScript version is available. It is slightly more up-to-date and it is the only one that will be maintained and expanded.

I. Direct Measures of Imbalance

(June 8-10 1998)

Imbalance of a signed graph can be measured in numerous ways. Here are problems concerning some measures that have appeared in the literature. The greatest interest has been in the edge version of frustration. (The problems in part II can be regarded as measuring imbalance in a different way.)

  1. Frustration index.
    Symbol: l( ). This is the least number of edges whose deletion results in a balanced subgraph. Its complement is the largest size of a balanced subgraph. It has turned out to be the measure that is most interesting and arises most often.

    1. Calculating l(Sigma).
      Taking the all-negative signing, l(-G) = the smallest size of the complement of a cut (bipartite subgraph). Thus the problem of calculating l(Sigma) -- more precisely, the question "l(Sigma) <= k?" -- is at least as hard as that of finding a maximum-sized cut, which is a standard NP-complete problem. Barahona (1981a, 1982a) proved that the question is solvable in polynomial time if |Sigma| can be embedded in the torus.
      1. Is the question polynomial-time solvable if |Sigma| ranges over graphs embeddable in a fixed genus?
      2. Is it polynomial-time solvable if, while Sigma ranges over all signed graphs, we are given an oracle that tells us:
        1. the genus of |Sigma|?
        2. an embedding of G in its minimal orientable surface?

    2. Most frustrated signatures.
      Let l(G) = max l(G, sigma) over all signings of a graph G.
      1. Maximizing signatures.
        Petersdorf's (1966a) Theorem says that -Kn is the unique maximally frustrated signing of Kn.
        1. Which other graphs attain maximum frustration index when signed all negative?
        2. Among these, for which is the all-negative signing uniquely most frustrated (up to switching, of course)?
        3. In particular, is it true that chordal graphs are among the answers to the first two questions? This is plausible since they have lots of triangles.
        4. Is it possible for a graph with even girth to attain maximum frustration when all negative? (Maybe the real question is whether girth has anything at all to do with whether the all-negative signature maximizes frustration.)
        5. What other kinds of graphs have nice answers to the question of which signings maximize the frustration index?
      2. Estimates and values.
        Akiyama, Avis, et al. (1981a) and Solé and Zaslavsky (1994a) found bounds on l(G) for various kinds of graphs. Brown and Spencer (1971a), followed by Gordon and Witsenhausen (1972a), found asymptotic estimates for complete bipartitie graphs. Brown and Spencer (1971a) found some exact values; also see Sole and Zaslavsky (1994a).
        1. Improve the known bounds, both in general and for special types of graphs.
        2. Improve the asymptotic estimates for complete bipartite graphs.
        3. Find asymptotic estimates for other graphs.
        4. Evaluate l(Kr,s) for r = 6, 7, ..., extending the work of Brown and Spencer (r < 5) and Solé and Zaslavsky (r = 5). (Possibly a linear programming approach would be feasible for small r.)

    3. Restricted frustration index.
      Here we restrict the deleted edges to lie within a prescribed subset A. Let lA(Sigma) be the smallest size of a subset D of A for which l(Sigma-D) = l(Sigma-A) (the smallest frustration index one can hope to achieve). If A = E this is l(Sigma). If A = E-, the negative edge set, it is the "negative-edge frustration index" (proposed recently by Harary; the restricted frustration index is a generalization); here l(Sigma-A) = 0. Note that, unlike the frustration index, these numbers are not switching invariant. They are also NP-complete, at least when A = E- (from Sigma form Sigma' by the negative-subdivision trick; then l(Sigma') = lE-(Sigma)).
      1. For which subsets A does lA(Sigma) = l(Sigma)? (Obviously it is never < l(Sigma).)
      2. In particular, find the signed graphs such that lE-(Sigma) = l(Sigma).
      3. Find a use for lA(Sigma). (It looks as though it ought to be good for something!)

  2. Vertex frustration number (vertex elimination number).
    Symbol: l0( ). This is the smallest number of vertices whose deletion results in a balanced subgraph. Its complement is the largest order of a balanced subgraph. Taking the all-negative case, it becomes the problem of the largest order of a bipartite induced subgraph (whose NP-completeness I don't happen to know).
    1. Can either of l0( ) and l( ) be expressed in terms of the other?
    2. Find any theorems about l0( ).
    3. Find any theorems about l0(G) = max l0(G, sigma) over all signatures sigma.

  3. Cycle indices of imbalance.
    In the early days of signed graph theory there was interest in the proportions of unbalanced polygons, balanced triangles, and balanced polygons weighted according to length (the weights decreasing with length). These were very hard to work with and not particularly natural as measures of imbalance. All I know of is some work of Norman and Roberts (1972a, b) on weighted measures.
    1. Find mathematical properties of the proportion of unbalanced polygons, unbalanced triangles, or unbalanced polygons weighted by length.
    2. Examine the proportion of unbalanced triangles for chordal graphs.
      1. Is it maximized by the all-negative signature (as is the case with complete graphs)?
      2. Are the maximizing signatures unique (up to switching)?

  4. Balancing degree.
    This is Deltab = minimum of Delta(S) over all balancing edge sets S (that is, Sigma - S is balanced). Hoffman's Theorem: There is a function f such that Deltab(Sigma) <= f(least eigenvalue of A(Sigma)) when Sigma is a signed complete graph.
    1. Does this generalize to other (simple) graphs than complete graphs? To all simple graphs?
    2. Find out something about Deltab besides Hoffman's Theorem.

II. Packing and Covering

(June 8-10 1998)

  1. Polygons.
    1. Vertex disjoint.
      1. Find the largest number of vertex-disjoint unbalanced polygons. There is a deep theorem in here somewhere. This includes as the contrabalanced case Lovasz's theorem on the largest number of vertex-disjoint polygons in a graph.
      2. Characterize the signed graphs for which this number is at most k. (The case k = 2 has been solved by Lovász (unpublished).)
    2. Edge disjoint.
      1. Find the largest number of edge-disjoint unbalanced polygons. There is also a deep theorem in here somewhere.
      2. Characterize the signed graphs for which this number is at most k.
      3. Obviously this number is not greater than l(Sigma). When is it equal? (This would be a deep theorem and very interesting.)

  2. Balanced Decomposition.
    A balanced decomposition is a decomposition of Sigma into balanced subgraphs. It is minimal if it decomposes Sigma into the fewest possible subgraphs. (Decomposition means that the edges are partitioned amongst the subgraphs. Every subgraph has all the vertices.) This generalizes bipartite decomposition of unsigned graphs (take all signs negative) and forest decomposition (take all polygons unbalanced). See Zaslavsky (1987b).
    1. Balanced decomposition number.
      The balanced decomposition number is the smallest number of subgraphs in a balanced decompostion. There is a simple formula for signed graphs (Zaslavsky) and a famous formula for contrabalanced biased graphs (Nash-Williams). Find something for all biased graphs.
    2. Connected balanced decomposition number.
      The connected balanced decomposition number (c.b.d.n.) is similar but requires connected subgraphs.
      1. Find out something about the c.b.d.n. of a general signed graph.
      2. Find the c.b.d.n.'s of signings of particular graphs.
      3. Study the maximum c.b.d.n. of all signings of a graph.
      4. Study the c.b.d.n. of a biased graph.
    3. Balanced decomposition degree.
      For a balanced decomposition rho of Sigma into subgraphs Si, let Deltadmax(rho) be the maximum Delta(Si) (where Delta denotes maximum degree of a graph) and let Deltadmin(rho) be the minimum. Over all minimal balanced decompositions rho of Sigma, let Deltadmax(Sigma) = the maximum of Deltadmax(rho). These are measures of the degree to which minimal balanced decompositions divide the edges up equitably among the subgraphs.
      1. What can one say about Deltadmax(Sigma)?
      2. What about the minimum of Deltadmax(rho) over all minimal balanced decompositions of Sigma?
      3. What about the maximum and minimum of Deltadmax(Sigma) over all signings of a particular graph?
      4. It must be obvious that I'm not sure which are the best numbers to look at in order to get a good picture of how equitable a balanced decomposition can be. Figure out which one(s) make the most sense.

  3. Covering by balancing edge sets
    1. Consider the intersection of all maximal balanced subsets. Equivalently (by complementation) this is the union of all balancing edge sets.
      1. When is it empty? (When does the union of all balancing edge sets cover Sigma?)
      2. In general what is it? That is, which edges belong to every maximal balanced subgraph?
    2. What is the smallest number of balancing edge sets required to cover the union of all balancing edge sets? Especially, when these sets cover Sigma.

Best Viewed With Any Browser Created 1998 June 8.

Home page of signed graphs.
E-mail: zaslav@math.binghamton.edu