Document Open Access Logo

Parameterized Complexity of Conflict-Free Matchings and Paths

Authors Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.35.pdf
  • Filesize: 0.62 MB
  • 15 pages

Document Identifiers

Author Details

Akanksha Agrawal
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel
Pallavi Jain
  • Institute of Mathematical Sciences, HBNI, Chennai, India
Lawqueen Kanesh
  • Institute of Mathematical Sciences, HBNI, Chennai, India
Saket Saurabh
  • University of Bergen, Bergen, Norway
  • Institute of Mathematical Sciences, HBNI, Chennai, India
  • UMI ReLax

Funding

  • Agrawal, Akanksha: PBC Program of Fellowships for Outstanding Post-doctoral Researchers from China and India, reference no. 5101479000.
  • Jain, Pallavi: SERB-NPDF fellowship, reference no. PDF/2016/003508, DST, India.
  • Saurabh, Saket: Horizon 2020 Framework program, the European Research Council (ERC) Consolidator Grant LOPPRE reference no. 819416.

Cite As Get BibTex

Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh. Parameterized Complexity of Conflict-Free Matchings and Paths. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.35

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Conflict-free
  • Matching
  • Shortest Path
  • FPT algorithm
  • W[1]-hard
  • Matroid

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Daniel Lokshtanov, and Saket Saurabh. Conflict Free Feedback Vertex Set: A Parameterized Dichotomy. 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS, pages 53:1-53:15, 2018. Google Scholar
  2. Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra, and Saket Saurabh. Exploring the Kernelization Borders for Hitting Cycles. 13th International Symposium on Parameterized and Exact Computation, IPEC, pages 14:1-14:14, 2018. Google Scholar
  3. Richard Bellman. On a routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958. Google Scholar
  4. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  5. Andreas Darmann, Ulrich Pferschy, and Joachim Schauer. Determining a minimum spanning tree with disjunctive constraints. International Conference on Algorithmic DecisionTheory (ADT), pages 414-423, 2009. Google Scholar
  6. Andreas Darmann, Ulrich Pferschy, Joachim Schauer, and Gerhard J. Woeginger. Paths, trees and matchings under disjunctive constraints. Discrete Applied Mathematics, 159(16):1726-1735, 2011. Google Scholar
  7. Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  8. Rodney G. Downey and Michael R. Fellows. Fixed Parameter Tractability and Completeness. Complexity Theory: Current Research, pages 191-225, 1992. Google Scholar
  9. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  10. Leah Epstein, Lene M. Favrholdt, and Asaf Levin. Online variable-sized bin packing with conflicts. Discrete Optimization, 8(2):333-343, 2011. Google Scholar
  11. Guy Even, Magnús M. Halldórsson, Lotem Kaplan, and Dana Ron. Scheduling with conflicts: online and offline algorithms. Journal of Scheduling, 12(2):199-224, 2009. Google Scholar
  12. Shimon Even and Oded Kariv. An O(n^2.5) algorithm for maximum matching in general graphs. Foundations of Computer Science (FOCS), pages 100-112, 1975. Google Scholar
  13. J. Flum and M. Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag, Secaucus, NJ, USA, 2006. Google Scholar
  14. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. Journal of the ACM, 63(4):29:1-29:60, 2016. Google Scholar
  15. Fedor V Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. Symposium on Discrete Algorithms (SODA), pages 142-151, 2014. Google Scholar
  16. Harold N. Gabow, Shachindra N Maheshwari, and Leon J. Osterweil. On two problems in the generation of program test paths. IEEE Transactions on Software Engineering, 2(3):227-231, 1976. Google Scholar
  17. Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47-56, 1974. Google Scholar
  18. Michel Gendreau, Gilbert Laporte, and Frédéric Semet. Heuristics and lower bounds for the bin packing problem with conflicts. Computers & OR, 31(3):347-358, 2004. Google Scholar
  19. Pallavi Jain, Lawqueen Kanesh, and Pranabendu Misra. Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized. Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia (CSR), pages 194-206, 2018. Google Scholar
  20. Klaus Jansen. An approximation scheme for bin packing with conflicts. Journal of combinatorial optimization, 3(4):363-377, 1999. Google Scholar
  21. Minghui Jiang. On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theoretical Computer Science, 411(49):4253-4262, 2010. Google Scholar
  22. Ton Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994. Google Scholar
  23. KW Krause, MA Goodwin, and RW Smith. Optimal software test planning through automated network analysis. TRW Systems Group, 1973. Google Scholar
  24. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Deterministic truncation of linear matroids. International Colloquium on Automata, Languages, and Programming (ICALP), pages 922-934, 2015. Google Scholar
  25. Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Covering small independent sets and separators with applications to parameterized algorithms. Symposium on Discrete Algorithms (SODA), pages 2785-2800, 2018. Google Scholar
  26. Dániel Marx. A parameterized view on matroid optimization problems. Theoretical Computer Science, 410(44):4471-4479, 2009. Google Scholar
  27. Dániel Marx. A parameterized view on matroid optimization problems. Theoretical Computer Science, 410(44):4471-4479, 2009. Google Scholar
  28. Silvio Micali and Vijay V Vazirani. An O(√|V||E|) algorithm for finding maximum matching in general graphs. Foundations of Computer Science (FOCS), pages 17-27, 1980. Google Scholar
  29. Moni Naor, Leonard J Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. Foundations of Computer Science (FOCS), pages 182-191, 1995. Google Scholar
  30. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2006. Google Scholar
  31. James G Oxley. Matroid theory, volume 3. Oxford University Press, 2006. Google Scholar
  32. Ulrich Pferschy and Joachim Schauer. The Knapsack Problem with Conflict Graphs. Journal of Graph Algorithms and Applications, 13(2):233-249, 2009. Google Scholar
  33. Ulrich Pferschy and Joachim Schauer. The maximum flow problem with conflict and forcing conditions. Network Optimization, pages 289-294, 2011. Google Scholar
  34. Ulrich Pferschy and Joachim Schauer. The maximum flow problem with disjunctive constraints. Journal of Combinatorial Optimization, 26(1):109-119, 2013. Google Scholar
  35. Ulrich Pferschy and Joachim Schauer. Approximation of knapsack problems with conflict and forcing graphs. Journal of Combinatorial Optimization, 33(4):1300-1323, 2017. Google Scholar
  36. Virginia Vassilevska Williams. Multiplying Matrices Faster Than Coppersmith-winograd. Symposium on Theory of Computing (STOC), pages 887-898, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact