Details

Autor(en) / Beteiligte

• Gaikwad, Ajinkya
• Maity, Soumen
• Tripathi, Shuvam Kant

Titel

The Balanced Satisfactory Partition Problem

Ist Teil von

• SOFSEM 2021: Theory and Practice of Computer Science, p.322-336

Ort / Verlag

Cham: Springer International Publishing

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.