The Upper Clique Transversal Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914910546427904 |
|---|---|
| author | Milanič, Martin Uno, Yushi |
| author_facet | Milanič, Martin Uno, Yushi |
| contents | A clique transversal in a graph is a set of vertices intersecting all maximal cliques. The problem of determining the minimum size of a clique transversal has received considerable attention in the literature. In this paper, we initiate the study of the ''upper'' variant of this parameter, the upper clique transversal number, defined as the maximum size of a minimal clique transversal. We investigate this parameter from the algorithmic and complexity points of view, with a focus on various graph classes. We show that the corresponding decision problem is NP-complete in the classes of chordal graphs, chordal bipartite graphs, cubic planar bipartite graphs, and line graphs of bipartite graphs, but solvable in linear time in the classes of split graphs, proper interval graphs, and cographs, and in polynomial time for graphs of bounded cliquewidth. We conclude the paper with a number of open questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_14103 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Upper Clique Transversal Problem Milanič, Martin Uno, Yushi Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms 05C69 (Primary), 05C85, 05C75, 05C76, 68Q25, 68R10 (Secondary) A clique transversal in a graph is a set of vertices intersecting all maximal cliques. The problem of determining the minimum size of a clique transversal has received considerable attention in the literature. In this paper, we initiate the study of the ''upper'' variant of this parameter, the upper clique transversal number, defined as the maximum size of a minimal clique transversal. We investigate this parameter from the algorithmic and complexity points of view, with a focus on various graph classes. We show that the corresponding decision problem is NP-complete in the classes of chordal graphs, chordal bipartite graphs, cubic planar bipartite graphs, and line graphs of bipartite graphs, but solvable in linear time in the classes of split graphs, proper interval graphs, and cographs, and in polynomial time for graphs of bounded cliquewidth. We conclude the paper with a number of open questions. |
| title | The Upper Clique Transversal Problem |
| topic | Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms 05C69 (Primary), 05C85, 05C75, 05C76, 68Q25, 68R10 (Secondary) |
| url | https://arxiv.org/abs/2309.14103 |