License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.41
URN: urn:nbn:de:0030-drops-115372
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11537/
Go to the corresponding LIPIcs Volume Portal


Agrawal, Akanksha ; Kolay, Sudeshna ; Madathil, Jayakrishnan ; Saurabh, Saket

Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices

pdf-format:
LIPIcs-ISAAC-2019-41.pdf (3 MB)


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
Seminar: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI