Maximum disjoint paths on edge-colored graphs: approximability and tractability
type: Item
instance of: scholarly article
title: Maximum disjoint paths on edge-colored graphs: approximability and tractability
zbMATH Open document ID: 1461.68144
author: Paola Bonizzoni
author: Riccardo Dondi
author: Yuri Pirola
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate the approximation and parameterized complexity of the problem. First, we show that, for any constant \(\varepsilon >0\), the problem is not approximable within factor \(c^{1-\varepsilon}\), where \(c\) is the number of colors, and that the corresponding decision problem is W[1]-hard when parametrized by the number of disjoint paths. Then, we present a fixed-parameter algorithm for the problem parameterized by the number and the length of the disjoint paths.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7042147
zbMATH Keywords: social networks
zbMATH Keywords: disjoint paths
zbMATH Keywords: fixed-parameter algorithms
zbMATH Keywords: hardness of approximation
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6010001
OpenAlex ID: W2142971798
cites work: Q4397004
cites work: On the maximum disjoint paths problem on edge-colored graphs
cites work: Q4258216
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
cites work: Q5710169
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Color-coding
cites work: Upper and lower bounds for finding connected motifs in vertex-colored graphs
cites work: Complexity issues in vertex-colored graph pattern matching
cites work: Algorithm engineering for color-coding with applications to signaling pathway detection
cites work: Variants of constrained longest common subsequence
cites work: A faster parameterized algorithm for set packing
cites work: Faster fixed-parameter tractable algorithms for matching and packing problems
cites work: Q2934608
cites work: Balanced Hashing, Color Coding and Approximate Counting
DOI: 10.3390/A6010001
description: scientific article; zbMATH DE number 7042147