Challenge Description
The challenge for this year is Directed Feedback Vertex Set:
Input: A directed graph $G = (V, E)$.
Output: Find a minimum subset $X \subseteq V$ such that, when all vertices of $X$ and their adjacent edges are deleted from $G$, the remainder is acyclic.
You can find more details on Directed Feedback Vertex Set here.
Tracks
We will have one track for Exact algorithms and another for Heuristic algorithms.
Exact: Your task is to find an optimal solution of each Directed Feedback Vertex Set 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 Directed Feedback Vertex Set instance within the time limit of 10 minutes. You will be ranked by the quality of the solution.
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
- September 2021: Announcement of the challenge (Problem) and tracks
- November 2021: Announcement of additional information and ranking methods
December 2021January 2022: Public instances are available- March 2022: Submission via optil.io is open (for testing and unofficial, auxiliary leaderboard)
- May 25th, 2022 (AoE): Leaderboards on optil.io will be closed. Solver submission will still be possible, but the leaderboard will not be updated.
- June 1st, 2022 (AoE): Submission deadline for solver
- June 15th, 2022 (AoE): Submission deadline for solver description
- July, 2022: Announcement of the results
- September 2022: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2022)
Program Committee
- Christian Schulz (chair) (Universität Heidelberg)
- Ernestine Großmann (Universität Heidelberg)
- Tobias Heuer (Karlsruher Institut für Technologie)
- Darren Strash (Hamilton College)
Sponsors
On behalf of the Organization Committee of the 7th PACE Challenge, we invite you to participate in the sponsoring of metals and travel support for PACE-22.
NETWORKS already announced sponsoring for PACE 2022.
