Is this problem NP?

[Script Coder]

OUTLINE:
You are given a bipartite graph (separated into A nodes and B nodes). Each node from A has at most N edges to a node in B (There is only ever one edge per pair of vertices). You need to find the "best" d(N) "non-overlapping grouping(s)" (where d(N) is the maximum degree of all vertices in A).

In a grouping every node in A is connected to one node in B. And non-overlapping mean that every edge may only appear in one grouping.

A set of groupings gets a score as follows:
For each node in B (in each grouping) is if the d(B_n)<4:
score+=4-d(B_n)

The best is the groupings that have the lowest score.

MY CURRENT SOLUTION:
Brute force. While really easy to understand and code (given on request), it runs in worst N!^A. Which is incredibly slow even for N=4 and A=40 (This is my test case).

REMARKS:
This could be a type of matching problem, however I could not find anything on it.
Also, if you need me to make anything clearer (or corrected), please let me know. I found the best way to visualise it is to draw a simple example.

QUESTION:
Is this NP or is there a better solution?

Thank you for all help.

[ne555]

> I found the best way to visualise it is to draw a simple example.
Please, draw it.

> You need to find the "best" d(N) "non-overlapping grouping(s)"
> In a grouping every node in A is connected to one node in B
> And non-overlapping mean that every edge may only appear in one grouping.
¿All the groupings must take all the nodes from `A'?
¿How could you make d(N) groupings if you have a node with a lesser degree?

> For each node in B (in each grouping) is the d(Bn)<4:
¿So in a grouping, there can't be more than 3 incident edges on a B node?

[Script Coder]

Thank you for replying and sorry for replying late.

Please, draw it.

http://snag.gy/b0mw9.jpg
In the above image one of the best groupings would be:

	G1	G2	G3
1	i	ii
2	ii	i
3	ii		iii
4	iii	ii	i
5		iii	ii

Where the value in each cell would mean that the number node in A is connected to that node in B in Grouping N.

¿All the groupings must take all the nodes from `A'?

No, however, all every edge must be in one and only one group.

¿How could you make d(N) groupings if you have a node with a lesser degree?

As shown above, some nodes won't appear in some groupings if they have got a lesser degree. (If this becomes problematic when solving, just assume that there are dummy nodes that take their place).

> For each node in B (in each grouping) is the d(Bn)<4:

Sorry the "is" is meant to be an "if"

¿So in a grouping, there can't be more than 3 incident edges on a B node?

What is an "incident edge"?

EDIT:Table corrected

[Mats]

The answer has to be 'probably'. It sure as hell looks NP, but since P = NP is unproven either way, then maybe it's actually just P.

[Script Coder]

^Okay so if it is "probably" NP, what would the most efficient algorithm be to find its solutions?

but since P = NP is unproven either way, then maybe it's actually just P.

Many problems are considered NP even though it is unknown whether or not P=NP or not.

[ne555]

> What is an "incident edge"?
an edge that has the node as endpoint
Consider the grouping

1 ii
2 ii
3 ii
4 ii
5 ii

¿is it legal? ¿what is its penalty?


> For each node in B (in each grouping)
If a node has no edges, ¿does it incur in penalty?
i.e. ¿a grouping has all the nodes in B?

with your example:
G1 = 3+2+3 = 8
G2 = 3+2+3 = 8
G3 = 0(¿4?)+3+3 = 6(¿10?)
total = 22 (¿26?)

[Script Coder]

¿is it legal? ¿what is its penalty?

It is legal, just not optimal.

An optimal solutions is as follows. Say a node in B have degree M and a the d(n) is 4 (where d(N) is the maximum degree of all vertices in A) then the optimum groupings will have either M/d(n) or (M/d(n))+1 edges connected the node B.

If a node has no edges, ¿does it incur in penalty?

This must be take assuming the node is in both A and in B. If in A then it will not influence d(n) (unless there are no edges at all). If it is in B, then in each grouping its optimum number of edges will be 0 or 1 and since all its groupings will have 0 edges it is optimum.

with your example:
G1 = 3+2+3 = 8
G2 = 3+2+3 = 8
G3 = 0(¿4?)+3+3 = 6(¿10?)
total = 22 (¿26?)

I am not sure which example you are referring to, and also do not understand your question, so please forgive any incorrect statements that follow.
What numbers are you adding up, the numbers in the image are just labels for the nodes, and carry no weights.
Also, why are you adding those numbers?

Once again, thank you for your help thus far. I really do appreciate it.

[ne555]

I don't understand how you compute the penalty
> For each node in B (in each grouping) if the d(Bn)<4:
> score+=4-d(Bn)
¿was `4' just an example?

using http://snag.gy/b0mw9.jpg and the groupings that you suggested, ¿what will the penalty, per grouping, per node?

[Script Coder]

¿was `4' just an example?

using http://snag.gy/b0mw9.jpg and the groupings that you suggested, ¿what will the penalty, per grouping, per node?

Oh, you mean that, yes 4 is taken as an example, for a problem with A=4 and B=9 and N=4 (this has no correspondence to the 4 in the penalty). Basically all I needed was a way to rank scores in that example. Now that I think about it, a better representation would be:
score+=min( |d(B_n)-M/d(n)|, |d(B_n)-((M/d(n))+1)|, |d(B_n)-((M/d(n))-1)|)
so in the example, the score would have been (please take note of the corrected error in the table):
Group 1: i appears once =0
ii appears twice = 0
iii appears once = 0
same with group two, and similarly with group 3. Thus it is a perfectly optimal grouping. Of course perfectly optimal groupings may not always exit, thus we need to find one of the most optimal groupings.

I hope I have not frustrated you to much by not being clear, and I would once again like to thank you for your ongoing help in helping me solve this problem.

[Mats]

Can I see the code you have so far?

Also, why are you working on this problem?

[Script Coder]

Can I see the code you have so far?

It is very messy and in python. It also has no comments. It is just a brute force solution trying all possible combinations and scoring them (note the scoring method has not been updated yet) But here it is :

def options(A, start=None, best=-1): #start and best are only there so that I can restart the program at a later point
	max=-1
	if(start==None):
		current=[0]*len(A)
	else:
		current=start
	for B in A:
		if max<len(A[B]):
			max=len(A[B])
	while(next_permutation(A, current)):
		print(current)
		c=(score(A, current, max))
		if(c[0]<best):
			output(c, 'w', current)
			best=c[0]
			print("Best:"+str(best))
		elif(c[0]==best):
			output(c, 'a', current)
			print("1")

def score(A, current, max):
	options=[{} for i in xrange(max)]
	for i, B in zip(xrange(len(current)), A):
		p=get_permutation(current[i], len(A[B]))
		for j,num in zip(xrange(len(A[B])),p):
			if(options[num-1].has_key(A[B][j])):
				options[num-1][A[B][j]].append(B)
			else:
				options[num-1][A[B][j]]=[B]
	ans=0
	for group in options:
		if(group>4):
			ans+=2
		for subject in group:
			if(len(group[subject])<4):
				ans+=4-len(group[subject])
	return(ans, options)
				
def get_permutation(i, N):
	p0, p=[k for k in xrange(1, N+1)], []
	for j in xrange(N-1, 0, -1):
		j_f=reduce(lambda x, y: x*y, [k for k in xrange(1, j+1)])
		c=i/j_f
		i%=j_f
		p.append(p0[c])
		p0=p0[:c]+p0[c+1:]
	p.append(p0[0])
	return(p)
	
def next_permutation(A, p):
	for i, B in zip(xrange(len(p)), A):
		fact=reduce(lambda x, y: x*y, [k for k in xrange(1, len(A[B])+1)])
		p[i]+=1
		if(p[i]==fact):
			p[i]=0
		else:
			return(True)
	return(False)
	
def output(option, mode, current):
	fout=open("ans.txt", mode)
	fout.write("=============================\n")
	fout.write("Score: "+str(option[0])+"\n[")
	for i in current:
		fout.write(str(i)+", ")
	fout.write("]\n")
	for i,group in zip(xrange(len(option[1])), option[1]):
		fout.write("Group "+str(i)+"\n")
		for subject in group:
			fout.write(subject+": ")
			for name in group[subject]:
				fout.write(name+", ")
			fout.write("\n")
	fout.close()
		
values={"0" : ("A","B","C",),
"1" : ("D","C","E","F",),
"2" : ("D","E","G","F",),
"3" : ("B","C","E","F",),
"4" : ("A","D","H","E",),
"5" : ("A","D","I",),
"6" : ("A","D","B",),
"7" : ("A","D","B","H",),
"8" : ("A","D","B","I",),
"9" : ("A","D","J",),
"10" : ("D","B","J",),
"11" : ("A","D","B",),
"12" : ("A","D","I","G",),
"13" : ("D","C","H",),
"14" : ("B","C","F",),
"15" : ("A","D","B",),
"16" : ("D","B","C","E",),
"17" : ("A","D","I",),
"18" : ("A","D","B",),
"19" : ("A","B","E","F",),
"20" : ("A","G","F","J",),
"21" : ("A","E","G","F",),
"22" : ("A","E","G","J",),
"23" : ("A","D","B",),
"24" : ("D","B","C",),
"25" : ("D","C","I",),
"26" : ("A","D","B",),
"27" : ("A","D","I","J",),
"28" : ("A","D","J",),
"29" : ("A","C","I",),
"30" : ("A","D","E",),
"31" : ("A","H","J",),
}		
options(values)

Also, why are you working on this problem?

I like to find myself challenging problems to solve, and this one was the one I came up with for last week.

Any queries and suggestion are more than welcome and greatly appreciated.

[Mats]

I'll put my maths hat on tomorrow and take a look, but I'm unlikely to find a neat algorithm for a faster solution. I find graph theory and related topics are generally really hard! You certainly have found an interesting problem here though...

[Script Coder]

Any help is still appreciated, the solution I am thinking of now would be one that uses a genetic algorithm. However, I am still figuring out how to to the "reproduction" of it.