> If I am understanding your problem correctly, the decision of the > existence of such a set of solutions (doesn't really make sense to > have a basis does it? 0,1 vectors in the kernel?) NP-Complete by Karp, > The Binary Integer Programming problem. > > http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems > > The hardness of this problem is the main difficulty underlying of much > of combinatorics.
Hmmmm :-/ I know I can find a solution through integer programming, but in this case I hope to find the whole set of solutions (actually, a basis of it) because the problem is very special. I have a DiGraph, and I am interested in all the eulerian subdigraphs (a subdigraph is eulerian if each vertex as as many incoming edges than outgoing edges). If you add two eulerian subgraphs, then forget the edges that were taken two times (over Z/2Z), what you get is a new eulerian subdigraph. "a solution" of my system, is, in this case, any circuit I could find for example... I hoped there was a lazy way to obtain a basis of such a space through matrix operations... :-/ Nathann -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
