Exact Algorithms for Distance to Unique Vertex Cover

Horiyama et al. (AAAI 2024) studied the problem of generating graph instances that possess a unique minimum vertex cover under specific conditions. Their approach involved pre-assigning certain vertices to be part of the solution or excluding them from it. Notably, for the VERTEX COVER problem, preassigning a vertex is equivalent to removing it from the graph. Horiyama et al. focused on maintaining the size of the minimum vertex cover after these modifications. In this work, we extend their study by relaxing this constraint: our goal is to ensure a unique minimum vertex cover, even if the removal of a vertex may not incur a decrease on the size of said cover. Surprisingly, our relaxation introduces significant theoretical challenges. We observe that the problem is Σ 2 P -complete, and remains so even for planar graphs of maximum degree 5. Nevertheless, we provide a linear time algorithm for trees, which is then further leveraged to show that MU-VC is in FPT when parameterized by the combination of treewidth and maximum degree. Finally, we show that MU-VC is in XP when parameterized by clique-width while it is fixed-parameter tractable (FPT) if we add the size of the solution as part of the parameter. Recently, the PRE-ASSIGNMENT FOR UNIFICATION OF MINIMUM VERTEX COVER (PAU-VC) problem was introduced by Horiyama et al. [16] , and further studied in [1] . This problem was motivated by the need to create challenging datasets for algorithmic evaluation. Intuitively, ensuring a solution is unique adds significant complexity, as solvers have no margin for error in identifying the correct solution. A set S of vertices in a graph G is called a vertex cover if S intersects all edges of G. The objective of MINIMUM VERTEX COVER is to compute a vertex cover of G with the smallest cardinality possible. The UNIQUE VERTEX COVER problem extends this by ensuring that the input graph has a unique minimum vertex cover. This guarantee imposes additional constraints, making the problem particularly challenging from both theoretical and practical perspectives. It is important to note that, in the context of vertex cover, selecting a vertex for inclusion in the cover is equivalent to deleting it from the graph along with all its incident edges. However, ensuring that a set of vertices belongs to the deletion set can inadvertently increase the size of the minimum vertex cover under this constraint, introducing further complexity. This leads to the definition of the MODULATOR TO UNIQUE MINIMUM VERTEX COVER (MU-VC for short) problem (refer to Figure 1 for an illustration of the difference in the nature of the two problems): given a graph G = (V, E) and an integer k, find a set S ⊆ V such that G -S has a unique minimum vertex cover and |S| ≤ k. Unlike PAU-VC, where the solver must adapt to preselected vertices to enforce uniqueness, MU-VC simplifies this process by reverting to solving the MINIMUM VERTEX COVER problem on G -S. This distinction makes MU-VC particularly appealing, as it maintains the standard problem formulation while achieving uniqueness. Although this property holds for VERTEX COVER, it does not necessarily extend to other problems, such as DOMINATING SET. Our Contribution. It is easy to see that MU-VC is NP-hard, as it generalizes the UNIQUE OPTIMAL VERTEX COVER problem (for k = 0), which is known to be at least as hard as UNIQUE SAT which is NP-hard [17] . Our first result is to precisely determine its complexity and show that MU-VC is actually Σ P 2 -complete, as is the case for PAU-VC [16] ; in fact, in Theorem 7 we show that both problems remain so even for very restricted graph classes, namely planar graphs of maximum degree 5 (which also improves the corresponding result in [16] ). Motivated by these negative results we proceed to examine MU-VC when the input graph G has an even simpler structure, that of a tree. We initially present a polynomial-time algorithm for this case in Section 3.1, which is then improved into an (optimal) linear time algorithm in Theorem 2. We then tackle the problem through the parameterized complexity point of view. Given that the natural parameterization by k cannot yield any positive results (as evidenced by the case k = 0), we proceed by taking into account the structure of G. We first consider the parameterization by treewidth, the most well-studied structural parameter. Building upon the algorithm of Theorem 2, in Theorem 3 we employ DP to construct an XP algorithm with running time n O(2 w ) , where w is the treewidth of G, which is then improved into an FPT algorithm in Theorem 4 when paramaterized also by the maximum degree of G. Next, we consider the parameterization by clique-width and, in Theorem 5, we develop a DP algorithm showing that the problem belongs to XP and is solvable in n O(2 d ) time, where d denotes the clique-width of G. Additionally parameterizing by the natural parameter k lifts the problem to FPT, and in Theorem 6 we develop such an algorithm of running