A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the initial graph. In this work we study the problem of finding tropical paths in vertex-colored graphs. There are two versions for this problem: the shortest tropical path problem (STPP), i.e., finding a tropical path with the minimum total weight, and the maximum tropical path problem (MTPP), i.e., finding a path with the maximum number of colors possible. We show that both versions of this problems are NP-hard for directed acyclic graphs, cactus graphs and interval graphs. Moreover, we also provide a fixed parameter algorithm for STPP in general graphs and several polynomial-time algorithms for MTPP in specific graphs, including bipartite chain graphs, threshold graphs, trees, block graphs, and proper interval graphs.

Tropical paths in vertex-colored graphs / Cohen, J.; Italiano, Giuseppe Francesco; Manoussakis, Y.; Thang, N. K.; Pham, H. P.. - In: JOURNAL OF COMBINATORIAL OPTIMIZATION. - ISSN 1382-6905. - 42:3(2021), pp. 476-498. [10.1007/s10878-019-00416-y]

Tropical paths in vertex-colored graphs

Italiano G. F.;
2021

Abstract

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the initial graph. In this work we study the problem of finding tropical paths in vertex-colored graphs. There are two versions for this problem: the shortest tropical path problem (STPP), i.e., finding a tropical path with the minimum total weight, and the maximum tropical path problem (MTPP), i.e., finding a path with the maximum number of colors possible. We show that both versions of this problems are NP-hard for directed acyclic graphs, cactus graphs and interval graphs. Moreover, we also provide a fixed parameter algorithm for STPP in general graphs and several polynomial-time algorithms for MTPP in specific graphs, including bipartite chain graphs, threshold graphs, trees, block graphs, and proper interval graphs.
NP-hard; Polynomial algorithms; Tropical paths; Vertex-colored graphs
Tropical paths in vertex-colored graphs / Cohen, J.; Italiano, Giuseppe Francesco; Manoussakis, Y.; Thang, N. K.; Pham, H. P.. - In: JOURNAL OF COMBINATORIAL OPTIMIZATION. - ISSN 1382-6905. - 42:3(2021), pp. 476-498. [10.1007/s10878-019-00416-y]
File in questo prodotto:
File Dimensione Formato  
2019_Article_TropicalPathsInVertex-coloredG.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: Tutti i diritti riservati
Dimensione 612.36 kB
Formato Adobe PDF
612.36 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/192107
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact