Detecting induced subgraphs

Benjamin Lévêque (1) , David Y. Lin (2) , Frédéric Maffray (1) , Nicolas Trotignon (3)

1 G-SCOP_OC - Optimisation Combinatoire
2 Princeton University
3 CES - Centre d'économie de la Sorbonne

An s-graph is a graph with two kinds of edges : subdivisible edges and real edges. A realisation of an s-graphB is any graph obtained by subdividing subdivisible edges of B into paths of arbitrary length (at least one). Given an s-graph B, we study the decision problem Pi(B) whose instance is a graph G and whose question is "Does G contain a realisation of B as an induced subgraph ?".

Un s-graph est un graphe avec deux sortes d'arêtes : les arêtes subdivisibles et les vraies arêtes. Une réalisation d'un s-graph B est un graphe obtenu en subdivisant des arêtes subdivisibles de B en des chemins de taille arbitraire (au moin un). Etant donné un s-graph B, nous étudions le problème de décision Pi(B) dont l'instance est un graphe G et dont la question est "G contient-il une réalisation de B en tant que sous graphe induit ?".

Mots clés: Detection; induced; subgraph

Mots clés: sous-graphe; induit; détection

Domaines: Economies et finances; Mathématique discrète [cs.DM]; Combinatoire [math.CO]

Benjamin Lévêque, David Y. Lin, Frédéric Maffray, Nicolas Trotignon. Detecting induced subgraphs. 2007. ⟨halshs-00180953⟩