Certifying Algorithms for the Path Cover and Related Problems on Interval Graphs

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves the answer has no compromised by a bug in the implementation. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to test whether a graph has a Hamiltonian cycle. A path cover of a graph is a family of vertex-disjoint paths that covers all vertices of the graph. The path cover problem is to find a path cover of a graph with minimum cardinality. The scattering number of a noncomplete connected graph

G

 = (

V

,

E

) is defined by

s

(

G

) =  max {

ω

(

G

 − 

S

) − |

S

|:

S

 ⊆ 

V

and

$\omega(G-S)\geqslant 1\}$

, in which

ω

(

G

 − 

S

) denotes the number of components of the graph

G

 − 

S

. The scattering number problem is to determine the scattering number of a graph. A recognition problem of graphs is to decide whether a given input graph has a certain property. To the best of our knowledge, most published certifying algorithms are to solve the recognition problems for special classes of graphs. This paper presents

O

(

n

)-time certifying algorithms for the above three problems, including Hamiltonian cycle problem, path cover problem, and scattering number problem, on interval graphs given a set of

n

intervals with endpoints sorted. The certificates provided by our algorithms can be authenticated in

O

(

n

) time.