2026-07-26T21:06:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11537 2024-03-06T10:48:15Z ddc:004 open_access

Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices Agrawal, Akanksha Kolay, Sudeshna Madathil, Jayakrishnan Saurabh, Saket list matrix partitions parameterized classification Almost 2-SAT important separators iterative compression 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}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Sudeshna Kolay and Jayakrishnan Madathil and Saket Saurabh 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.41 urn:nbn:de:0030-drops-115372 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.41 eng https://creativecommons.org/licenses/by/3.0/legalcode