License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.2
URN: urn:nbn:de:0030-drops-173580
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17358/
Agrawal, Akanksha ;
Bhattacharjee, Sutanay ;
Jana, Satyabrata ;
Sahu, Abhishek
Parameterized Complexity of Perfectly Matched Sets
Abstract
For an undirected graph G, a pair of vertex disjoint subsets (A, B) is a pair of perfectly matched sets if each vertex in A (resp. B) has exactly one neighbor in B (resp. A). In the above, the size of the pair is |A| (= |B|). Given a graph G and a positive integer k, the Perfectly Matched Sets problem asks whether there exists a pair of perfectly matched sets of size at least k in G. This problem is known to be NP-hard on planar graphs and W[1]-hard on general graphs, when parameterized by k. However, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we study the problem parameterized by k, and design FPT algorithms for: i) apex-minor-free graphs running in time 2^O(√k)⋅ n^O(1), and ii) K_{b,b}-free graphs. We obtain a linear kernel for planar graphs and k^?(d)-sized kernel for d-degenerate graphs. It is known that the problem is W[1]-hard on chordal graphs, in fact on split graphs, parameterized by k. We complement this hardness result by designing a polynomial-time algorithm for interval graphs.
BibTeX - Entry
@InProceedings{agrawal_et_al:LIPIcs.IPEC.2022.2,
author = {Agrawal, Akanksha and Bhattacharjee, Sutanay and Jana, Satyabrata and Sahu, Abhishek},
title = {{Parameterized Complexity of Perfectly Matched Sets}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {2:1--2:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-260-0},
ISSN = {1868-8969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17358},
URN = {urn:nbn:de:0030-drops-173580},
doi = {10.4230/LIPIcs.IPEC.2022.2},
annote = {Keywords: Perfectly Matched Sets, Parameterized Complexity, Apex-minor-free graphs, d-degenerate graphs, Planar graphs, Interval Graphs}
}
|
Keywords: |
|
Perfectly Matched Sets, Parameterized Complexity, Apex-minor-free graphs, d-degenerate graphs, Planar graphs, Interval Graphs |
|
Collection: |
|
17th International Symposium on Parameterized and Exact Computation (IPEC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
