The Steiner Cycle and Path Cover Problem on Interval Graphs

Ante Custic, Stefan Lendl

Research output: Contribution to journalArticlepeer-review

Abstract

The Steiner path problem is a common generalization of the Steiner tree and the Hamiltonian path problem, in which we have to decide if for a given graph there exists a path visiting a fixed set of terminals. In the Steiner cycle problem we look for a cycle visiting all terminals instead of a path. The Steiner path cover problem is an optimization variant of the Steiner path problem generalizing the path cover problem, in which one has to cover all terminals with a minimum number of paths. We study those problems for the special class of interval graphs. We present linear time algorithms for both the Steiner path cover problem and the Steiner cycle problem on interval graphs given as endpoint sorted lists. The main contribution is a lemma showing that backward steps to non-Steiner intervals are never necessary. Furthermore, we show how to integrate this modification to the deferred-query technique of Chang et al. to obtain the linear running times.

Original languageEnglish
Pages (from-to)226-234
Number of pages9
JournalJournal of Combinatorial Optimization
Volume43
Issue number1
Early online date27 May 2021
DOIs
Publication statusPublished - Jan 2022

Keywords

  • Hamiltonian cycle
  • Interval graphs
  • Linear time
  • Steiner cycle

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics
  • Discrete Mathematics and Combinatorics
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this