Reducibility among NP-Hard graph problems and boundary classes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913979448688640 |
|---|---|
| author | Hassan, Syed Mujtaba Hussain, Shahid Samad, Abdul |
| author_facet | Hassan, Syed Mujtaba Hussain, Shahid Samad, Abdul |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14553 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reducibility among NP-Hard graph problems and boundary classes Hassan, Syed Mujtaba Hussain, Shahid Samad, Abdul Computational Complexity Computation and Language Discrete Mathematics 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. |
| title | Reducibility among NP-Hard graph problems and boundary classes |
| topic | Computational Complexity Computation and Language Discrete Mathematics |
| url | https://arxiv.org/abs/2411.14553 |