Algorithm design to assign nodes to graphs

Question

I have a graph-theoretic (which is also related to combinatorics) problem that is illustrated below, and wonder what is the best approach to design an algorithm to solve it.

Given 4 different graphs of 6 nodes (by different, I mean different structures, e.g. STAR, LINE, COMPLETE, etc), and 24 unique objects, design an algorithm to assign these objects to these 4 graphs 4 times, so that the number of repeating neighbors on the graphs over the 4 assignments is minimized. For example, if object A and B are neighbors on 1 of the 4 graphs in one assignment, then in the best case, A and B will not be neighbors again in the other 3 assignments.

Obviously, the degree to which such minimization can go is dependent on the specific graph structures given. But I am more interested in a general solution here so that given any 4 graph structures, such minimization is guaranteed as the result of the algorithm.

Any suggestion/idea of solving this problem is welcome, and some pseudo-code may well be sufficient to illustrate the design. Thank you.

Answer 1

Representation:

You have 24 elements, I will name this elements from A to X (24 first letters). Each of these elements will have a place in one of the 4 graphs. I will assign a number to the 24 nodes of the 4 graphs from 1 to 24.

I will identify the position of A by a 24-uple =(xA1,xA2...,xA24), and if I want to assign A to the node number 8 for exemple, I will write (xa1,Xa2..xa24) = (0,0,0,0,0,0,0,1,0,0...0), where 1 is on position 8.

We can say that A =(xa1,...xa24)

e1...e24 are the unit vectors (1,0...0) to (0,0...1)

note about the operator '.':

• A.e1=xa1
• ...
• X.e24=Xx24

There are some constraints on A,...X with these notations :

Xii is in {0,1} and

Sum(Xai)=1 ... Sum(Xxi)=1

Sum(Xa1,xb1,...Xx1)=1 ... Sum(Xa24,Xb24,... Xx24)=1

Since one element can be assign to only one node.

I will define a graph by defining the neighbors relation of each node, lets say node 8 has neighbors node 7 and node 10

to check that A and B are neighbors on node 8 for exemple I nedd:

A.e8=1 and B.e7 or B.e10 =1 then I just need A.e8*(B.e7+B.e10)==1

in the function isNeighborInGraphs(A,B) I test that for every nodes and I get one or zero depending on the neighborhood.

Notations:

• 4 graphs of 6 nodes, the position of each element is defined by an integer from 1 to 24. (1 to 6 for first graph, etc...)
• e1... e24 are the unit vectors (1,0,0...0) to (0,0...1)
• Let A, B ...X be the N elements.

A=(0,0...,1,...,0)=(xa1,xa2...xa24)

B=...

...

X=(0,0...,1,...,0)

• Graph descriptions:

IsNeigborInGraphs(A,B)=A.e1*B.e2+... //if 1 and 2 are neigbors in one graph for exemple

• State of the system:

L(A)=[B,B,C,E,G...] // list of neigbors of A (can repeat)

actualise(L(A)):
for element in [B,X]
if IsNeigbotInGraphs(A,Element)
L(A).append(Element)
endIf
endfor

• Objective functions

N(A)=len(L(A))+Sum(IsneigborInGraph(A,i),i in L(A))

...

N(X)= ...

Description of the algorithm

1. start with an initial position A=e1... X=e24
2. Actualize L(A),L(B)... L(X)
3. Solve this (with a solveur, ampl for exemple will work I guess since it's a nonlinear optimization problem):

Objective function

min(Sum(N(Z),Z=A to X)

Constraints:

Sum(Xai)=1 ... Sum(Xxi)=1

Sum(Xa1,xb1,...Xx1)=1 ... Sum(Xa24,Xb24,... Xx24)=1

You get the best solution

4.Repeat step 2 and 3, 3 more times.