Challenge description
The challenge for this year is Cluster Editing:
Input: An undirected graph $G = (V, E)$.
Output: A set of edge modifications (addition or deletion) of minimum size that transforms $G$ into a cluster graph.
You can find more details on Cluster Editing here.
Tracks
As in PACE 2020, we will have one track for Exact algorithms and another for Heuristic algorithms. In addition, we will have another track for Data Reduction algorithms:
Exact: Your task is to find an optimal solution of each Cluster Editing instance within the time limit of 30 minutes. You will be ranked by the number of solved instances.
Heuristic: Your task is to find the best solution of each Cluster Editing instance within the time limit of 10 minutes. You will be ranked by the quality of the solution.
Kernelization: Your task is to find an equivalent instance of each Cluster Editing instance within the time limit of 5 minutes. You will be ranked by the size of the returned instance.
You can find more details on the ranking methods here.
Submission
You submit your solver to optil.io and its description to EasyChair. See submission requirements for details.
Timeline
- October 22nd, 2020: Announcement of the challenge (Problem)
- November 2020: Announcement of the tracks and additional information
- December 2020: Public instances are available
- March 2021: Submission via optil.io is open (for testing and unofficial, auxiliary leaderboard)
- June 1st, 2021 (AoE): Submission deadline for solver
- June 15th, 2021 (AoE): Submission deadline for solver description
- July 16th: Announcement of the results
- September 2021: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2021) (slides)
Program Committee
- André Nichterlein (chair) (Technical University of Berlin)
- Leon Kellerhals (Technical University of Berlin)
- Tomohiro Koana (Technical University of Berlin)
- Philipp Zschoche (Technical University of Berlin)