2026-08-12T04:19:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22166 2024-12-04T06:53:44Z ddc:004 open_access

Core Stability in Additively Separable Hedonic Games of Low Treewidth Hanaka, Tesshu Köhler, Noleen Lampis, Michael Hedonic games Treewidth Core stability Additively Separable Hedonic Games (ASHGs) are coalition-formation games where we are given a directed graph whose vertices represent n selfish agents and the weight of each arc uv denotes the preferences from u to v. We revisit the computational complexity of the well-known notion of core stability of symmetric ASHGs, where the goal is to construct a partition of the agents into coalitions such that no group of agents would prefer to diverge from the given partition and form a new coalition. For Core Stability Verification (CSV), we first show the following hardness results: CSV remains coNP-complete on graphs of vertex cover 2; CSV is coW[1]-hard parameterized by vertex integrity when edge weights are polynomially bounded; and CSV is coW[1]-hard parameterized by tree-depth even if all weights are from {-1,1}. We complement these results with essentially matching algorithms and color{black}{an FPT algorithm parameterized by the treewidth tw plus the maximum degree Δ (improving a previous algorithm’s dependence from 2^O(twΔ²)} to 2^O(twΔ)).} We then move on to study Core Stability (CS), which one would naturally expect to be even harder than CSV. We confirm this intuition by showing that CS is Σ₂^p-complete even on graphs of bounded vertex cover number. On the positive side, we present a 2^{2^O(Δtw)}n^O(1)-time algorithm parameterized by tw+Δ, which is essentially optimal assuming Exponential Time Hypothesis (ETH). Finally, we consider the notion of k-core stability: k denotes the maximum size of the allowed blocking (diverging) coalitions. We show that k-CSV is coW[1]-hard parameterized by k (even on unweighted graphs), while k-CS is NP-complete for all k ≥ 3 (even on graphs of bounded degree with bounded edge weights). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tesshu Hanaka and Noleen Köhler and Michael Lampis 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.39 urn:nbn:de:0030-drops-221662 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.39 eng https://creativecommons.org/licenses/by/4.0/legalcode