Browse State-of-the-Art › Feedback Vertex Set (FVS)

Feedback Vertex Set (FVS)

1 paper with code · 0 benchmarks · 3 datasets archive 2025-07-28

Graphs

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

Description from the archive archive 2025-07-28.

Benchmarks archive 2025-07-28

No benchmark for this task in the archive.

Libraries

Not in the archive: the export carries no per-task library table, so there is nothing to show at snapshot 2025-07-28.

Datasets archive 2025-07-28

3 datasets whose archive record lists this task, ordered by the archive's paper count.

Subtasks archive 2025-07-28

No subtask under this task in the archive's task tree.

Papers archive 2025-07-28

archive papers tagged: 4 · with a code link: 1 · where Syntology ran a sample: 1 (1 with a run with no instrument failure, 0 where every run was a failure of Syntology's instrument) Syntology

Show: all tagged papersonly where code ran (1 of 4 tagged: 1 with a run with no instrument failure, 0 where every run was a failure of Syntology's instrument)

Page 1 of 1: papers 1 to 4 of 4, in archive order: by repositories listed in the archive (most first), then newest first, not by stars (the archive holds no stars, so PwC's “Social” and “Latest” sorts cannot be reproduced). Papers that list no repository come after every paper that lists one.

Papers without a page here are shown as plain text. A Syntology line reads “N ran (of which C constructed an object rather than computing a result; K with no instrument failure: H honoured, V violated, P with no contract checked; I where Syntology's instrument failed) · U unverified”; the figure “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. When the archive marks a repository official for the paper, the line starts with that repository's state (the archive's flag, not a verdict on who wrote the code); hover it for the repositories the samples that ran came from.

Syntology lines on 1 of the papers shown; no Syntology record for the others (a paper without an arXiv id cannot be joined to the graph, and absence from the graph layer is not a recorded non-run). “Ran” means the sample executed on a synthesized fixture, not that the paper's result was reproduced; each line links to that paper's sample list. Syntology's record for this page last changed ; when this build read Syntology's graph is in the build record. For agents: get_harvested_code_for_paper(arxiv_id) lists each paper's samples; how to connect.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections