# PACE 2022

## 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.

More details on the ranking methods will be disclosed later on.

## Timeline

• September 2021: Announcement of the challenge (Problem) and tracks
• November 2021: Announcement of additional information and ranking methods
• December 2021: Public instances are available
• March 2022: Submission via optil.io is open (for testing and unofficial, auxiliary leaderboard)
• 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)