On Poset Sandwich Problems.

Michel Habib (1) , David Kelly (1) , Emmanuelle Lebhar (1) , Christophe Paul (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

A graph G8 = (V,E8) is a sandwich for a pair of graph Gt=(V,E_t) and G = (V, E) si Et ⊆ E8 ⊆E. Any poset, or partially ordered set, admits a unique graph representation which is directed and transitive. In this paper we introduce the notion of sandwich poset problems inspired by former sandwich problems on comparability graphs. In particular, we are interested in series-parallel and interval posets which are subclasses of 2-dimensional posets, we describe polynomial algorithms for these two classes of poset sandwich problems and then prove that the problem of deciding the existence of a 2-dimensional sandwich poset is NP-complete.

Un graphe G8= (V, Es) est un graphe sandwich de la paire de graphes Gt=(V, Et) et G = (V, E) si Et ⊆ E8 ⊆E. Tout ordre partiel admet une représentation en graphe unique, ce graphe est orienté et transitif. Dans ce article, nous introduisons la notion de problèmes d’ordres sandwich inspirée des problèmes sandwich existants sur les graphes de comparabilité. En particulier, nous nous sommes intéressés aux ordres série-parallèles et aux ordres d’intervalle qui sont des sous-classes des ordres de dimension 2, nous décrivons des algorithmes polynomiaux pour ces deux classes de problèmes d’ordre sandwich puis nous démontrons que le problème de décider de l’existence d’un ordre sandwich de dimension 2 est NP-complet

Mots clés: Analysis of Algorithms; Graph Sandwich Problems; Partially Ordered Sets

Mots clés: Analyse d'algorithmes; Ordres partiels; Problèmes de graphes sandwich

Domaines: Informatique [cs]

Michel Habib, David Kelly, Emmanuelle Lebhar, Christophe Paul. On Poset Sandwich Problems.. [Research Report] LIP RR-2003-27, Laboratoire de l'informatique du parallélisme. 2003, 2+8p. ⟨hal-02101856⟩