Parameterized complexity classification of deletion to list matrix-partition for low-order matrices
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 |
Tilhørende fil(er)
Denne innførselen finnes i følgende samling(er)
-
Department of Informatics [917]
-
Registrations from Cristin [9487]