تقرير
Computing pivot-minors
| العنوان: | Computing pivot-minors |
|---|---|
| المؤلفون: | Dabrowski, Konrad K., Dross, François, Jeong, Jisu, Kanté, Mamadou Moustapha, Kwon, O-joung, Oum, Sang-il, Paulusma, Daniël |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Data Structures and Algorithms |
| الوصف: | A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. Pivot-minors have mainly been studied from a structural perspective. In this paper we perform the first systematic computational complexity study of pivot-minors. We first prove that the Pivot-Minor problem, which asks if a given graph $G$ contains a pivot-minor isomorphic to a given graph $H$, is NP-complete. If $H$ is not part of the input, we denote the problem by $H$-Pivot-Minor. We give a certifying polynomial-time algorithm for $H$-Pivot-Minor when (1) $H$ is an induced subgraph of $P_3+tP_1$ for some integer $t\geq 0$, (2) $H=K_{1,t}$ for some integer $t\geq 1$, or (3) $|V(H)|\leq 4$ except when $H \in \{K_4,C_3+ P_1\}$. Let ${\cal F}_H$ be the set of induced-subgraph-minimal graphs that contain a pivot-minor isomorphic to $H$. To prove the above statement, we either show that there is an integer $c_H$ such that all graphs in ${\cal F}_H$ have at most $c_H$ vertices, or we determine ${\cal F}_H$ precisely, for each of the above cases. Comment: 33 pages, 9 figures. An extended abstract appeared in the proceedings of WG2018 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2311.04656 |
| رقم الأكسشن: | edsarx.2311.04656 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |