Please use this identifier to cite or link to this item: http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/5797
Title: Parameterized Complexity of Satisfactory Partition Problem
Authors: GAIKWAD, AJINKYA
MAITY, SOUMEN
TRIPATHI, SHUVAM KANT
Dept. of Mathematics
Keywords: Parameterized complexity
FPT
W[1]-hard
Treewidth
Clique-width
2020
Issue Date: Dec-2020
Publisher: Springer Nature
Citation: Combinatorial Optimization and Applications, 76-90.
Abstract: The Satisfactory Partition problem consists in deciding if the set of vertices of a given undirected graph can be partitioned into two nonempty parts such that each vertex has at least as many neighbours in its part as in the other part. The Balanced Satisfactory Partition problem is a variant of the above problem where the two partite sets are required to have the same cardinality. Both problems are known to be NP-complete. This problem was introduced by Gerber and Kobler [European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors, but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The three main results of the paper are the following: (1) The Satisfactory Partition problem is polynomial-time solvable for block graphs, (2) The Satisfactory Partition problem and its balanced version can be solved in polynomial time for graphs of bounded clicque-width, and (3) A generalized version of the Satisfactory Partition problem is W[1]-hard when parametrized by treewidth.
URI: http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/5797
ISBN: 9783030648435
9783030648435
Appears in Collections:BOOK CHAPTERS

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.