2023/12/17 by Takashi Horiyama, Horiyama, Takashi, Yasuaki Kobayashi +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Assignment problem #Bipartite graph #Combinatorics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer science #Cover (algebra) #Data Structures and Algorithms (cs.DS) #Edge cover #FOS: Computer and information sciences #Graph #Mathematical optimization #Mathematics #Optimization and Search Problems #Set (abstract data type) #Set cover problem #Time complexity #Uniqueness #Vertex (graph theory) #Vertex cover
paper · pdf · doi:10.48550/arxiv.2312.10599
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The uniqueness of an optimal solution to a combinatorial optimization problem attracts many fields of researchers' attention because it has a wide range of applications, it is related to important classes in computational complexity, and an instance with only one solution is often critical for algorithm designs in theory. However, as the authors know, there is no major benchmark set consisting of only instances with unique solutions, and no algorithm generating instances with unique solutions is known; a systematic approach to getting a problem instance guaranteed having a unique solution would be helpful. A possible approach is as follows: Given a problem instance, we specify a small part of a solution in advance so that only one optimal solution meets the specification. This paper formulates such a ``pre-assignment'' approach for the vertex cover problem as a typical combinatorial optimization problem and discusses its computational complexity. First, we show that the problem is ΣP2-complete in general, while the problem becomes NP-complete when an input graph is bipartite. We then present an O(2.1996n)-time algorithm for general graphs and an O(1.9181n)-time algorithm for bipartite graphs, where n is the number of vertices. The latter is based on an FPT algorithm with O^*(3.6791τ) time for vertex cover number τ. Furthermore, we show that the problem for trees can be solved in O(1.4143n) time.