Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2408.09591 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916365236961280 |
|---|---|
| author | An, Shinwoo Chang, Yeonsu Cho, Kyungjin Kwon, O-joung Lee, Myounghwan Oh, Eunjin Shin, Hyeonjun |
| author_facet | An, Shinwoo Chang, Yeonsu Cho, Kyungjin Kwon, O-joung Lee, Myounghwan Oh, Eunjin Shin, Hyeonjun |
| contents | Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Pre-assignment for Uniquification of Minimum Vertex Cover problem (shortly PAU-VC) is the problem, for given a graph $G$, to find a minimum set $S$ of vertices in $G$ such that there is a unique minimum vertex cover of $G$ containing $S$. We show that PAU-VC is fixed-parameter tractable parameterized by clique-width, which improves an exponential algorithm for trees given by Horiyama et al. Among natural graph classes with unbounded clique-width, we show that the problem can be solved in linear time on split graphs and unit interval graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09591 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs An, Shinwoo Chang, Yeonsu Cho, Kyungjin Kwon, O-joung Lee, Myounghwan Oh, Eunjin Shin, Hyeonjun Data Structures and Algorithms Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Pre-assignment for Uniquification of Minimum Vertex Cover problem (shortly PAU-VC) is the problem, for given a graph $G$, to find a minimum set $S$ of vertices in $G$ such that there is a unique minimum vertex cover of $G$ containing $S$. We show that PAU-VC is fixed-parameter tractable parameterized by clique-width, which improves an exponential algorithm for trees given by Horiyama et al. Among natural graph classes with unbounded clique-width, we show that the problem can be solved in linear time on split graphs and unit interval graphs. |
| title | Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.09591 |