The Feedback Vertex Set (FVS) problem is a computational problem in computer science and graph theory that involves finding the smallest possible subset of vertices in an undirected graph such that removing those vertices results in a graph that is acyclic, i.e., a forest. The goal of the FVS problem is to minimize the size of the feedback vertex set, and is considered NP-hard, meaning that finding the optimal solution is computationally difficult. For directed graphs, a feedback vertex set is instead a subset of vertices whose removal results in directed acyclic graph (DAG), not necessarily a forest. This task can refer to either looking for a set of provably minimal size (in as little time as possible), or a heuristic algorithm that produces small solutions quickly (but which may have even smaller sets).
데이터셋
출처에 같은 태스크 이름으로 연결된 데이터셋입니다. 동명 태스크가 포함될 수 있으므로, 비교할 때는 평가 결과의 조건도 확인하세요.
This is the dataset used in the PACE 2016 challenge, Track B, which was computing minimal Feedback Vertex Set. This competition focused on exact solutions, i.e. provably minimal feedback vertex sets (and no heuristic solutions). This should not be confused with the PACE 2022 challenge, which focused on directed feedback vertex set, and has its own entries on PapersWithCode (exact and heuristic). The dataset can be downloaded here, and includes 100 instances that were released for practice (the public/ folder) and 100 instances that were kept private (hidden/) until the competition evaluation. All 200 were used in the final evaluation. Each instance is an undirected graph, one edge per line, in the format a b indicating an edge between vertices a and b. Vertices are 1-indexed. Final results of the competition were reported in the PACE report, and additional analysis of some top solutions was done independently by Kiljan and Pilipczuk.
This is the set of graphs used in the PACE 2022 challenge for computing the Directed Feedback Vertex Set, from the Exact track. It consists of 200 labelled directed graphs. The graphs range in size up to from N=512 up to N=131072 vertices, and up to 1315170 edges. The graphs are mostly not symmetric (an edge form u->v does not imply an edge from v->u), although some are symmetric. The graph labels are integers ranging from 1 to N. There is the related PACE 2022 Heuristic dataset, which allowed for approximate solutions (feedback vertex sets that were not necessarily of minimum size). Those graphs are generally larger and denser, as approximate solutions were still accepted. The data format begins with one line N E 0, where N is the number of vertices, E is the number of edges, and 0 is the literal integer zero. The N subsequent lines are each a space-separated list of integers, such as 2 5 11 19. If that appeared on line number 1 (the first after N E 0), it would indicate that there are edges from vertex 1 to each of the vertices 2, 5, 11, and 19. Some lines are blank, and these indicates vertices with outdegree zero. An example graph would be 4 4 0 2 3 3 1 The dataset can be downloaded here. The 100 instances that were available for public testing are precisely the odd-numbered ones in that link; the public instances can be downloaded on their own here.
This is the set of graphs used in the PACE 2022 challenge for computing the Directed Feedback Vertex Set, from the Heuristic track. It consists of 200 labelled directed graphs. The graphs are mostly not symmetric (an edge form u->v does not imply an edge from v->u), although some are symmetric. The graph labels are integers ranging from 1 to N. There is the related PACE 2022 Exact dataset, which was for exact computation; those graphs are generally smaller and sparser, as only exact solutions were accepted. The data format begins with one line N E 0, where N is the number of vertices, E is the number of edges, and 0 is the literal integer zero. The N subsequent lines are each a space-separated list of integers, such as 2 5 11 19. If that appeared on line number 1 (the first after N E 0), it would indicate that there are edges from vertex 1 to each of the vertices 2, 5, 11, and 19. Some lines are blank, and these indicates vertices with outdegree zero. An example graph would be 4 4 0 2 3 3 1 The dataset can be downloaded here. The 100 instances that were available for public testing are precisely the odd-numbered ones in that link; the public instances can be downloaded on their own here.