Maximum disjoint paths on edge-colored graphs: approximability and tractability (Q1736537): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 06:44, 1 February 2024

scientific article
Language Label Description Also known as
English
Maximum disjoint paths on edge-colored graphs: approximability and tractability
scientific article

    Statements

    Maximum disjoint paths on edge-colored graphs: approximability and tractability (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    26 March 2019
    0 references
    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.
    0 references
    social networks
    0 references
    disjoint paths
    0 references
    fixed-parameter algorithms
    0 references
    hardness of approximation
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references