Research map / Graph learning / Graph algorithms and clustering
Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs
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.
Shows that Min PAU-VC (minimum pre-assignment for unique minimum vertex cover) is FPT parameterized by clique-width via an NLC-width dynamic program, and solvable in linear time on unit interval and split graphs.
Problem
Finding a minimum pre-assignment S of vertices such that exactly one minimum vertex cover of G contains S; previously only exponential algorithms were known for trees and the complexity on trees and other sparse/dense structured classes was open.
Approach
A dynamic programming over clique-width (NLC-width) expressions that tracks, for each label subset, whether a set forces zero, one, or at least two minimum vertex covers with respect to that label subset; combined with structural arguments giving linear-time algorithms for unit interval and split graphs.
Key results
- Min PAU-VC is fixed-parameter tractable parameterized by clique-width, running in 2^{O(2^k)} |V(G)|^2 time given a k-expression (improving the exponential tree algorithm of Horiyama et al.).
- Min PAU-VC is solvable in linear time on unit interval graphs and on split graphs, which have unbounded clique-width.
- For bipartite graphs, no polynomial-time constant-factor approximation exists unless P=NP, via reduction from minimum independent dominating set and Irving's hardness result.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the clique-width-parameterized algorithm on graphs given a clique-width expression | Min PAU-VC · Graphs with clique-width k | running time: 2^{\mathcal{O}(2^k)} |V(G)|^2 | Helped |
| use the unit interval graph algorithm | Min PAU-VC · Unit interval graphs | running time: linear time | Helped |
| use the split graph algorithm | Min PAU-VC · Split graphs | running time: linear time | Helped |
| use the polynomial-time algorithm instead of the prior exponential-time algorithm | Min PAU-VC · Trees | running time: \mathcal{O}(1.4143^n) -> polynomial-time | Helped |
Limitations
- Running time is double exponential in clique-width.
- Chordal graphs and interval graphs remain open.
- Bipartite graphs admit no constant-factor approximation unless P=NP.
Experimental setup
Metrics: running time complexity
Baselines: Horiyama et al. O(1.4143^n) tree algorithm
Builds on: Horiyama et al. PAU-VC (AAAI 2024) Courcelle-Makowsky-Rotics meta-theorem Johansson clique-width to NLC-width transformation Oum clique-width approximation
Closest papers by meaning
- Exact Algorithms for Distance to Unique Vertex Cover (AAAI 2026 · similarity 0.90)
- Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover (AAAI 2024 · similarity 0.88)
- Finding Diverse Solutions Parameterized by Cliquewidth (AAAI 2026 · similarity 0.86)
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.86)
- KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem (AAAI 2024 · similarity 0.84)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.83)
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.