Research map / Graph learning / Graph algorithms and clustering
Threshold-Based Responsive Simulated Annealing for Directed Feedback Vertex Set Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes TRSA, a threshold-based responsive simulated annealing with a closing-opening swap neighborhood, two new reduction rules (DOMV, MC), and acceleration strategies for the directed feedback vertex set problem.
Problem
Directed feedback vertex set problem (DFVSP): find a minimum set of vertices whose removal makes a directed graph acyclic; NP-hard and the PACE 2022 heuristic track topic.
Approach
Represents solutions directly as the set of remaining (open) vertices, uses a closing-then-opening swap neighborhood accelerated by cycle elimination, bidirectional-edge elimination and a threshold-based first-fit limit, and embeds these in simulated annealing with periodic temperature rises and a dynamic threshold.
Key results
- On 100 PACE 2022 instances TRSA obtains the best result on 92 instances and improves best known results on 40, with a total gap of 0.4%.
- TRSA improves best known results on 13 of 40 classical instances and matches the rest in best results.
- Across both sets TRSA improves best-known results on 53 instances and matches 79 of 140.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TRSA instead of the strongest reference algorithm | DFVSP on classical instances · 40 classical instances | FVS size: improving the best known results of all reference algorithms on 13 instances | Helped |
| Use TRSA instead of the strongest reference algorithm | DFVSP on PACE 2022 instances · 100 PACE 2022 instances | FVS size: improves the best known results on 40 instances | Helped |
| Disable the DOMV and MC reduction rules (ablation) | TRSA · h 141, h 165, h 181 | objective value gap over search time | Hurt |
| Disable neighborhood reduction based on bidirectional edge elimination (ablation) | TRSA · h 141, h 165, h 181 | objective value gap over search time | Hurt |
| Disable the threshold-based first-fit strategy (ablation) | TRSA · h 141, h 165, h 181 | objective value gap over search time | Hurt |
Limitations
- Reported results are from single-CPU experiments with 30 runs; compute constraints limit scaling claims.
- Authors note the implementation is a preliminary version of TRSA for the competitor listing.
Experimental setup
Datasets: Pardalos-Qian-Resende classical DFVSP instances (40) PACE 2022 heuristic track instances (100)
Benchmarks: 40 classical DFVSP instances 100 PACE 2022 heuristic track instances
Metrics: best objective (fmin) average objective (favg) Wilcoxon p-value total gap (%)
Baselines: SA-FVSP IDTS DiVerSeS DreyFVS HustFVS
Builds on: simulated annealing (SA-FVSP) iterated dynamic thresholding search (IDTS) Lin and Jou reduction rules
Closest papers by meaning
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.83)
- An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem (AAAI 2025 · similarity 0.83)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.82)
- Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover (AAAI 2024 · similarity 0.82)
- Bayesian Optimization of Functions over Node Subsets in Graphs (NeurIPS 2024 · similarity 0.82)
- AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs (NeurIPS 2026 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.