The four-in-a-tree problem in triangle-free graphs

Nicolas Derhy; Christophe Picouleau; Nicolas Trotignon

halshs-00270623, version 1

The four-in-a-tree problem in triangle-free graphs

Nicolas Derhy () ¹, Christophe Picouleau () ¹, Nicolas Trotignon () ²

Documents de travail du Centre d'Economie de la Sorbonne 2008.23 - ISSN : 1955-611X (2008)

Abstract: The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n4) whether three given vertices of a graph belong to an induced tree. Here, we study four-in-a-tree for triangle-free graphs. We give a structural answer to the following question : how does look like a triangle-free graph such that no induced tree covers four given vertices ? Our main result says that any such graph must have the "same structure", in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete.

1: Centre d'Etude et De Recherche en Informatique du Cnam (CEDRIC)
Conservatoire National des Arts et Métiers (CNAM)
2: Centre d'économie de la Sorbonne (CES)
CNRS : UMR8174 – Université Paris I - Panthéon-Sorbonne

halshs-00270623, version 1
http://halshs.archives-ouvertes.fr/halshs-00270623
oai:halshs.archives-ouvertes.fr:halshs-00270623
From: Lucie Label <>
Submitted on: Monday, 7 April 2008 10:23:55
Updated on: Monday, 7 April 2008 12:09:26

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

%F halshs-00270623, version 1
%0 Unpublished Work
%U http://halshs.archives-ouvertes.fr/halshs-00270623
%T The four-in-a-tree problem in triangle-free graphs
%A Derhy, Nicolas
%A Picouleau, Christophe
%A Trotignon, Nicolas
%+ Centre d'Etude et De Recherche en Informatique du Cnam - CEDRIC , Centre d'économie de la Sorbonne - CES
%G English
%X The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n4) whether three given vertices of a graph belong to an induced tree. Here, we study four-in-a-tree for triangle-free graphs. We give a structural answer to the following question : how does look like a triangle-free graph such that no induced tree covers four given vertices ? Our main result says that any such graph must have the "same structure", in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete.
%X L'algorithme "three-in-a-tree" de Chudnovsky et Seymour décide en temps O(n4) si trois sommets donnés d'un graphe appartiennent à un arbre induit. Ici, nous étudions four-in-a-tree pour les graphes sans triangles. Nous donnons une réponse structurelle à la question suivante : à quoi ressemble un graphe sans triangles dont aucun arbre induit ne couvre quatre sommets donnés ? Notre résultat principal affirme qu'un tel graphe doit avoir la "même structure", dans un sens précisemment défini, qu'un carré ou un cube. Nous donnons un algorithme en temps O(nm) qui étant donné un graphe sans triangles G et quatre de ses sommets, retourne ou bien un arbre induit qui contient les sommets, ou bien une partition de V(G) certifiant qu'un tel arbre n'existe pas. Nous prouvons que le problème consistant à décider s'il existe un arbre T couvrant les quatre sommets et tel qu'au plus un sommet de T est de degré au moins 3 est NP-complet.
%2 SHS:ECO;SHS:STAT;MATH:MATH_CO;INFO:INFO_DM
%8 2008-03-00
%Z Documents de travail du Centre d'Economie de la Sorbonne 2008.23 - ISSN : 1955-611X
%K Three, four, tree, algorithm, 3-in-a-tree, 4-in-a-tree, triangle-free graphs.
%K Trois, quatre, arbre, algorithme, 3-in-a-tree, 4-in-a-tree, graphes sans triangles.
%Z URL des Documents de travail : http://ces.univ-paris1.fr/cesdp/CESFramDP2008.htm