Research map / Learning theory and algorithms / Combinatorial and search optimization
Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover
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.
Formalizes pre-assignment (clue-style) instance generation for unique minimum vertex cover (PAU-VC), proves Σ2P-completeness for general graphs, NP-completeness for bipartite graphs, and gives exact/FPT/tree algorithms.
Problem
Generating vertex cover instances with a unique minimum solution by pre-assigning roles to a small set of vertices; the complexity of finding the smallest such pre-assignment (PAU-VC) is unknown.
Approach
Defines three pre-assignment models (Include, Exclude, Mixed) for uniquifying minimum vertex covers, shows Exclude and Mixed are equivalent and Exclude is stronger than Include, and gives reductions and algorithms exploiting vertex-cover structure (FPT in vertex cover number via branching and set-cover DP).
Key results
- PAU-VC is Σ2P-complete for general graphs under any model, while NP-complete for bipartite graphs.
- Exact algorithm runs in O(2.1996^n) for general graphs; FPT algorithm in O*(3.6791^τ) for Include, Mixed and Exclude models (Exclude/Mixed via set-cover cost device).
- For bipartite graphs, O(1.9181^n) time; for trees, O(1.4143^n) time under any model.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply pre-assignment uniquification to Vertex Cover instances | Vertex Cover instance generation · instances with small vertex covers | generation suitability | Helped |
Surprising findings
- Exclude model is strictly stronger than Include: a complete graph K_n needs only one excluded vertex to be uniquified, while Include needs n-2 or more vertices.
Limitations
- Pre-assignment approach may not be universally promising; works best for graphs with small vertex covers.
- No polynomial-time algorithm known for trees; only exponential upper bounds given.
Experimental setup
Metrics: worst-case running time computational complexity class
Baselines: Algorithm enumerating all subsets for UVC check
Builds on: FCP (Fewest Clues Problem) Konig's theorem Hopcroft-Karp algorithm
Closest papers by meaning
- Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs (AAAI 2025 · similarity 0.88)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.86)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.85)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.85)
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.84)
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.84)
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.