The Path Contraction and Cycle Contraction problems take as input an undirected graph G with n vertices, m edges and an integer k and determine whether one can obtain a path or a cycle, respectively, by performing at most k edge contractions in G. We revisit these NP-complete problems and prove the following results. Central to these results is an algorithm for a general variant of Path Contraction, namely, Path Contraction With Constrained Ends. We also give an \(\mathcal {O}^*(2.5191^n)\) -time algorithm to solve the optimization version of Cycle Contraction. Next, we turn our attention to restricted graph classes and show the following results. The second result complements the \(\mathcal {O}(nm)\) -time, i.e., \(\mathcal {O}(n^2 \cdot tw)\) -time, algorithm known for the problem [Discret. Appl. Math. 2014].

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Revisiting Path Contraction and Cycle Contraction

  • R. Krithika,
  • V. K. Kutty Malu,
  • Prafullkumar Tale

摘要

The Path Contraction and Cycle Contraction problems take as input an undirected graph G with n vertices, m edges and an integer k and determine whether one can obtain a path or a cycle, respectively, by performing at most k edge contractions in G. We revisit these NP-complete problems and prove the following results. Central to these results is an algorithm for a general variant of Path Contraction, namely, Path Contraction With Constrained Ends. We also give an \(\mathcal {O}^*(2.5191^n)\) -time algorithm to solve the optimization version of Cycle Contraction. Next, we turn our attention to restricted graph classes and show the following results. The second result complements the \(\mathcal {O}(nm)\) -time, i.e., \(\mathcal {O}(n^2 \cdot tw)\) -time, algorithm known for the problem [Discret. Appl. Math. 2014].