Computing Pivot-Minors

doi:10.1007/s00453-026-01393-5

Computing Pivot-Minors

2026-05-01

0

PRE

AI

Mamadou Moustapha Kanté

DOI：10.1007/s00453-026-01393-5

原文链接

原文求助

摘要

En 中文

图G包含图H为枢轴-子图，如果H可以通过对G应用一系列顶点删除和边枢轴操作得到。枢轴-子图在秩宽度的研究中扮演着重要角色。枢轴-子图的研究主要从结构角度进行。本文首次对枢轴-子图进行了系统性的计算复杂性研究。首先，我们证明PIVOT-MINOR问题——即判断给定图G是否包含与给定图H同构的枢轴-子图——是NP完全的。如果H不是输入的一部分，我们将该问题记为H-PIVOT-MINOR。当H是P-3+tP(1)（t为某个整数且t≥0）的诱导子图、H为K(1,t)（t为某个整数且t≥1）或|V(H)|≤4时（除非H∈{K-4, C-3+P-1}），我们给出了H-PIVOT-MINOR问题的认证多项式时间算法。令FH为包含与H同构的枢轴-子图的最小诱导子图集合。为证明上述结论，我们或者证明存在整数CH使得FH中的所有图至多有CH个顶点，或者针对上述每种情况精确确定FH。

Keyword:

certifying algorithm

computational complexity

pivot-minor

Computing Pivot-Minors

摘要

期刊

机构

引用论文