Agrawal, Akanksha ;
Kolay, Sudeshna ;
Madathil, Jayakrishnan ;
Saurabh, Saket
Parameterized Complexity Classification of Deletion to List MatrixPartition for LowOrder 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 Mpartition 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 MPartition 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 ksized set S subseteq V(G) such that GS has a list Mpartition. 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 MPartition problem. In this paper, we provide a classification of the parameterized complexity of Deletion to List MPartition, 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 MatrixPartition for LowOrder Matrices}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {41:141:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11537},
URN = {urn:nbn:de:0030drops115372},
doi = {10.4230/LIPIcs.ISAAC.2019.41},
annote = {Keywords: list matrix partitions, parameterized classification, Almost 2SAT, important separators, iterative compression}
}
28.11.2019
Keywords: 

list matrix partitions, parameterized classification, Almost 2SAT, important separators, iterative compression 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 