@techreport{oai:ipsj.ixsq.nii.ac.jp:00234048,
 author = {Takashi, Horiyama and Yasuaki, Kobayashi and Hirotaka, Ono and Kazuhisa, Seto and Ryu, Suzuki and Takashi, Horiyama and Yasuaki, Kobayashi and Hirotaka, Ono and Kazuhisa, Seto and Ryu, Suzuki},
 issue = {9},
 month = {May},
 note = {Given an instance of combinatorial optimization problem A with multiple optimal solutions, how can we efficiently reduce it into an instance of A with a unique optimal solution? In AAAI 2024, we formulated the problem of uniquifying minimum vertex covers under pre-assignments: how many vertices are included/excluded vertices into/from vertex covers to uniquify minimum vertex covers including/excluding these vertices? We showed the Σ???? 2 -completeness for general graphs and the NP-completeness for bipartite graphs. We designed an ????(2.1996????)-time algorithm for general graphs and an ????(1.9181????)-time algorithm for bipartite graphs, where ???? is the number of vertices. The latter is based on an FPT algorithm with ????∗ (3.6791????) time for vertex cover number ????. In this report, we present these algorithms., Given an instance of combinatorial optimization problem A with multiple optimal solutions, how can we efficiently reduce it into an instance of A with a unique optimal solution? In AAAI 2024, we formulated the problem of uniquifying minimum vertex covers under pre-assignments: how many vertices are included/excluded vertices into/from vertex covers to uniquify minimum vertex covers including/excluding these vertices? We showed the Σ???? 2 -completeness for general graphs and the NP-completeness for bipartite graphs. We designed an ????(2.1996????)-time algorithm for general graphs and an ????(1.9181????)-time algorithm for bipartite graphs, where ???? is the number of vertices. The latter is based on an FPT algorithm with ????∗ (3.6791????) time for vertex cover number ????. In this report, we present these algorithms.},
 title = {Exact Algorithms for Uniquifying Minimum Vertex Covers under Pre-assignment Models},
 year = {2024}
}