Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a very sparse undirected graph. I need to decompose it into n sets of edges. In each of these sets, all edges are independent (no two edges share any vertices). Every edge in the graph is contained in exactly one of these sets.

The goal here is to minimize n. Note that this problem is somewhat different from the classic largest independent edge set problem in that EVERY edge must go into SOME set. We just want as few of these sets as possible.

I have a simple algorithm that provides decent results. In Python-like pseudocode:

start = ... #All of the edges are initially in the graph "start".
sets = {}   #The result of the algorithm: n independent sets, together containing all the edges
while size(start) > 0:
    new_set = {}
    for edge in start:
        if "edge" is independent of any edge in "new_set":
            start.remove(edge)
            new_set.add(edge)
    sets.add(new_set)

I can easily demonstrate by counterexample that it is nonoptimal. Consider the graph (note the edges' numbering):

#----#          #----#          #----#          #----#          #----#
| V1 |----E1----|-V2-|----E2----|-V3-|----E4----|-V4-|----E3----|-V5-|
#----#          #----#          #----#          #----#          #----#

The optimal solution is the set {{E1,E4},{E2,E3}}, but the above algorithm will output {{E1,E3},{E2},{E4}}, because it chooses E3 before E4. On (my) real data, it takes about 11% more sets than is optimal.

Does a better algorithm exist to solve this problem?

Speed is of some concern, but it is in the context of an amortized operation, so it's not terribly important. Right now, I'm interested in if an optimal algorithm actually exists/is known.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The problem is equivalent to finding the minimum number of colors to color the edges of a graph. The problem is NP-complete in general, and even for sparse graphs, but there are polynomial time algorithms which color the graph with at most one color more than the optimal coloring. In some other cases, such as bipartite graphs, we can find the optimal coloring in polynomial time. You can read more about this problem here

share|improve this answer
    
Doh! It is edge coloring. Thanks! –  imallett Dec 29 '12 at 20:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.