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

Nicolas Derhy (), Christophe Picouleau () and Nicolas Trotignon ()
Additional contact information
Nicolas Derhy: CEDRIC - Centre d'études et de recherche en informatique et communications - ENSIIE - Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise - CNAM - Conservatoire National des Arts et Métiers [CNAM]
Christophe Picouleau: CEDRIC - Centre d'études et de recherche en informatique et communications - ENSIIE - Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise - CNAM - Conservatoire National des Arts et Métiers [CNAM]
Nicolas Trotignon: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

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.

Keywords: Three; four; tree; algorithm; triangle-free graph; trois; quatre; arbre; algorithme; 3-in-a-tree; 4-in-a-tree; graphes sans triangles (search for similar items in EconPapers)
Date: 2008-03
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00270623
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in 2008

Downloads: (external link)
https://shs.hal.science/halshs-00270623/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-00270623

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().