dc.contributor.author Agrawal, Akanksha dc.contributor.author Jain, Pallavi dc.contributor.author Kanesh, Lawqueen dc.contributor.author Saurabh, Saket dc.date.accessioned 2021-01-12T10:42:20Z dc.date.available 2021-01-12T10:42:20Z dc.date.created 2019-12-18T12:54:16Z dc.date.issued 2019 dc.Published Leibniz International Proceedings in Informatics. 2019, 138, 35:1--35:15 en_US dc.identifier.issn 1868-8969 dc.identifier.uri https://hdl.handle.net/11250/2722526 dc.description.abstract An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) is a solution to I in Gamma, which is also an independent set in H. In this paper, we study conflict-free variants of Maximum Matching and Shortest Path, which we call Conflict-Free Matching (CF-Matching) and Conflict-Free Shortest Path (CF-SP), respectively. We show that both CF-Matching and CF-SP are W[1]-hard, when parameterized by the solution size. Moreover, W[1]-hardness for CF-Matching holds even when the input graph where we want to find a matching is itself a matching, and W[1]-hardness for CF-SP holds for conflict graph being a unit-interval graph. Next, we study these problems with restriction on the conflict graphs. We give FPT algorithms for CF-Matching when the conflict graph is chordal. Also, we give FPT algorithms for both CF-Matching and CF-SP, when the conflict graph is d-degenerate. Finally, we design FPT algorithms for variants of CF-Matching and CF-SP, where the conflicting conditions are given by a (representable) matroid. en_US dc.language.iso eng en_US dc.publisher Dagstuhl Publishing en_US dc.rights Navngivelse 4.0 Internasjonal * dc.rights.uri http://creativecommons.org/licenses/by/4.0/deed.no * dc.title Parameterized complexity of conflict-free matchings and paths en_US dc.type Journal article en_US dc.type Peer reviewed en_US dc.description.version publishedVersion en_US dc.rights.holder Copyright 2019 The Authors en_US dc.source.articlenumber 35 en_US cristin.ispublished true cristin.fulltext original cristin.qualitycode 1 dc.identifier.doi 10.4230/LIPIcs.MFCS.2019.35 dc.identifier.cristin 1762490 dc.source.journal Leibniz International Proceedings in Informatics en_US dc.source.40 138 en_US dc.source.pagenumber 35:1--35:15 en_US
﻿

### Denne innførselen finnes i følgende samling(er)

Med mindre annet er angitt, så er denne innførselen lisensiert som Navngivelse 4.0 Internasjonal