# minimizing edges problem in a graph

Let \(G, S, C\) be finite sets.

for each \(c\) in \(C\) define a set \(S_c \subset S\)

for each \(g\) in \(G\), define a set \(G_c \subset C\)

consider an assignment function \(f:(g,c) \mapsto s\), where \(f: G \times G_c \to S_c\)

consider the graph with vertices \(S\), and

edges \(E = \{(s1,s2)\, |\, f^{-1}(s1) \cap f^{-1}(s2) \neq \emptyset\}\)

The objective is to minimize the number of edges of the graph where the minimization occurs over all possible assignment functions.

Is there an efficient way to solve this kind of problem or is it NP Hard?

I tried with a MIP (below), and it Gurobi seems to behave like it does for the TSP class of problems. Is there a better way to formulate the MIP?

Does this problem have a name, i.e. something like independent set of a graph or something?

m = Model('Sec')

W = set([(g,s) for g in G for s in S if (sd[s].course_name in gd[g].course_name_set) ] )

GC = [(g,c) for g in G for c in C if c in gd[g].course_name_set ]

Q = [(p,s) for p in P for s in S if sd[s].course_name in pd[p].course_numbers_list ]

SS = [(s1,s2) for s1 in S for s2 in S if s1 < s2]

GSS = [(g,s1,s2) for g in G for (s1,s2) in SS if ( (g,s1) in W and (g,s2) in W ) ]

PS = [(p,s) for p in P for s in S if s in pd[p].secs]

PSS = [(p,s1,s2) for p in P for (s1,s2) in SS if ( (p,s1) in PS and (p,s2) in PS ) ]

x = m.addVars(W, vtype=GRB.BINARY, name='x')

x1 = m.addVars(GSS, vtype=GRB.BINARY, name='x1')

x2 = m.addVars(SS,obj =1, vtype=GRB.BINARY, name='x2')

m.addConstrs( (quicksum(x[g,s] for s in S if (sd[s].course_name == c ) ) == 1 for (g,c) in GC ), name='assign_group_to_sections')

m.addConstrs( (quicksum(x[g,s] for g in G if ( (g,s) in W ) ) <= sd[s].cap for s in S), name='do_not_exceed_section_capacity')

m.addConstrs( (x[g,s1] + x[g,s2] - 1 <= x1[g,s1,s2] for (g,s1,s2) in GSS) , 'c1' )

m.addConstrs( (x1[g,s1,s2] <= x2[s1,s2] for (g,s1,s2) in GSS) , 'c2' )

m.addConstrs( (x2[s1,s2] == 1 for (p,s1,s2) in PSS) , 'c3' )

m.write('seconIze.lp')

m.write('seconIze.mps')

# m.setParam(GRB.Param.Threads,int(sys.argv[2]))

m.optimize()

Please sign in to leave a comment.

## Comments

0 comments