:-D It's true than when I re-read my question, I am plainly asking "how to solve an binary program" :-D
There should be some constraint to add to my question to make it less powerful than SAT... Sorry for that ^^; Nathann On 17 July 2010 01:42, Nathann Cohen <[email protected]> wrote: >> 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
