Subquadratic-exponent counting of graphs with small vertex cover
Subquadratic-exponent counting of graphs with small vertex cover. Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.
Editorial MSC2020 mapping of Subquadratic-exponent counting of graphs with small vertex cover. https://drops.dagstuhl.de/storage/04dagstuhl-reports/volume15/issue01/25041/DagRep.15.1.105/DagRep.15.1.105.pdf#page=13 Not an author-supplied code.
Problem statement
Given integers , count the labeled simple graphs on vertex set having a vertex cover of size at most . Is an algorithm with running time possible?
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
Editorial question summary. Consult the linked source for the complete model, assumptions and discussion.
Progress & source assessment
Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.
- [1]Seminar 25041 problem-session contributors. Dagstuhl 25041 — Graph Classes and Algorithmic Complexity (2025).; Subquadratic-exponent counting of graphs with small vertex cover linkCC BY 4.0; attributed editorial adaptation of the named section authors.
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.