# On Poset Sandwich Problems

3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A graph $G_s=(V,E_s)$ is a sandwich for a pair of graph $G_t=(V,E_t)$ and $G=(V,E)$ if $E_t\subseteq E_s\subseteq 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.
Type de document :
Communication dans un congrès
EuroComb: European Conference on Combinatorics, Graph Theory and Applications, 2003, Prague, Czech Republic. 2003
Domaine :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269577
Contributeur : Christine Carvalho de Matos <>
Soumis le : mercredi 6 février 2019 - 12:57:18
Dernière modification le : jeudi 7 février 2019 - 01:25:18

### Identifiants

• HAL Id : lirmm-00269577, version 1

### Citation

Michel Habib, David Kelly, Emmanuelle Lebhar, Christophe Paul. On Poset Sandwich Problems. EuroComb: European Conference on Combinatorics, Graph Theory and Applications, 2003, Prague, Czech Republic. 2003. 〈lirmm-00269577〉

### Métriques

Consultations de la notice