The Graph Partitioning Problem (equicut) is:

INPUT: an undirected graph G with 2n nodes.

OUTPUT: a partition of the nodes of G into two equicardinality sets S and T as to minimize the number of edges with one endpoint in S and the other in T.

The figure above shows two examples. Set S is enclosed in an ellipse and the red edges represent the minimum equicut of each graph.

• Tutorial (suggested for first-time users).
• Interactive Tool (send instances and receive solutions).
• Benchmarks (collected instances, results, formats and conversions).
• advanced tool.
• Other network resources for graph partitioning.

---

Interactive Tool
We are developing efficient heuristic algorithms for the graph partitioning problem. The tool puts at your disposal two algorithms: Diff-Greedy (Differential Greedy) and RRTS (Reactive and Randomized Tabu Search) .
Diff-Greedy is a very fast greedy construction algorithm, RRTS is a Tabu Search algorithm (local search plus prohibitions) with a randomized and reactive determination of the prohibition. RRTS takes more computational effort but provides state-of-the-art heuristic results on many benchmark graphs.

You can submit a description of your graph. Our server will run our heuristics on your problem. The best solution found and other statistics will be returned to you online and, optionally, by e-mail.

---

Submit your problem:

• Equicut problem file:
• Note: The problem file must be in plain DIMACS format (see our tutorial) or in binary DIMACS format.
  Here you can find a converter from plain DIMACS format to binary DIMACS format.
  If the edge density of the graph is bigger than ~1.2%, the binary storage is more space efficient. So it is preferable to convert an ascii Dimacs file to the binary format before uploading to our server.
• Set Random Seed: (Note: this seed is used only in RRTS.)

---

our

Greedy RRTS

heuristic.