Sequence graphs: characterization and counting of admissible elements

Sammy Khalife (1)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

We present a family of graphs implicitly involved in sequential models, which are obtained by adding edges between elements of a discrete sequence appearing simultaneously in a window of size w, and study their combinatorial properties. First, we study the conditions for a graph to be a sequence graph. Second, we provide, when possible, the number of sequences it represents. For w = 2, unweighted 2-sequence graphs are simply connected graphs, whereas unweighted 2-sequence digraphs form a less trivial family. The decision and counting for weighted 2-sequence graphs can be transformed by reduction into Eulerian graph problems. Finally, we present a polynomial time algorithm to decide if an undirected and unweighted graph has the said property for w ≥ 3. The question of NP-hardness is left opened for other cases.

Domaines: Mathématique discrète [cs.DM]; Algorithme et structure de données [cs.DS]; Complexité [cs.CC]

Sammy Khalife. Sequence graphs: characterization and counting of admissible elements. 2021. ⟨hal-03109398⟩