License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.41
URN: urn:nbn:de:0030-drops-115372
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11537/
Agrawal, Akanksha ;
Kolay, Sudeshna ;
Madathil, Jayakrishnan ;
Saurabh, Saket
Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices
Abstract
Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G) - > 2^{[l]} (where [l] = {1,2,...,l}), a list M-partition of G with respect to L is a partition of V(G) into l parts, say, V_1, V_2, ..., V_l such that for each i,j in {1,2,...,l}, (i) if m_{i,j}=0 then for any u in V_i and v in V_j, uv not in E(G), (ii) if m_{i,j}=1 then for any (distinct) u in V_i and v in V_j, uv in E(G), (iii) for each v in V(G), if v in V_i then i in L(v). We consider the Deletion to List M-Partition problem that takes as input a graph G, a list function L:V(G) - > 2^[l] and a positive integer k. The aim is to determine whether there is a k-sized set S subseteq V(G) such that G-S has a list M-partition. Many important problems like Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion, Multiway Cut and Deletion to List Homomorphism are special cases of the Deletion to List M-Partition problem. In this paper, we provide a classification of the parameterized complexity of Deletion to List M-Partition, parameterized by k, (a) when M is of order at most 3, and (b) when M is of order 4 with all diagonal entries belonging to {0,1}.
BibTeX - Entry
@InProceedings{agrawal_et_al:LIPIcs:2019:11537,
author = {Akanksha Agrawal and Sudeshna Kolay and Jayakrishnan Madathil and Saket Saurabh},
title = {{Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {41:1--41:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11537},
URN = {urn:nbn:de:0030-drops-115372},
doi = {10.4230/LIPIcs.ISAAC.2019.41},
annote = {Keywords: list matrix partitions, parameterized classification, Almost 2-SAT, important separators, iterative compression}
}
|
Keywords: |
|
list matrix partitions, parameterized classification, Almost 2-SAT, important separators, iterative compression |
|
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
28.11.2019 |
