Connected Tropical Subgraphs in Vertex-Colored Graphs
Jean-Alexandre Anglès d'Auriac, Nathann Cohen, Hakim El Mafthoui, Ararat Harutyunyan, Sylvain Legay, Yannis Manoussakis
Abstract
A subgraph of a vertex-colored graph is said to be tropical whenever
it contains each color of the graph. In this work we study the problem
of finding a minimal connected tropical subgraph. We first show that
this problem is NP-Hard for trees, interval graphs and split graphs,
but polynomial when the number of colors is logarithmic in terms of
the order of the graph (i.e. FPT). We then provide upper bounds for
the order of the minimal connected tropical subgraph under various
conditions. We finally study the problem of finding a connected
tropical subgraph in a randomly vertex-colored random graph.
Full Text: PDF PostScript