2026-07-22T21:35:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10979 2024-03-06T10:46:58Z ddc:004 open_access

Parameterized Complexity of Conflict-Free Matchings and Paths Agrawal, Akanksha Jain, Pallavi Kanesh, Lawqueen Saurabh, Saket Conflict-free Matching Shortest Path FPT algorithm W[1]-hard Matroid 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Pallavi Jain and Lawqueen Kanesh and Saket Saurabh 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.35 urn:nbn:de:0030-drops-109798 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.35 eng https://creativecommons.org/licenses/by/3.0/legalcode