wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Socialist graphs
        
(Message started by: Aryabhatta on Sep 20^th, 2004, 10:38pm)

Title: Socialist graphs
Post by Aryabhatta on Sep 20^th, 2004, 10:38pm

Let G be a simple undirected connected graph with the value 0 assigned to each vertex except a dictator vertex D, which has the value 1. The pair (G,D) is called socialist if each vertex of G can be made to have ~~an even~~ a value divisible by 3 by repeated application of the following process: Pick any edge of G and increment the values of the endpoints of that edge by 1.

Given a graph G and a dictator D, give an algorithm to decide if (G,D) is socialist.

[EDIT] Modified the post to replace even by multiple of 3 [/EDIT]

Title: Re: Socialist graphs
Post by towr on Sep 20^th, 2004, 11:38pm

::[hide]Isn't it always impossible?
The sum over the values of all vertices begins odd (1+k*0=1), and at each step you increase it by 2, so it will never be even as it would be when all vertices are even.[/hide]::

Title: Re: Socialist graphs
Post by baudolino on Sep 21^st, 2004, 7:19am

How about comunist graphs?

Let G be a simple undirected connected graph with the value 0 assigned to each vertex except a dictator vertex D, which has the value 1. The pair (G,D) is called comunist if each vertex of G can be made to have an even value by repeated application of the following process: Pick any VERTEX of G, say v, and increment the values of the vertices adjacent to vertex v by 1. (The value at v is not changed.)

Given a graph G and a dictator D, give an algorithm to decide if (G,D) is comunist.

Title: Re: Socialist graphs
Post by Grimbal on Sep 21^st, 2004, 8:43am

I looks like solving a linear equation in ([bbz]/2)ⁿ.

Title: Re: Socialist graphs
Post by Aryabhatta on Sep 21^st, 2004, 10:04am

You are right towr. I modified the post so that each value should now be a multiple of 3.

Sorry about that, i was trying to reduce the amount of typing and ended up botching the problem itself. :-[

Title: Re: Socialist graphs
Post by baudolino on Sep 21^st, 2004, 12:59pm

An algorithm, probably not optimal, for the modified version (where the value of each vertex is a multiple of 3) is as follows.
Since only the values mod 3 matters, we consider the values be to in Z/3Z. Given (G,D), the idea is to construct a NFA over an alphabet {z} (consisting of 1 element) that models this problem. The states are all possible assignments of values from Z/3Z to each of the vertices of G. The non-deterministic delta function associates to any state [and the symbol z,] all the possible states obtained by applying the rule in the problem. That is, given an edge, it increases mod 3 the values in the endpoints of the edge, and leaves all other values unchanged. The initial state in NFA is the state corresponding to the initial case, in which vertex D has value 1 and all other vertices have value 0. The final state is the one with 0s in all states. The problem is now to determine where the language accepted by this NFA is nonempty.
Determining whether the language accepted by NFA is nonempty is straightforward when you consider the associated boolean matrix M. This matrix M has order n x n , where n is the number of states in the NFA. The entry (i,j) in M is 1 when there is a symbol (a string of length 1) in the alphabet that takes the state i into state j, and 0 if there is no such symbol. Consider all the powers of matrix M. (Remember to use boolean operations (1+1=1) when computing the powers of M.) Starting from a certain power, this sequence of powers will be periodic, so there are a finite number of possible powers of M. Consider two 1 x n vectors v_S and v_F: v_S corresponds to the initial state (the j-th entry in v_S is 1 if j is the starting state, and is 0 otherwise), and v_F corresponds to the final states (the j-th entry in v_F is 1 if j is a final state, and is 0 otherwise). The language accepted by the NFA is nonempty if and only if there is a power of M, say M^k, such that v_S * M^k *(v_F)^transpose = 1. Since there is a finite number of powers of M, all is finite.

Title: Re: Socialist graphs
Post by baudolino on Sep 21^st, 2004, 1:06pm

Correction in the definition of M. The entry (i,j) in M is 1 when there is a string of length 0 or 1 in the alphabet that takes the state i into state j, and 0 if there is no such string.

Title: Re: Socialist graphs
Post by Aryabhatta on Sep 21^st, 2004, 2:57pm

on 09/21/04 at 12:59:54, baudolino wrote:

<snip>
The states are all possible assignments of values from Z/3Z to each of the vertices of G.
<snip>
Since there is a finite number of powers of M, all is finite.

Yes, finite but exponential (in number of vertices) or worse. If n is the number of vertices and m is the number of edges I think we can give an O(n+m) algorithm (assuming neighbouring vertices and edges of any given vertex can be found in constant time).

Title: Re: Socialist graphs
Post by baudolino on Sep 21^st, 2004, 3:25pm

or like Gimbal said, solve a system of linear equations in Z/3Z.

Let V be the number of vertices of graph G and E be the number of edges of G. Label the vertices from 1 through V and the edges from 1 through E. Define an array I of length V by I[j]=1 if j=D, and I[j]=0 otherwise. If 1<=e<=E, define an array A_e of length V by A_e[j]=1 if vertex j is one of the 2 endpoints of edge e and A_e[j]=0 otherwise. The problem is equivalent to finding an algorithm for solving in Z/3Z the equation I + \sum_{e=1}^{E} n_e * A_e =0, where n_e are in Z/3Z. This is a system of V equations in E unknowns with coeffcients in Z/3Z.

Assume that each operation (addition, muliplication) in Z/3Z is counted as a unit operation. Using Gaussian elimination, the complexity of solving the system is O(V^2 * E). Since E is in O(V^2), the complexity is O(V^4).

Title: Re: Socialist graphs
Post by Aryabhatta on Sep 21^st, 2004, 3:57pm

on 09/21/04 at 15:25:42, baudolino wrote:

like Gimbal said, solve a system of linear equations in Z/3Z.

Yes that works and is a pretty elegant solution I think. In fact, it works for the communist graph problem and a host of other such similar problems (Example: google for the lights out puzzle, or look at the locks and switches puzzle in the cs forum here). But for the specific case of the socialist graph problem, we can do better (like in the case of the locks and switches problem). Maybe we can do the same with the communist graph problem too...

Title: Re: Socialist graphs
Post by Aryabhatta on Sep 22^nd, 2004, 3:36pm

I guess it is too early for a hint. Feel free to ignore this :)
:
[hide]

The choice of the dictator vertex does not matter.
Trees and n-D cubes are examples of un-socialist graphs...

[/hide]
:

Title: Re: Socialist graphs
Post by Aryabhatta on Sep 24^th, 2004, 8:29am

More examples of un-socialist graphs
:[hide]

Chessboards of any size (i.e nxn grids), the graph appearing in the utilities puzzle (K33). Cycles with even number of edges.

[/hide]:

Title: Re: Socialist graphs
Post by baudolino on Sep 24^th, 2004, 12:35pm

examples of socialist graphs:

[hide]Any graph that contains an odd-length cycle connected to D[/hide]

Title: Re: Socialist graphs
Post by Aryabhatta on Sep 24^th, 2004, 2:02pm

Right baudolino! Since G is a connected graph, you don't have to explictly mention connectivity to D.

Once we can prove that those are the only socialist graphs, we should have an algorithm.

Title: Re: Socialist graphs
Post by baudolino on Sep 24^th, 2004, 7:51pm

G connected. G socialist iff G has an odd cycle.

Ore direction: (try drawing a figure) If G has an odd cycle, it has a subgraph consisting of an odd cycle and a tail connecting one node in the cycle with vertex D. Numbers will be assigned to the edges of the subgraph as follows. Start along the tail from D until the tail connects with the odd cycle, and consider the edges along the way. Starting with a 2, assign 2s and 1s alternatively to these edges. Consider the last edge in this tail and say the number assigned to it is y. Assign 1s and 2s alternatively to the edges of the odd cycle, so that the y is assigned to the two edges of the cycle where the cycle connected with the tail. Now, for any edge apply the rule t times, where t is the number assigned to the edge. In the resulting subgraph, the number in the vertices are all 0.
The remaining direction: Consider a graph with no odd cycles. The vertices of such a graph have coloring with 2 colors, so that any 2 adjacent vertices have different colors. Think of such a coloring as an assignment of +'s and -'s to the vertices. Say the vertex v is assigned sign sign(v). Consider the invariant I = Sum sign(v)*n(v), where the sum runs over all vertices, n(v) is the number assigned at the vertex v, and the sum is computed in Z/3Z. I is invariant under the rule. Clearly, I has different values for the initial assignment (1 for vertex D and 0 for all other vertices) and for the final assignment (0 for all vertices), so the initial assignment can not be transformed by a successive application of the rule into the final assignment. Therefore G is not-socialist.

Deciding whether G has an odd cycle (or equivalently a coloring with 2 colors) can be done in O(V+E)

A similar proof works in general (for any initial assignment and Z/3Z replaced by Z/dZ, where d > 1 is a positive odd integer) to prove the following.

G connected graph. Let S be an assignment of numbers from Z/dZ to the vertices of G. Consider the rule, which applied to an edge, increments (in Z/dZ) the values at the two ends of the edge.
(a) If G has an odd cycle, then any two assignments are equivalent under the rule (i.e. one can be obtained from the other by successively applying the rule).
(b) If G has no odd cycles, consider an assignment of +'s and -'s to the vertices so that no two adjacent vertices are assigned the same symbol. If S is an assignment of numbers from Z/dZ to the vertices of G , let I(S) = Sum sign(v) * n(v), as above. Two assignments S and S' are equivalent iff I(S) = I(S').

When d is even, there is a problem when the numbers are assigned to the 3 edges adjacent to the vertex where the odd cycle connects with the tail. The two edges on the cycle need to be assigned the same number x. If y is the number assigned to the 3rd edge (on the tail), given y, the equation 2x+y=0 in Z/dZ sometimes does not have any solution x.

Title: Re: Socialist graphs
Post by Aryabhatta on Sep 25^th, 2004, 1:29pm

Right baudolino!

A connected graph G is not socialist if and only if G is bipartite (or 2 colourable). Depending on the representation of G, we have efficient algortihms to determine if G is 2-colourable.

Maybe this will give us some interesting properties of the 'related' matrices over [bbf]₃.