The problem of uniquifying an optimal vertex cover under pre-assignment is, given a graph G and an integer k, to determine whether there exists a pair of sets of vertices \((\tilde{U}_{\text {in}}, \tilde{U}_{\text {ex}})\) such that \(|\tilde{U}_{\text {in}}| + |\tilde{U}_{\text {ex}}| \le k\) and G has exactly one minimum vertex cover including the vertices in \(\tilde{U}_{\text {in}}\) and excluding those in \(\tilde{U}_{\text {ex}}\) . Horiyama et al. introduced this problem as PAU-VC. They showed that PAU-VC is \(\Sigma ^P_2\) -complete for general graphs and NP-complete for bipartite graphs. They also gave an \(O^*(3.6791^\tau )\) time algorithm for general graphs, where \(\tau\) is the size of optimal vertex covers of a given graph. It can solve the problem on bipartite graphs with n vertices in time \(O(1.9181^n)\) . In this paper, we propose an \(O(1.4143^n)\) time algorithm for PAU-VC on bipartite graphs with n vertices. Our algorithm utilizes the Dulmage-Mendelsohn decomposition and reduces the problem to a problem on a poset. In addition, we prove that PAU-VC remains NP-complete even for planar bipartite graphs of maximum degree 3.
