.png){kind=icon}
Return
Computing Pivot-Minors
.png){kind=icon}
PRE
AI
DOI：10.1007/s00453-026-01393-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 H is an induced subgraph of P-3+tP(1) for some integer t >= 0 H = K(1,t )for some integer t >= 1 or |V(H)| <= 4 except when H is an element of (K-4, C-3 + P-1). Let FH 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 CH such that all graphs in FH have at most CH vertices, or we determine FH precisely, for each of the above cases.
Keywords:
certifying algorithm
computational complexity
pivot-minor
Journal
A
IF:
0.7
Papers:
56
Citations:
2.7K
Organization
View more organizations
Cited Papers
No cited papers available