Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2501.13217 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916579229302784 |
|---|---|
| author | Li, Hengzhe Wang, Qiong Liu, Jianbing Gao, Yanhong |
| author_facet | Li, Hengzhe Wang, Qiong Liu, Jianbing Gao, Yanhong |
| contents | In 1985, Chvátal introduced the concept of star cutsets as a means to investigate the properties of perfect graphs, which inspired many researchers to study cutsets with some specific structures, for example, star cutsets, clique cutsets, stable cutsets. In recent years, approximation algorithms have developed rapidly, the computational complexity associated with determining the minimum vertex cut possessing a particular structural property have attracted considerable academic attention.
In this paper, we demonstrate that determining whether there is a matching vertex-cutset in $H$ with size at most $k$, is $\mathbf{NP}$-complete, where $k$ is a given positive integer and $H$ is a connected graph. Furthermore, we demonstrate that for a connected graph $H$, there exists a $2$-approximation algorithm in $O(nm^2)$ for us to find a minimum matching vertex-cutset. Finally, we show that every plane graph $H$ satisfying $H\not\in\{K_2, K_4\}$ contains a matching vertex-cutset with size at most three, and this bound is tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13217 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity and Algorithm for the Matching vertex-cutset Problem Li, Hengzhe Wang, Qiong Liu, Jianbing Gao, Yanhong Data Structures and Algorithms Combinatorics In 1985, Chvátal introduced the concept of star cutsets as a means to investigate the properties of perfect graphs, which inspired many researchers to study cutsets with some specific structures, for example, star cutsets, clique cutsets, stable cutsets. In recent years, approximation algorithms have developed rapidly, the computational complexity associated with determining the minimum vertex cut possessing a particular structural property have attracted considerable academic attention. In this paper, we demonstrate that determining whether there is a matching vertex-cutset in $H$ with size at most $k$, is $\mathbf{NP}$-complete, where $k$ is a given positive integer and $H$ is a connected graph. Furthermore, we demonstrate that for a connected graph $H$, there exists a $2$-approximation algorithm in $O(nm^2)$ for us to find a minimum matching vertex-cutset. Finally, we show that every plane graph $H$ satisfying $H\not\in\{K_2, K_4\}$ contains a matching vertex-cutset with size at most three, and this bound is tight. |
| title | Complexity and Algorithm for the Matching vertex-cutset Problem |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2501.13217 |