Nathann Cohen
  • Member for 11 years, 4 months
  • Last seen more than 3 years ago
Are there good implementations for easy subclasses of NP-hard graph problems
Accepted answer
13 votes

I'd be surprised if there existed a graph library recognizing them all (there is a lot of them), but most of the algorithms you will find in the litterature are focused on a very small amount of ...

View answer
Decompose a complete graph into smaller cliques
Accepted answer
12 votes

If you want to decompose a complete graph into triangles then look for "steiner triple system" (STS). You will find some there: http://steinertriples.fr/ If you want to decompose a complete graph ...

View answer
Shortest paths disallowing each edge
8 votes

If you want to associate to each edge the length of a shortest path between $s$ and $t$, you can begin with computing a shortest path in the whole graph, and associate to each edge not in the shortest ...

View answer
Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges
Accepted answer
8 votes

According to Bollobas (Random Graphs), if you make "natural assumptions" on $n$ and $m$ there are $n!$ times more labelled graphs on $n$ vertices and $m$ edges than random unlabelled graphs on $n$ ...

View answer
Bounds on sum of squares of node degrees in undirected graphs
7 votes

You may also like to know that this "sum of squares of the degrees" is also called "First Zagreb Index". When you type it in Google you get results like this one : http://www.springerlink.com/content/...

View answer
Finding cliques in a big graph
7 votes

Give Cliquer a try. http://users.tkk.fi/pat/cliquer.html It's true your graph is huge, but sometimes it works. And it doesn't take long to try it as this software is already (and well) coded :-) ...

View answer
Smallest set that intersects some given sets
6 votes

If you want to solve actual instances, you will probably like that : http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_vertex_set Nathann

View answer
Does there exist polytime algorithm for this partitioning problem?
Accepted answer
6 votes

(This is about the problem in which $|\phi(\Phi^{-1}(i))|\geq 2$ instead of $|\Phi(\phi^{-1}(i))|\geq 2$. Read it too fast. On the bright side Dave fixes it in a comment to this message ) What about ...

View answer
LP relaxation of independent set
6 votes

There is another way to get a "relaxed version of maximal independent set". Instead of having as constraints "for each edge, the sum is at most 1", the constraints are "for each complete subgraph, the ...

View answer
All pair shortest path problem for large number of nodes
5 votes

I tried to write a good implementation for precisely this problem, which is now available in Sage. http://www.sagemath.org/doc/reference/sage/graphs/distances_all_pairs.html While Sage is written in ...

View answer
Postselection in geometric complexity theory
5 votes

I like to think this way too, and I link it with the $P=NP\cap co-NP$ conjecture. It is mentionned there or there (I am having a hard time finding pages about this conjecture as I can only refer to it ...

View answer
Generation of unlabeled acyclic digraphs
Accepted answer
5 votes

If you are looking for an implementation, Sage knows how to generate general digraphs up to isomorphism sage: len(list(digraphs(4))) 218 You can then plug in a "test" method if you just want the ...

View answer
Exact algorithm for edge coloring
4 votes

You main gain significant time by first computing the fractional chromatic index, which would tell quickly if your graph is class 2. Then Vizing's algorithm would probably do. In Sage -- even though ...

View answer
Catalog of NP-complete problems, more up-to-date than Garey&Johnson?
4 votes

There is "Encyclopedia of Algorithms" from 2008, which surveys a lot of different problems (1160 pages of it) http://www.springer.com/computer/theoretical+computer+science/book/978-0-387-30770-1

View answer
Approximate Maximum Weight Matching
Accepted answer
3 votes

You should try Sage's implementation. It uses LP, but I don't think that you would get something so large in less than 100milliseconds. Greedy probabilistic would be nice in this case I guess. http://...

View answer
Fast treewidth algorithms
3 votes

Sage doesn't know how to compute treewidth exactly but it can give you the pathwidth of small graphs. http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation....

View answer
Maximum-clique practical applications
3 votes

If you ask questions like that, I feel that the only answers you could get are problems that "reduce to the maximum clique". That would be a mistake. There are many problems in practice where finding ...

View answer
Any references for techniques in FPT reductions?
3 votes

I haven't had the occasion to open it yet, but I guess you may be interested in "Exact exponential algorithms" by Fomin and Kratsch (from last year) Here it its table of contents : http://www....

View answer
Implementations of Undirected Disjoint Paths
2 votes

If you want an implementation, Sage has one. With a LP, as usual ;-) http://www.sagemath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph....

View answer
Max-Flow and Graph Orientation:
2 votes

One of the most amazing theorems in graph theory is Nash-William's : http://en.wikipedia.org/wiki/Strong_orientation .... And its proof is constructive, but not that easy to implement :-)

View answer
Longest path in Complete Directed Graphs
Accepted answer
2 votes

Sage's implementation of it for instance :-) http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path Nathann

View answer
Finding the longest path between two nodes in a bidirectional unweighted graph
2 votes

If you are not looking for an algorithm but for an implementation of it and want to solve this problem on an actual graph, this is one of the things Sage (http://sagemath.org/index.html) knows how to ...

View answer
What are the root difficulties in going from graphs to hypergraphs?
2 votes

I was first going to answer the wrong question : "which example of problems are much harder in hypergraphs than in graphs". I was particularly impressed by the difference in dealing with the maximum ...

View answer
Longest circuit in a directed graph
1 votes

One million nodes is far too much for any exact method that I know. This being said, I expect your graph does not have a very large number of edges, so the best is to begin by applying repeatedly this ...

View answer
Shortest Path Algorithm for large graph but short paths
1 votes

Well, for example did you try sorting the list of outneighrs of each vertex according to their degree ? Sort them once and for all, then each time you do a BFS it will use this ordering, which may be ...

View answer
Data-structure for functions of independent sets
Accepted answer
1 votes

I wanted to post a comment, but with no "karma" it seems impossible... What about using dictionaries (hashmap, depending on the language you use) to store the values of your $f_i$ ? This way you don't ...

View answer
Finding maximum weight arborescence in an edge-weighted DAG
0 votes

What about picking, for any vertex different from the source, an incoming arc with maximum weight ? Each vertex except the source is of indegree one, and you needn't worry about circuits as you are in ...

View answer