Breakthrough Tracker record
An AI-assisted proof yields a new iterative-rounding route for Feedback Vertex Set
Karthekeyan Chandrasekaran, Chandra Chekuri and Shubhang Kulkarni prove a 2021 extreme-point conjecture for strong-density polyhedra and derive polynomial-time iterative-rounding 2-approximation algorithms for Feedback Vertex Set.
← Back to the filtered Breakthrough Tracker
- Stable ID
cs-feedback-vertex-set-extreme-point-proof-2026- Revision
cs-feedback-vertex-set-extreme-point-proof-2026.v1- Field
- Computer science · Approximation algorithms, polyhedral combinatorics and graph optimization
- Evidence
- Tier 1 · Peer reviewed: No
- Record state
- Provisional · Provisional AI-assisted theorem and algorithm
- Last checked
AI role
The paper states that AI tools suggested key ideas in the proof of the extreme-point property. The authors provide the final proof and algorithmic analysis.
Record details
- Problem or result
- Fiorini's extreme-point conjecture and iterative rounding for Feedback Vertex Set
- Authors
- Karthekeyan Chandrasekaran, Chandra Chekuri and Shubhang Kulkarni
- Institutions
- University of Illinois Urbana-Champaign
- Result date
- Preprint submitted September 3, 2026
Why it matters
The factor-two approximation ratio is already optimal under standard assumptions, but this proves a previously open polyhedral property and supplies the first stated iterative-rounding route to that ratio.
Limits
This is a first-version preprint without located peer review. The approximation factor itself is not new, and the paper does not yet identify the AI tools or provide a detailed interaction record.
Sources
Correction and revision history
- 2026-09-07 — Added after primary-source, scope, status, AI-role and limitation review.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.