论文标题
将双方图缩入小周期的复杂性
The Complexity of Contracting Bipartite Graphs into Small Cycles
论文作者
论文摘要
对于一个正整数$ \ ell \ geq 3 $，$ c_ \ ell $ - 可交解性问题是输入无方向的简单图$ g $，并确定是否只能使用Edge Crossistions使用$ \ ell $ dertices的$ c_ \ ell $转换为$ c_ \ ell $（$ \ ell $ vertices上的诱导循环）。 Brouwer和Veldman [JGT 1987]表明，在一般图中，$ C_4 $ - 收集性是NP的完整性。很容易验证$ c_3 $ - 收缩性是多项式时间可解决的。 Dabrowski和Paulusma [IPL 2017]表明，$ c _ {\ ell} $ - 合同性是\ np-complete \ in tiptite graphs for $ \ ell = 6 $ = 6 $ = 6 $，并作为开放问题所构成的问题是$ \ ell $ $ $ $ $ 4或5的问题。图。
For a positive integer $\ell \geq 3$, the $C_\ell$-Contractibility problem takes as input an undirected simple graph $G$ and determines whether $G$ can be transformed into a graph isomorphic to $C_\ell$ (the induced cycle on $\ell$ vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed that $C_4$-Contractibility is NP-complete in general graphs. It is easy to verify that $C_3$-Contractibility is polynomial-time solvable. Dabrowski and Paulusma [IPL 2017] showed that $C_{\ell}$-Contractibility is \NP-complete\ on bipartite graphs for $\ell = 6$ and posed as open problems the status of the problem when $\ell$ is 4 or 5. In this paper, we show that both $C_5$-Contractibility and $C_4$-Contractibility are NP-complete on bipartite graphs.
