通过归约关系揭示图问题的难易边界，找到关键结构特征。
Reducibility among NP-Hard graph problems and boundary classes
- 利用问题间的可归约性，将一个难题的边界类转化为另一个难题的边界类。
- 证明了若Π可归约至Γ，其边界类在归约下保持对应关系。
- 成功推导出顶点覆盖、团、旅行商等经典问题的新边界类。
许多NP-hard图问题在特定图类上变得容易，例如二分图上的着色问题。这引发关键问题：何时难题变简单？最小维持难题的子结构是什么？本文引入边界类来研究此类问题。提出一种方法，将一个问题的边界类通过归约映射到另一问题的边界类。若问题Π可归约至Γ，且归约满足特定条件，则Π的边界类X当且仅当其在归约下的像为Γ的边界类。该理论建立了多个NP-hard问题间边界类与可归约性的联系。通过应用此定理，我们首次获得顶点覆盖、团、旅行商、有界度生成树、子图同构及团覆盖等问题的部分未知边界类。
原文摘要 · Abstract (English)
Many NP-hard graph problems become easy for some classes of graphs. For example, coloring is easy for bipartite graphs, but NP-hard in general. So we can ask question like when does a hard problem become easy? What is the minimum substructure for which the problem remains hard? We use the notion of boundary classes to study such questions. In this paper, we introduce a method for transforming the boundary class of one NP-hard graph problem into a boundary class for another problem. If Π and Γ are two NP-hard graph problems where Π is reducible to Γ, we transform a boundary class of Π into a boundary class of Γ. More formally if Π is reducible to Γ, where the reduction satisfies certain conditions, then X is a boundary class of Π if and only if the image of X under the reduction is a boundary class of Γ. This gives us a relationship between boundary classes and reducibility among several NP-hard problems. To show the strength of our main result, we apply our theorem to obtain some previously unknown boundary classes for a few graph problems namely; vertex-cover, clique, traveling-salesperson, bounded-degree-spanning-tree, subgraph-isomorphism and clique-cover.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。