Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/5792| Title: | The Balanced Satisfactory Partition Problem |
| Authors: | GAIKWAD, AJINKYA MAITY, SOUMEN TRIPATHI, SHUVAM KANT Dept. of Mathematics |
| Keywords: | Parameterized complexity FPT W[1]-hard Treewidth Neighbourhood diversity 2021-APR-WEEK2 TOC-APR-2021 2021 |
| Issue Date: | Jan-2021 |
| Publisher: | Springer Nature |
| Citation: | Lecture Notes in Computer Science book series (LNCS) Vol. 12607, 322-336. |
| Abstract: | The Satisfactory Partition problem asks whether it is possible to partition the vertex set of a given undirected graph into two parts such that each vertex has at least as many neighbours in its own 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 but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The two main results of the paper are the following: (1) The Satisfactory Partition problem and its balanced version are fixed parameter tractable (FPT) when parametrized by neighbourhood diversity, (2) The Balanced Satisfactory Partition problem is W[1]-hard when parametrized by treewidth. |
| URI: | http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/5792 |
| ISBN: | 9783030677305 9783030677312 |
| 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.