Tropical paths in vertex-colored graphs

Johanne Cohen (), Giuseppe F. Italiano (), Yannis Manoussakis (), Nguyen Kim Thang () and Hong Phong Pham ()
Additional contact information
Johanne Cohen: University Paris-Saclay
Giuseppe F. Italiano: University of Rome “Tor Vergata”
Yannis Manoussakis: University Paris-Saclay
Nguyen Kim Thang: University Paris-Saclay
Hong Phong Pham: University Paris-Saclay

Journal of Combinatorial Optimization, No 0, 23 pages

Abstract: 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.

Keywords: Tropical paths; Vertex-colored graphs; Polynomial algorithms; NP-hard (search for similar items in EconPapers)
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00416-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v::y::i::d:10.1007_s10878-019-00416-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00416-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().