Connected Tropical Subgraphs in Vertex-Colored Graphs

Jean-Alexandre Angles d'Auriac (1) , Nathann Cohen (1) , Hakim Maftouhi (1) , Ararat Harutyunyan (1) , Sylvain Legay (1) , Yannis Manoussakis (1)

1 LRI - Laboratoire de Recherche en Informatique

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the original graph at least once. In this work we study the problem of finding a minimal connected tropical subgraph. We show that this problem is NP-Hard for trees, interval graphs and split graphs, but polynomial when the number of colors is logarithmic on the number of vertices of the graph. We give results that provide upper bounds for the order of the minimal connected tropical subgraph under various sufficient conditions, for example, minimal degree or number of edges. We finaly study sufficient and necessary conditions for a random graph to have a tropical subgraph such that each color is present precisely once.

Domaines: Combinatoire [math.CO]; Algorithme et structure de données [cs.DS]; Complexité [cs.CC]

Jean-Alexandre Angles d'Auriac, Nathann Cohen, Hakim Maftouhi, Ararat Harutyunyan, Sylvain Legay, et al.. Connected Tropical Subgraphs in Vertex-Colored Graphs. 9th International colloquium on graph theory and combinatorics, Jun 2014, Grenoble, France. ⟨hal-01077567⟩