Pith. sign in

REVIEW 3 major objections 4 minor 70 references

Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper maps exactly which structural parameters make bounded-size coalition formation tractable, delivering FPT algorithms for treewidth plus capacity and for vertex cover, with matching lower bounds under ETH.

desk verdict A substantial parameterized complexity study with a sound algorithmic core and a load-bearing but likely fixable constant error in the tree-depth hardness proof. read the letter →

arxiv 2505.22384 v1 pith:2IKDLOJU submitted 2025-05-28 cs.DS cs.AI

Foivos Fioravantes , Harmender Gahlawat , Nikolaos Melissinos This is my paper
classification cs.DScs.AI
keywords coalitionformationadditiveseparablehedonicgamesboundedsizeparameterizedcomplexitytreewidthvertexcoverkernelizationW[1]-hardness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks when agents with pairwise preferences can be split into teams of size at most C so that the total weight of edges inside teams is maximized, and whether the task admits algorithms whose exponential cost is controlled by a structural parameter rather than by the number of agents. Its central claim is a map: with treewidth plus the capacity C, the weighted problem is fixed-parameter tractable in time (twC)^{O(tw)}$n^{{O(1)}}$; the dependence on C is unavoidable because the unweighted problem is already W[1]-hard parameterized by tree-depth alone; and on graphs of bounded vertex cover a $vc^{{O(vc)}}$$n^{{O(1)}}$-time algorithm is essentially optimal under the Exponential Time Hypothesis. The paper also shows that the unweighted version has a polynomial kernel parameterized by vertex cover plus C, while the weighted version has none unless the polynomial hierarchy collapses. If the map is right, exact solutions are available exactly on the structural classes where the paper claims them, and approximation-oriented approaches are not needed there.

What carries the argument

The carrying object of the main positive result is the notion of an 'important' C-partition of a bag-coloring type: for each node of a nice tree decomposition, the dynamic program keeps, for every coloring of the bag's vertices by tw+1 named coalitions and every table of sizes up to C, a single partition of maximum value among those of that type. This collapses the state space to (twC)^{O(tw)} entries per bag. The vertex-cover algorithm uses a different mechanism: guess the restriction of an optimal partition to a vertex cover U, then reduce the assignment of the independent-set vertices to a maximum-weight matching in an auxiliary graph. The lower-bound machinery reduces from General Factors for tree-depth hardness and from a bounded-occurrence variant of 3-SAT for the ETH bound, while the kernel gap is obtained through an auxiliary bipartite matching reduction rule and a reduction from Multicolored Clique.

What would settle it

Substitute A = $n^{2}$, B = $5n^{2}$ + 3m + 4, C = $100n^{3}$ into the size of the two gadgets in Theorem 1.2; if, as appears, |V(F^v)| + |V(F)| = C + 16 − 2α rather than C − 2α, then the forward direction's sets C_v exceed the capacity and the reduction as written is falsified, with a corrected constant B = $5n^{2}$ + 3m + 20 restoring the identity.

Watch

Extended reading notes

Core claim

The paper's discovery is a parameterized complexity classification of C-Coalition Formation in additive separable hedonic games with symmetric unit or natural-weight valuations. On the positive side, Weighted C-Coalition Formation can be solved in (twC)^{O(tw)}$n^{{O(1)}}$ time via bottom-up dynamic programming over a nice tree decomposition, and in $vc^{{O(vc)}}$$n^{{O(1)}}$ time when the graph has vertex cover number vc. On the negative side, C-Coalition Formation is W[1]-hard parameterized by tree-depth, so the factor C in the treewidth algorithm cannot be removed; and under ETH it admits no (Cvc)^{o(vc+C)}$n^{{O(1)}}$ algorithm, matching the vertex-cover algorithm. The kernelization picture separates the two versions: the unweighted problem has an O($vc^{2}$ C)-vertex kernel, while the weighted problem admits no polynomial kernel parameterized by vc+C unless the polynomial hierarchy collapses. Additional results place vertex integrity on the FPT side and twin-cover on the W[1]-hard side.

Load-bearing premise

The tree-depth hardness theorem depends on an asserted gadget-size identity, |V(F^v)| + |V(F)| = C − 2α, which fixes exactly how many vertices can be packed into each constructed coalition; if the constants in the constructed graph do not satisfy it, the reduction's capacity accounting breaks.

Editorial extensions

If this is right

  • Any bounded-capacity coalition-formation instance whose preference graph has small treewidth can be solved exactly, and the same dynamic program works for arbitrary natural-number weights.
  • No exact FPT algorithm parameterized by treewidth alone can exist for the problem, so the capacity parameter C is genuinely needed in the treewidth result.
  • On graphs with small vertex cover, exact solutions with only polynomial dependence on C are possible, and under ETH the running time cannot be substantially improved.
  • For the unweighted problem the input can be preprocessed to O(vc^2 C) vertices, but for the weighted problem no such polynomial compression exists unless the polynomial hierarchy collapses.
  • Because every optimal solution is Nash-stable, the positive algorithms also produce Nash-stable team structures.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The tree-depth hardness proof (Theorem 1.2) relies on an asserted gadget-size identity, |V(F^v)| + |V(F)| = C − 2α. Substituting the paper's constants A = n^2, B = 5n^2 + 3m + 4, C = 100n^3 gives C + 16 − 2α instead; the constructed sets C_v then exceed capacity, so the reduction as written needs a constant correction such as B = 5n^2 + 3m + 20. This is an editorial check of the written proof, not
  • If that reduction is repaired, a natural next step is to decide whether C-Coalition Formation is FPT for feedback vertex number or neighborhood diversity, parameters the paper leaves open, mirroring the vertex-integrity/twin-cover dichotomy.
  • The treewidth DP's (twC)^{O(tw)} running time suggests a concrete practical benchmark: test it on random graphs with tw ≤ 10 against ILP or branch-and-bound to see where the constant in the exponent becomes prohibitive.
  • One could extend the classification to directed or asymmetric valuations, since the paper analyzes only symmetric undirected preferences.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies C-Coalition Formation and its weighted variant, where the input is an undirected edge-weighted graph and the goal is to partition the vertices into parts of size at most C maximizing the total weight of internal edges. The main results are: an FPT algorithm for the weighted case parameterized by treewidth plus C running in (twC)^{O(tw)} n^{O(1)} (Theorem 1.1); W[1]-hardness parameterized by tree-depth (Theorem 1.2); an FPT algorithm parameterized by vertex cover running in vc^{O(vc)} n^{O(1)} (Theorem 1.3); an ETH-based lower bound excluding (Cvc)^{o(vc+C)} (Theorem 1.4); an O(vc^2 C)-vertex kernel for the unweighted case (Theorem 1.5); a kernelization lower bound for the weighted case (Theorem 1.6); FPT for vertex integrity (Theorem 1.7); and W[1]-hardness for twin-cover number (Theorem 1.8). The hardness results use self-contained reductions from General Factors, R3-SAT, k-Multicolored Clique, and Unary Bin Packing.

Significance. If the proofs are repaired, this is a substantial contribution to the parameterized complexity of bounded-size coalition formation. The treewidth DP and the vertex-cover matching reformulation are clean, explicit, and give concrete running times; the kernelization dichotomy between the weighted and unweighted cases is interesting; and the lower-bound reductions are standard in form. The paper is also transparent about the unresolved C<tw case in Section 6. The main caveat is that Theorem 1.2 is invalid as written, and the advertised optimality of the treewidth algorithm is not fully justified by the stated vertex-cover lower bound. These issues are localized and appear fixable, so the central classification is likely defensible after revision.

major comments (3)
  1. [§3.2 (Theorem 1.2)] The proof's capacity accounting is off by 16 under the printed constants. The text asserts that |V(F^v) ∪ V(F)| = C − 2αv, but with A = n^2, B = 5n^2 + 3m + 4, D = 2m + 5, a vertex-gadget F_{4,C−B,2m+10} has 4 + (C−B) + (2m+10) = C − 5n^2 − m + 10 vertices and a list-gadget F_{m+6,5A−2α} has (m+6) + (5n^2 − 2α) vertices, so their union has C + 16 − 2α vertices. Consequently, in the forward direction the constructed set C_v = V(F^v) ∪ V(F) ∪ U_v has size C + 16 and violates the capacity, and the later bound that at most 2αv vertices of VE can be included should read at most 2αv − 16. The reduction is restored by setting B = 5n^2 + 3m + 20, which also preserves the inequality C − B > 24nA used in Lemma 3.2, but Theorem 1.2 is not valid as written.
  2. [§3.2 (edge-gadget construction)] The construction of the translator edges is misstated. As printed, the sentence 'We add all the edges between V1(F^u) and Ve' attaches the set Ve to V1(F^u), and the following sentences attach the w_L and w_R vertices to V1(F^u) and V1(F^v); no edge is added between V1(F^e) and Ve. Under this text, V(F^e) is an isolated component, Lemma 3.7 has no basis, and the later definition of the edge set E′ of the General Factors solution cannot function. The intended first attachment should be V1(F^e)–Ve, with V1(F^u) attached to the w_L vertices and V1(F^v) to the w_R vertices. This is a localized but load-bearing transcription error in the same reduction.
  3. [Abstract, §1, and §6] The paper presents Theorem 1.4 as proving that the treewidth algorithm of Theorem 1.1 is 'essentially optimal', but the theorem and its proof are formulated for the parameter pair (vc+C), and the reduction only upper-bounds vc. Since tw ≤ vc always, a lower bound in vc+C does not exclude algorithms with running time (twC)^{o(tw+C)} unless the constructed instances also satisfy tw = Ω(vc). The proof in §3.3 does not establish such a lower bound on tw. The remark in §6 that the lower bound applies to instances with C ≥ vc ≥ tw does not close this gap. Either the reduction must show tw = Ω(vc) for the constructed graphs, or the optimality claim should be restricted to the vertex-cover parameter and Theorem 1.3.
minor comments (4)
  1. [§3.2, last paragraph] The stated tree-depth bound '3m + 9' does not follow from the preceding deletion argument: the proof first deletes 4m vertices for VL, then 4 vertices for a VR-component, while the largest remaining component has tree-depth at most 2m + 5, giving a bound such as 6m + 10. Since the theorem only needs a computable bound in m, this is a constant error, but it should be corrected.
  2. [§4.2, Theorem 1.6 proof] In the reverse direction, the count of weight-4C^3 edges inside each C_i is off by one: I_i has size C − log n − 1, so the term should be 4C^3(C − log n − 1), not 4C^3(C − log n). With the printed value, the intermediate total exceeds the target threshold by k·4C^3, and the subsequent comparison about the extra kC(2,2)(2 log n + 1) value does not line up. This appears to be a transcription error, but it should be fixed.
  3. [§5.1, ILP constraint (3)] In the displayed ILP, the subscript of v in constraint (3) appears as z instead of l, so the constraint should read v_{i,j,l} to match the vectors τ_i^j and the preceding definition.
  4. [§2.4] There is a duplicated word in 'We have that that twc ≤ f vc'; the extra 'that' should be removed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all algorithmic and hardness claims are proved from external problems or direct constructions, with the sole self-citation being a conference-version footnote that is not load-bearing.

full rationale

The paper's derivation chain is self-contained against external sources. Theorem 1.1 is a direct bottom-up dynamic program on nice tree decompositions, with correctness proved in the text and no fitted parameters. Theorem 1.2 is a W[1]-hardness reduction from General Factors, citing the external source [39] for the source problem's hardness and then giving an explicit gadget construction; the proof does not rely on any result from the present authors' prior work. Theorem 1.3 enumerates vertex-cover partitions and reduces the remaining problem to maximum-weight matching, a standard polynomial-time problem. Theorem 1.4 reduces from R3-SAT through a fully specified construction, and its ETH lower bound follows from the external 3-SAT hypothesis. Theorems 1.5 and 1.6 are respectively a kernel with an explicit reduction rule and an incompressibility reduction from k-Multicolored Clique citing the external kernel lower bound [43]. Theorems 1.7 and 1.8 use an ILP formulation and a reduction from Unary Bin Packing [46], respectively. The only self-citation is [31], identified as the AAAI-2025 preliminary version, and it is not used in any proof or as support for any claim. The arithmetic inconsistency flagged by the skeptic in Section 3.2 (the asserted vertex counts) is a potential correctness issue within an externally based reduction, not a circularity: the reduction's source instance is defined independently of the target problem's optimal value, and the claimed identity is a checkable algebraic fact rather than an input disguised as an output. No step fits the patterns of self-definition, fitted-input prediction, load-bearing self-citation, imported uniqueness, ansatz smuggling, or renaming of a known result. Therefore the correct circularity score is 0.

Assumptions & free parameters 6 free parameters · 7 assumptions · 0 invented entities

All constants listed above are reduction design values verified by explicit inequalities inside the proofs rather than empirical fits; they are listed for transparency because they are hand-chosen. The only constant that fails its verification is B in Theorem 1.2, where the size identity used in the proof is off by 16. The hardness results rest on standard external assumptions (ETH, W[1] != FPT, PH does not collapse) and imported hardness theorems; none of the paper's own claims is used to prove itself.

free parameters (6)
  • B = 5n^2 + 3m + 4 (Theorem 1.2 reduction constant) = 5n^2 + 3m + 4
    Hand-chosen gadget size constant. As written it is inconsistent with the asserted identity |V(F^v)| + |V(F)| = C - 2alpha, since the true value is C + 16 - 2alpha; setting B = 5n^2 + 3m + 20 would restore the proof.
  • C = 100n^3, A = n^2, D = 2m+5 (Theorem 1.2) = C = 100n^3, A = n^2, D = 2m+5
    Design constants for the General Factors reduction, each verified by explicit inequalities in the proof (for example C - B > 24nA). Not fitted to data; listed for transparency.
  • C = 42N log n, N = ceil(n/log^2 n) (Theorem 1.4) = 42N log n with N = ceil(n/log^2 n)
    Capacity and gadget scale for the R3-SAT reduction; chosen so that C and the vertex cover number are both O(n/log n), making the ETH lower bound close.
  • C = C(k,2) + k log n + 1 and weights 4C^3, 3C^2, 2C (Theorem 1.6) = C = C(k,2) + k log n + 1, weights 4C^3, 3C^2, 2C, 1
    Design constants for the k-Multicolored Clique kernel lower bound; the weights are chosen to force the structural lemmas (Lemmas 4.2 through 4.4).
  • C = B + 1 (Theorem 1.8) = B + 1
    Capacity set to one more than the bin size in the Unary Bin Packing reduction; this makes each coalition holding a bin vertex plus full items exactly full.
  • t = vc*C + C (kernel matching multiplicity, Theorem 1.5) = vc*C + C
    Number of copies of each vertex-cover vertex in the auxiliary bipartite graph; the extra C copies provide the free-vertex budget needed in Lemma 4.1.
assumptions (7)
  • domain assumption ETH: 3-SAT cannot be solved in 2^{o(n+m)} time
    Explicitly stated in Section 2.3; underpins Lemma 3.10 and Theorem 1.4.
  • domain assumption W[1] is not contained in FPT
    Standard parameterized intractability hypothesis; underpins the interpretation of Theorems 1.2 and 1.8.
  • domain assumption The polynomial hierarchy does not collapse
    Explicitly stated in Theorem 1.6; needed for the no-polynomial-kernel conclusion.
  • standard math General Factors is W[1]-hard on bipartite graphs parameterized by the smaller bipartition size
    Proposition 3.1 imports this from [39]; it is the source problem of the Theorem 1.2 reduction.
  • standard math k-Multicolored Clique has no kernel of size poly(k + log n) unless the polynomial hierarchy collapses
    Imported from [43]; the source of Theorem 1.6's kernel lower bound via a polynomial parameter transformation.
  • standard math Unary Bin Packing with k bins is W[1]-hard parameterized by k
    Imported from [46]; the source problem of Theorem 1.8.
  • standard math Nice tree decompositions of width tw exist and are computable in FPT time; Lenstra's ILP solver runs in FPT time in the number of variables; Edmonds' maximum weight matching is polynomial
    Background algorithmic facts invoked by Theorems 1.1, 1.3, 1.5 and 1.7; standard and cited.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size." pith.science (2026). https://pith.science/paper/2IKDLOJU

@misc{pith2026250522384,
  author       = {Pith},
  title        = {Pith review of: Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2IKDLOJU}},
  note         = {Machine review of arXiv:2505.22384}
}
read the original abstract

Imagine we want to split a group of agents into teams in the most \emph{efficient} way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied \textsc{Coalition Formation} problem. Here, we study a version of this problem where each team must additionally be of bounded size. We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded \emph{treewidth}) for ``small'' teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, there can be no algorithm that vastly outperforms the one we present, under reasonable theoretical assumptions, even when considering star-like structures (bounded \emph{vertex cover number}).

Figures

Figures reproduced from arXiv: 2505.22384 by the authors.

Figure 1
Figure 1. Overview of our results. A parameter A appearing linked to a parameter B with A being below B is to be understood as “there is a function f such that f(A) ≥ f(B)”. In blue (red resp.) we exhibit the FPT (W[1]-hardness resp.) results we provide. The clique number of the graph is denoted by ω. Note that our FPT results are for the more general, weighted version of the problem (C-CFw), while our W[1]-hardness results a… view at source ↗
Figure 2
Figure 2. An example of possible solutions to the unweighted version of the [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. The gadgets used in the proof of Theorem 1.2 [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: The graph G constructed in the proof of Theorem 1.2. Our goal is to show that an optimal C-partition P of G has value v(P) = mv|V (H)| + mℓ |V (H)| 2 + me|E(H)| + 10A|V (H)| + 8|E(H)| if and only if (H, L) is a yes-instance of the General Factors problem. Assume that P…
Figure 5
Figure 5. Figure 5: The gadget Gi,j used in the construction of Theorem 1.4. Finally, notice that the number of variables and clauses that were added is linear in regards to n+m. Therefore, we cannot have an algorithm that runs in 2 o(n+m) and decides whether the new instance is satisfiab…
Figure 6
Figure 6. Figure 6: The graph G constructed in the proof of Theorem 1.6. The vertex vyz represents the edge of H with endpoints the vertices y and z such that y ∈ Vi and z ∈ Vj (for some i < j ∈ [k]). The red edges joining the vertex vyz to the red vertices of V i and V j are according to…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

70 extracted references · 59 canonical work pages

  1. [1]

    Alessandro Aloisio, Michele Flammini, and Cosimo Vinci. 2020. The impact of self- ishness in hypergraph hedonic games. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 1766–1773

    work page 2020

  2. [2]

    Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Do- minik Peters. 2019. Fractional hedonic games.ACM Transactions on Economics and Computation (TEAC)7, 2 (2019), 1–29

    work page 2019

  3. [3]

    Haris Aziz, Felix Brandt, and Hans Georg Seedig. 2013. Computing desirable parti- tions in additively separable hedonic games.Artificial Intelligence 195 (2013), 316– 334

    work page 2013

  4. [4]

    Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghad- dam. 2013. Optimal coalition structure generation in cooperative graph games. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 27. 81–87. 44

    work page 2013

  5. [5]

    Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, and Stefan Szei- der. 2012. The complexity of planning revisited—a parameterized analysis. InPro- ceedings of the AAAI Conference on Artificial Intelligence, Vol. 26. 1735–1741

    work page 2012

  6. [6]

    Nathanaël Barrot, Kazunori Ota, Yuko Sakurai, and Makoto Yokoo. 2019. Unknown agents in friends oriented hedonic games: Stability and complexity. InProceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 1756–1763

    work page 2019

  7. [7]

    Nathanaël Barrot and Makoto Yokoo. 2019. Stable and Envy-free Partitions in He- donic Games.. InIJCAI. 67–73

    work page 2019

  8. [8]

    Theparameterizedcomplexityofglobalconstraints

    Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Claude Guy Quimper, andTobyWalsh.2008. Theparameterizedcomplexityofglobalconstraints. In AAAI Conference on Artificial Intelligence. AAAI Press, 235–240

    work page 2008

Show all 70 references
  1. [9]

    Vittorio Bilò, Gianpiero Monaco, and Luca Moscardelli. 2022. Hedonic games with fixed-sizecoalitions.In Proceedings of the AAAI Conference on Artificial Intelligence

    2022

  2. [10]

    Bodlaender

    Hans L. Bodlaender. 1996. A Linear-Time Algorithm for Finding Tree- Decompositions of Small Treewidth. SIAM J. Comput. 25, 6 (1996), 1305–1317. https://doi.org/10.1137/S0097539793251219

    1996 doi

  3. [11]

    Bodlaender

    Hans L. Bodlaender. 1998. A partialk-arboretum of graphs with bounded treewidth. Theoretical Computer Science 209, 1 (1998), 1–45. https://doi.org/10.1016/ S0304-3975(97)00228-4

    1998

  4. [12]

    Niclas Boehmer and Edith Elkind. 2020. Individual-based stability in hedonic diver- sity games. InProceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 1822–1829

    2020

  5. [13]

    Anna Bogomolnaia and Matthew O Jackson. 2002. The stability of hedonic coalition structures. Games and Economic Behavior38, 2 (2002), 201–230

    2002

  6. [14]

    Felix Brandt, Martin Bullinger, and Anaëlle Wilczynski. 2023. Reaching individually stable coalition structures. ACM Transactions on Economics and Computation11, 1-2 (2023), 1–65

    2023

  7. [15]

    Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia

  8. [16]

    Robert Bredereck, Jiehua Chen, Rolf Niedermeier, and Toby Walsh. 2017. Parlia- mentary voting procedures: Agenda control, manipulation, and uncertainty.Journal of Artificial Intelligence Research59 (2017), 133–173

    2017

  9. [17]

    Martin Bullinger and Stefan Kober. 2021. Loyalty in Cardinal Hedonic Games.. In IJCAI. 66–72. 45

    2021

  10. [18]

    Jiehua Chen, Gergely Csáji, Sanjukta Roy, and Sofia Simola. 2023. Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 202...

    2023

  11. [19]

    Agnes Cseh, Tamás Fleiner, and Petra Harján. 2019. Pareto Optimal Coalitions of Fixed Size. Journal of Mechanism and Institution Design4 (2019), 1

    2019

  12. [20]

    Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2015.Parameterized Algo- rithms. Springer. https://doi.org/10.1007/978-3-319-21275-3

    2015 doi

  13. [21]

    Andreas Darmann, Edith Elkind, Sascha Kurz, Jérôme Lang, Joachim Schauer, and Gerhard Woeginger. 2018. Group activity selection problem with approval prefer- ences. International Journal of Game Theory47 (2018), 767–796

    2018

  14. [22]

    Xiaotie Deng and Christos H Papadimitriou. 1994. On the complexity of cooperative solution concepts. Mathematics of operations research19, 2 (1994), 257–266

    1994

  15. [23]

    2012.Graph Theory, 4th Edition

    Reinhard Diestel. 2012.Graph Theory, 4th Edition. Graduate texts in mathematics, Vol. 173. Springer. https://doi.org/10.1007/978-3-662-53622-3

    2012 doi

  16. [25]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. 2013.Fundamentals of Parameterized Complexity. Springer. https://doi.org/10.1007/978-1-4471-5559-1

    2013 doi

  17. [26]

    Dregi, and Pim van ’t Hof

    Pål Grønås Drange, Markus S. Dregi, and Pim van ’t Hof. 2016. On the Computa- tional Complexity of Vertex Integrity and Component Order Connectivity.Algorith- mica 76, 4 (2016), 1181–1202

    2016

  18. [27]

    Jacques H Dreze and Joseph Greenberg. 1980. Hedonic coalitions: Optimality and stability. Econometrica: Journal of the Econometric Society(1980), 987–1003

    1980

  19. [28]

    Jack Edmonds. 1965. Paths, Trees, and Flowers.Canadian Journal of Mathematics 17 (1965), 449–467. https://doi.org/10.4153/CJM-1965-045-4

    1965 doi

  20. [29]

    Angelo Fanelli, Gianpiero Monaco, Luca Moscardelli, et al. 2021. Relaxed core sta- bility in fractional hedonic games. InProceedings of the Thirtieth International Joint Conference on Artificial Intelligence. 182–188

    2021

  21. [30]

    M. R. Fellows. 2006. The Lost Continent of Polynomial Time: Preprocessing and Kernelization (IWPEC’06). Springer-Verlag, Berlin, Heidelberg, 276–277. https: //doi.org/10.1007/11847250_25 46

    2006 doi

  22. [31]

    Foivos Fioravantes, Harmender Gahlawat, and Nikolaos Melissinos. 2025. Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39. 13847– 13855

    2025

  23. [32]

    Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom, and Shmuel Zaks. 2018. Online coalition structure generation in graph games. InPro- ceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. 1353–1361

    2018

  24. [33]

    Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer. https://doi.org/10.1007/3-540-29953-X

    2006 doi

  25. [34]

    Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi

    Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. 2019.Ker- nelization: Theory of Parameterized Preprocessing. Cambridge University Press. https://doi.org/10.1017/9781107415157

    2019 doi

  26. [35]

    Robert Ganian. 2011. Twin-Cover: Beyond Vertex Cover in Parameterized Algo- rithmics. InParameterized and Exact Computation - 6th International Symposium, IPEC 2011 (Lecture Notes in Computer Science, Vol. 7112). Springer, 259–271. https://doi.org/10.1007/978-3-642-28050-4_21

    2011 doi

  27. [36]

    Robert Ganian, Thekla Hamm, Dušan Knop, Šimon Schierreich, and Ondřej Such` y

  28. [37]

    Yong Gao. 2009. Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability.Artificial Intelligence 173, 14 (2009), 1343–1366

    2009

  29. [38]

    Jiong Guo and Rolf Niedermeier. 2007. Invitation to data reduction and problem kernelization. ACM SIGACT News38, 1 (2007), 31–45

    2007

  30. [39]

    Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider, and Anders Yeo.2012

    Gregory Z. Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider, and Anders Yeo.2012. ParameterizedComplexityResultsforGeneralFactorsinBipartiteGraphs with an Application to Constraint Programming.Algorithmica 64, 1 (2012), 112– 125

    2012

  31. [40]

    Tesshu Hanaka, Airi Ikeyama, and Hirotaka Ono. 2023. Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-Like Graphs. InCombina- torial Optimization and Applications - 17th International Conference, COCOA 2023, Hawaii, HI, USA, December 15-17, 20...

    2023

  32. [41]

    Tesshu Hanaka, Hironori Kiya, Yasuhide Maei, and Hirotaka Ono. 2019. Computa- tional Complexity of Hedonic Games on Sparse Graphs. InPRIMA 2019: Principles and Practice of Multi-Agent Systems - 22nd International Conference, Turin, Italy, October 28-31, 2019, Proceedings. 47

    2019

  33. [42]

    Tesshu Hanaka and Michael Lampis. 2022. Hedonic Games and Treewidth Revisited. In 30th Annual European Symposium on Algorithms, ESA 2022. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

    2022

  34. [43]

    Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu

  35. [44]

    Ayumi Igarashi, Kazunori Ota, Yuko Sakurai, and Makoto Yokoo. 2019. Robustness against agent failure in hedonic games. InProceedings of the 28th International Joint Conference on Artificial Intelligence. 364–370

    2019

  36. [45]

    Russell Impagliazzo and Ramamohan Paturi. 2001. On the Complexity of k-SAT.J. Comput. Syst. Sci.62, 2 (2001), 367–375. https://doi.org/10.1006/JCSS.2000. 1727

    2001 doi

  37. [46]

    Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. 2013. Bin packing with fixed number of bins revisited. J. Comput. System Sci.79, 1 (2013), 39–49. https://doi.org/10.1016/j.jcss.2012.04.004

    2013 doi

  38. [47]

    Ton Kloks. 1994. Treewidth, Computations and Approximations. Lecture Notes in Computer Science, Vol. 842. Springer. https://doi.org/10.1007/BFb0045375

    1994 doi

  39. [48]

    Tuukka Korhonen and Daniel Lokshtanov. 2023. An Improved Parameterized Algo- rithm for Treewidth. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023. ACM, 528–541. https://doi.org/10.1145/3564246. 3585245

    2023 doi

  40. [49]

    Euiwoong Lee. 2017. Partitioning a graph into small pieces with applications to path transversal. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1546–1558

    2017

  41. [50]

    H. W. Lenstra Jr. 1983. Integer Programming with a Fixed Number of Variables. Mathematics of Operations Research8, 4 (1983), 538–548

    1983

  42. [51]

    Chaya Levinger, Amos Azaria, and Noam Hazon. 2023. Social Aware Coalition Formation with Bounded Coalition Size. InProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. 2667–2669

    2023

  43. [52]

    Fu Li. 2021. Fractional Hedonic Games With a Limited Number of Coalitions. InPro- ceedings of the 22nd Italian Conference on Theoretical Computer Science, Bologna, Italy, September 13-15, 2021

    2021

  44. [53]

    Silviu Maniu, Pierre Senellart, and Suraj Jog. 2019. An experimental study of the treewidth of real-world graph data. InICDT 2019–22nd International Conference on Database Theory. 48

    2019

  45. [54]

    Gianpiero Monaco and Luca Moscardelli. 2023. Nash Stability in Fractional Hedo- nic Games with Bounded Size Coalitions. InInternational Conference on Web and Internet Economics

    2023

  46. [55]

    Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. 2021. Additively Separable Hedonic Games with Social Context.Games 12, 3 (2021), 71

    2021

  47. [56]

    2006.Invitation to Fixed-Parameter Algorithms

    Rolf Niedermeier. 2006.Invitation to Fixed-Parameter Algorithms. Oxford University Press. https://doi.org/10.1093/ACPROF:OSO/9780198566076.001.0001

    2006

  48. [57]

    Rolf Niedermeier and Peter Rossmanith. 2000. A general method to speed up fixed- parameter-tractable algorithms. Inform. Process. Lett.73, 3-4 (2000), 125–129

    2000

  49. [58]

    Kazunori Ohta, Nathanaël Barrot, Anisse Ismaili, Yuko Sakurai, and Makoto Yokoo

  50. [59]

    Martin Olsen. 2009. Nash stability in additively separable hedonic games and com- munity structures.Theory of Computing Systems45 (2009), 917–925

    2009

  51. [60]

    Dominik Peters. 2016. Graphical hedonic games of bounded treewidth. InProceedings of the AAAI Conference on Artificial Intelligence, Vol. 30

    2016

  52. [61]

    Dominik Peters. 2016. Towards Structural Tractability in Hedonic Games. InPro- ceedings of the AAAI Conference on Artificial Intelligence

    2016

  53. [62]

    Dominik Peters and Edith Elkind. 2015. Simple causes of complexity in hedonic games. InProceedings of the 24th International Conference on Artificial Intelligence. 617–623

    2015

  54. [63]

    Walid Saad, Zhu Han, Tamer Basar, Mérouane Debbah, and Are Hjorungnes. 2010. Hedonic coalition formation for distributed task allocation among wireless agents. IEEE Transactions on Mobile Computing10, 9 (2010), 1327–1344

    2010

  55. [64]

    Jakub Sliwinski and Yair Zick. 2017. Learning Hedonic Games.. InIJCAI. 2730– 2736

    2017

  56. [65]

    Johan M. M. van Rooij, Marcel E. van Kooten Niekerk, and Hans L. Bodlaender

  57. [66]

    Karsten Weihe. 1998. Covering trains by stations or the power of data reduction. Proceedings of Algorithms and Experiments, ALEX(1998), 1–8. 49

    1998

  58. [2013]

    Partition Into Triangles on Bounded Degree Graphs.Theory Comput. Syst. 52, 4 (2013), 687–718

    2013

  59. [2015]

    A Completeness Theory for Polynomial (Turing) Kernelization.Algorithmica 71, 3 (2015), 702–730

    2015

  60. [2016]

    Cambridge University Press

    Handbook of computational social choice. Cambridge University Press

  61. [2017]

    Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals.. InIJCAI. 359–365

  62. [2023]

    Artificial Intelligence 325 (2023), 104017

    Hedonic diversity games: A complexity picture with more than two colors. Artificial Intelligence 325 (2023), 104017

    2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.