Show simple item record

Finding disjoint paths on edge-colored graphs: more tractability results

hal.structure.identifier
dc.contributor.authorDondi, Riccardo
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
dc.date.accessioned2019-04-30T10:41:41Z
dc.date.available2019-04-30T10:41:41Z
dc.date.issued2018
dc.identifier.issn1382-6905
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18867
dc.language.isoenen
dc.subjectParameterized complexityen
dc.subjectApproximationen
dc.subjectSocial networksen
dc.subjectEdge-colored graphsen
dc.subject.ddc003en
dc.titleFinding disjoint paths on edge-colored graphs: more tractability resultsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe problem of finding the maximum number of vertex-disjointuni-color paths in anedge-colored graph (called MaxCDP) has been recently introduced in literature, motivatedby applications in social network analysis. In this paper we investigate how the complexity ofthe problem depends on graph parameters (namely the number of vertices to remove to makethe graph a collection of disjoint paths and the size of the vertex cover of the graph), which makes sense since graphs in social networks are not random and have structure. The problemwas known to be hard to approximate in polynomial time and not fixed-parameter tractable (FPT) for the natural parameter. Here, we show that it is still hard to approximate, evenin FPT-time. Finally, we introduce a new variant of the problem, called MaxCDDP, whosegoal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDPis already hard on graphs at distance two from disjoint paths.en
dc.relation.isversionofjnlnameJournal of Combinatorial Optimization
dc.relation.isversionofjnlvol36en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2018-11
dc.relation.isversionofjnlpages1315-1332en
dc.relation.isversionofdoi10.1007/s10878-017-0238-6en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-22T09:27:43Z
hal.identifierhal-02115531*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
155324627752555.pdf
Size:
221.0Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record