Horiyama, Kobayashi, Ono, Seto, and Suzuki introduced the pre-assignment model for uniquifying the optimal solutions of a given instance of optimization problems [AAAI 2024]. For example, a pre-assignment of minimum vertex cover C is defined as a vertex set \(C_\text {pre}=(C_{\text {in}}, C_{\text {ex}})\) such that C includes vertices in \(C_{\text {in}}\) and excludes ones from \(C_{\text {ex}}\) . The pre-assignment problem for unique minimum vertex covers (PAU-VC) asks whether there exists a pre-assignment of at most k vertices that induces a unique minimum vertex cover of a given graph. PAU-VC has three pre-assignment models: Include (i.e., \(C_{\text {ex}}=\emptyset \) ), Exclude (i.e., \(C_{\text {in}}=\emptyset \) ), and Mixed. Horiyama et al. showed that PAU-VC is \(\varSigma _2^p\) -complete on general and NP-complete on bipartite graphs under all three models. This paper shows PAU-VC remains \(\varSigma _2^p\) -complete in all three models even if a given graph is restricted to be planar with maximum degree 3.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Hardness of Pre-assignment Problem for Unique Minimum Vertex Cover on Planar Graphs with Maximum Degree 3

  • Takashi Horiyama,
  • Fumiya Sakamoto,
  • Kazuhisa Seto,
  • Ryu Suzuki

摘要

Horiyama, Kobayashi, Ono, Seto, and Suzuki introduced the pre-assignment model for uniquifying the optimal solutions of a given instance of optimization problems [AAAI 2024]. For example, a pre-assignment of minimum vertex cover C is defined as a vertex set \(C_\text {pre}=(C_{\text {in}}, C_{\text {ex}})\) such that C includes vertices in \(C_{\text {in}}\) and excludes ones from \(C_{\text {ex}}\) . The pre-assignment problem for unique minimum vertex covers (PAU-VC) asks whether there exists a pre-assignment of at most k vertices that induces a unique minimum vertex cover of a given graph. PAU-VC has three pre-assignment models: Include (i.e., \(C_{\text {ex}}=\emptyset \) ), Exclude (i.e., \(C_{\text {in}}=\emptyset \) ), and Mixed. Horiyama et al. showed that PAU-VC is \(\varSigma _2^p\) -complete on general and NP-complete on bipartite graphs under all three models. This paper shows PAU-VC remains \(\varSigma _2^p\) -complete in all three models even if a given graph is restricted to be planar with maximum degree 3.