dc.contributor.author Agrawal, Akanksha dc.contributor.author Kolay, Sudeshna dc.contributor.author Madathil, Jayakrishnan dc.contributor.author Saurabh, Saket dc.date.accessioned 2021-01-12T10:45:33Z dc.date.available 2021-01-12T10:45:33Z dc.date.created 2020-03-02T18:08:12Z dc.date.issued 2019 dc.Published Leibniz International Proceedings in Informatics. 2019, 149:41 1-14. en_US dc.identifier.issn 1868-8969 dc.identifier.uri https://hdl.handle.net/11250/2722528 dc.description.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}. en_US dc.language.iso eng en_US dc.publisher Dagstuhl Publishing en_US dc.rights Navngivelse 4.0 Internasjonal * dc.rights.uri http://creativecommons.org/licenses/by/4.0/deed.no * dc.title Parameterized complexity classification of deletion to list matrix-partition for low-order matrices en_US dc.type Journal article en_US dc.type Peer reviewed en_US dc.description.version publishedVersion en_US dc.rights.holder Copyright 2019 The Authors en_US dc.source.articlenumber 41 en_US cristin.ispublished true cristin.fulltext original cristin.qualitycode 1 dc.identifier.doi 10.4230/LIPIcs.ISAAC.2019.41 dc.identifier.cristin 1799073 dc.source.journal Leibniz International Proceedings in Informatics en_US dc.source.40 149 en_US dc.source.pagenumber 1-14 en_US
﻿

### This item appears in the following Collection(s)

Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal