Parameterized Complexity of Edge-Constrained Graph Partitioning

Positioning

• Unlike hedonic-game research on stability, this work studies feasibility-based coalition formation in which every coalition must satisfy a prescribed local utility constraint.The model also differs from graph-restricted coalition formation and correlation clustering by enforcing induced-edge constraints rather than connectivity or a global optimization objective.Source: §1 · pp. 2–3

Problem formulation

• ECGP partitions vertices into r parts each inducing at least γ edges, while BECGP additionally requires equal-sized parts.Signed variants replace edge counts with the difference between induced positive and negative edges, modeling local cooperation–conflict utilities.Source: §1 · p. 2

Kernelization

• ECGP and BECGP remain NP-hard for fixed r and γ, but both admit polynomial kernels parameterized by r + γ.The ECGP kernel has O(rγ^2) vertices and O((rγ)^2) edges, while the BECGP kernel has O(rγ^2 + r^2) vertices.Source: §1 · p. 2

Tractability

• Both problems are FPT parameterized by vertex integrity and vertex deletion distance to a clique, while ECGP is additionally FPT for cluster vertex deletion plus γ, maximum leaf number, and path deletion plus γ.The algorithms use N-fold ILP for vertex integrity and bounded-variable ILP with guessing and linearized edge counts for deletion to a clique; neighborhood diversity remains open.Source: §1 · p. 3

Tree-decomposition algorithm

• On a nice tree decomposition of width k, ECGP is solvable in O(n · r^(k+1) · (γ + 1)^(2r)) time.Together with kernelization, this yields parameterized algorithms for ECGP and BECGP, while the introduction leaves treewidth plus γ as an open case.Source: §1 · p. 3

Hardness

• ECGP and BECGP are W[1]-hard when parameterized by r together with feedback edge set, star or path deletion, modular width, or cluster vertex deletion.The hardness transfers to BECGP through a parameter-preserving reduction, and clique-width remains W[1]-hard even when γ = 3.Source: §1 · p. 3

Signed variants

• Signed ECGP and BECGP are NP-hard even when r + γ = 3 on graphs that are disjoint unions of two cliques.The balanced signed variant is additionally W[1]-hard parameterized by treedepth plus r plus γ, even when γ = 0.Source: §1 · p. 3

Problem definitions

• ECGP asks whether a graph’s vertices can be partitioned into r parts, each inducing at least γ edges.The notation E(G[Vi]) denotes the edges induced by part Vi.Source: §2 · p. 5
• BECGP adds the requirement that r divides n and every part has equal size n/r.Source: §2 · p. 5

Signed variants

• Signed ECGP replaces induced-edge counts with the utility |E+(Vi)| − |E−(Vi)|, requiring this difference to be at least γ in every part.Signed BECGP additionally requires equal part sizes.Source: §2 · p. 5

Structural parameters

• The preliminaries introduce structural parameters including feedback and tree-depth measures, decomposition widths, deletion distances, clique-width, vertex integrity, and maximum leaf number.They also establish standard notation for vertex cover, feedback edge sets, treedepth, treewidth, pathwidth, cluster vertex deletion, clique-width, vertex integrity, and deletion distances to graph classes.Source: §2 · pp. 5–6

Polynomial-time cases

• For r = 1, both BECGP and ECGP are solvable in polynomial time because the sole part is V(G), so feasibility is equivalent to |E(G)| ≥ γ.The algorithm simply checks the total number of graph edges.Source: §3 · p. 6

NP-hardness

• BECGP is NP-hard for r = 2 via a reduction from Minimum Bisection on cubic graphs.The reduction preserves balanced partitions and translates the internal-edge threshold into a bound on the cut size.Source: §3 · pp. 6–7

Polynomial-time cases

• For γ = 1, both BECGP and ECGP are solvable in polynomial time, since feasibility is equivalent to the existence of a matching of size at least r.A feasible partition yields vertex-disjoint intra-part edges, while a matching can be extended to a valid ECGP or balanced partition.Source: §3 · p. 7

NP-hardness

• Both BECGP and ECGP are NP-hard for γ = 2 through P3-Partition on bipartite graphs of maximum degree 3 [41].Because such graphs contain no triangles, every three-vertex part induces at least two edges exactly when it forms a P3.Source: §3 · p. 7

4.1 Kernelization Algorithm

• ECGP has a polynomial kernel with O(rγ^2) vertices and O((rγ)^2) edges when parameterized by r + γ.The kernel applies reduction rules for isolated vertices, large matchings, and γ-expansions, then bounds the reduced graph using a vertex cover and independent set.Source: §4.1 · pp. 8, 10
• BECGP has a polynomial kernel with O(rγ^2 + r^2) vertices when parameterized by r + γ.The construction combines matching-based reduction, iterative expansion marking, pseudo-isolated-vertex compression, and an expansion-based bound on the active remainder.Source: §4.1 · pp. 10, 11, 13

4.2 ILP-Based FPT Algorithms

• ILP formulations underpin FPT algorithms parameterized by vertex deletion distance to a clique and by maximum leaf number.The approach relies on solving ILPs with p variables in time p^O(p) · |I|.Source: §4.2 · p. 13
• ECGP and BECGP are FPT parameterized by vertex deletion distance to a clique, using guessed modulator partitions, neighborhood types, and bounded-variable linear integer programs.For BECGP, equal part sizes determine the clique-vertex assignments, while both formulations have a number of variables depending only on the deletion distance.Source: §4.2 · pp. 13, 15
• For a graph G with maximum leaf number mln, Proposition 29 ([11, 37, 23]) states that G is a subdivision of a graph H with at most 4mln −6 vertices, and any ECGP solution can be replaced by a nice solution.Source: §4.2 · p. 16
• The maximum-leaf-number algorithms run in mln^O(mln^6) · n time, and the balanced variant is obtained by adding size constraints without new variables.Well-behaved parts occupy single branches and contain γ edges with γ + 1 vertices; special parts are handled through guessed branch assignments and ILP constraints.Source: §4.2 · pp. 16–18

4.3 FPT via N-Fold ILP

• Both ECGP and BECGP are FPT parameterized by vertex integrity using brute force on the modulator followed by N-fold integer programming.The modulator is partitioned into global parts, and components outside it have bounded size and are grouped by their isomorphism types relative to the modulator.Source: §4.3 · pp. 18–19
• For algorithms parameterized by vertex integrity, using at most vivi ILP instances gives total running time 22O(vi2)r log(r) + n, completing the FPT algorithms.Source: §4.3 · pp. 19, 21

Constraints

• For cluster vertex deletion plus γ, a single N-fold ILP has runtime 2^{2^{O(cvd·γ)}} · n · log(n), unchanged for BECGP after balancing constraints are added.The construction represents clique intersections as chunks of at most γ + 1 vertices and distributes them among parts by chunk type.Source: Constraints · p. 23

4.3 FPT via N-Fold ILP

• Both ECGP and BECGP are FPT parameterized by cluster vertex deletion number plus γ.The algorithm uses bounded-size chunk types and N-fold ILP formulations, with balancing enforced by additional per-part vertex constraints.Source: Constraints · p. 23

4.4 FPT via Vertex Integrity

• ECGP is fixed-parameter tractable on disjoint unions of paths when parameterized by γ.The reduction deletes γ + 1 vertices from any sufficiently long path component and decreases r by one, preserving correctness because those vertices induce exactly γ edges.Source: §4.4 · p. 24
• ECGP is FPT when parameterized by vdp + γ.Here, vdp is the size of a vertex set whose deletion leaves a disjoint union of paths.Source: §4.4 · p. 36
• The algorithm branches over partitions of the deletion set X, with at most k special parts, and certifies each special part using at most 2γ vertices outside X.These certificate vertices preserve at least γ induced edges, while other vertices in the special part are irrelevant to feasibility.Source: §4.4 · p. 25
• After selecting certificates, only at most 2kγ path components are affected, producing at most 4kγ residual path segments.The remaining path components are handled through a fixed baseline decomposition into feasible blocks and residual paths.Source: §4.4 · p. 26
• Affected-path configurations are summarized by bounded signatures recording certificate assignments, edge contributions, and corrections to baseline blocks and residual paths.Lemma 44 bounds the block correction by −s ≤ δ(P, φ) ≤ 0 and each residual correction between −1 and s + 1 for s selected certificates.Source: §4.4 · pp. 26–28
• A left-to-right finite-state dynamic program computes realizable signatures for each path and combines them across all path components.Global corrections remain bounded by a function of k + γ, despite baseline quantities depending on the input size.Source: §4.4 · p. 29
• The path dynamic program computes exactly the realizable signatures of affected configurations while tracking truncated edge counts, certificate sizes, assignments, and ordinary-segment corrections.Each path position has a number of states bounded by a function of k and γ, yielding time f1(k, γ) · |V(P)| per path.Source: §4.4 · pp. 31–32
• A second dynamic program combines path signatures, accumulating corrections for completed feasible blocks and residual paths while enforcing bounds depending only on k and γ.The resulting global state space is bounded by a function of k + γ, so the combination runs in FPT time.Source: §4.4 · pp. 32, 34
• Each accepted final state yields feasible special parts, completed ordinary blocks, and a residual graph Hζ whose components have at most γ vertices and vertex integrity at most γ.If completed blocks do not supply all required non-special parts, the algorithm invokes the vertex-integrity algorithm on (Hζ, q − A, γ).Source: §4.4 · pp. 33–34
• The acceptance procedure is sound and complete: it accepts exactly when the selected special parts, completed blocks, and any residual partition form r feasible parts.Soundness reconstructs a valid partition from accepted signatures, while completeness follows by selecting bounded certificate sets from every part intersecting the modulator.Source: §4.4 · p. 35
• ECGP is FPT parameterized by vertex deletion distance to paths plus γ and by vertex deletion distance to stars plus γ.For stars, reduction bounds each star component by 1 + 2k(kγ + γ) vertices, yielding bounded vertex integrity.Source: §4.4 · pp. 36–37
• The star-based algorithm safely reduces each leaf-neighborhood class to at most (k + 1)γ vertices while preserving whether the ECGP instance is feasible.At most k + 1 parts can contain such leaves, and at most γ leaves per part are needed to contribute the required edge threshold.Source: §4.4 · pp. 36–37

4.5 Algorithms via Dynamic Programming

• Given a tree decomposition of width k, ECGP can be solved in time rO(k)(γ + 1)O(r) · n using dynamic programming over labeled parts and truncated internal-edge counts.The dynamic program handles leaf, introduce, forget, and join nodes, accepting exactly when every part reaches γ induced edges.Source: §4.5 · pp. 37–38
• The treewidth dynamic program extends to BECGP and signed variants, placing ECGP, BECGP, and their signed variants in XP parameterized by tw + r.BECGP tracks per-part vertex counts, while signed variants track edge-count values in the states.Source: §4.5 · pp. 38–39

General structural hardness

• A general reduction from Tight Unary Bin Packing makes ECGP W[1]-hard for r + vdd_H, even when vdd_H = 0, for graph classes closed under disjoint union with connected gadgets realizing every positive edge count.The reduction represents each item by a connected gadget and uses tightness to prevent gadgets from being split across parts.Source: §5 · p. 40
• Consequently, ECGP is W[1]-hard for r + fes + vds + mw and for r + fes + vdp + Δ, even with fes = 0 and respectively (vds, mw) = (0, 2) or (vdp, Δ) = (0, 2).The two cases arise by applying the general framework to disjoint unions of stars and paths.Source: §5 · pp. 40–41

Cluster vertex deletion

• ECGP is also W[1]-hard parameterized by r + cvd, using clique gadgets with correction edges and bin vertices to encode item sizes while forcing whole cliques into parts.The construction has cvd(G) = r, so the reduction preserves the combined parameter up to a factor of two.Source: §5 · pp. 41–42

Balanced variant

• Adding (r − 1)n isolated vertices transfers ECGP hardness to BECGP whenever the structural parameter does not increase, yielding the same W[1]-hardness results for r + cvd, star/path deletion, and associated parameters.The added vertices force every balanced part to have size n without changing induced-edge counts or the relevant parameters.Source: §5 · p. 43

Clique-width

• Both ECGP and BECGP are W[1]-hard parameterized by clique-width even when γ = 3, via a reduction from K3-Clique Partition.With |V| = 3r, every feasible part has exactly three vertices and therefore must be a triangle.Source: §5 · p. 43

Hardness on signed graphs

• SBECGP is NP-hard on a disjoint union of two cliques even when r = 3 and γ = 0.Source: §6 · p. 45
• SBECGP is W[1]-hard parameterized by tw + r + γ, even when γ = 0.The reduction uses a disjoint union of item cycles and copies of K_{r+1}; its treewidth is r and it preserves r.Source: §6 · p. 47
• SBECGP is W[1]-hard parameterized by td + r, even when γ = 0.Replacing each item cycle by a connected graph of equal vertex and edge counts gives treedepth at most r + 1.Source: §6 · pp. 45, 47

• ECGP, BECGP, and their signed variants provide a local-threshold framework for coalition formation, requiring every part to meet a prescribed utility threshold.Unlike classical global-objective clustering and coalition-formation models, utility is measured by interactions induced within each individual part.Source: §7 · p. 47
• Both ECGP and BECGP remain NP-hard in restricted settings, but admit polynomial kernels parameterized by r+u and FPT algorithms under several structural parameterizations.The positive results use the Expansion Lemma for kernelization and include vertex deletion distance to a clique, vertex integrity, and additional ECGP parameterizations.Source: §7 · p. 47
• The problems are W[1]-hard for several structural parameterizations, while signed variants remain hard on disjoint unions of two cliques and with fixed natural parameters.The balanced signed variant is W[1]-hard parameterized by treedepth plus r + u, even when the utility threshold is zero.Source: §7 · pp. 47–48
• Open questions concern neighborhood diversity and whether ECGP and BECGP are FPT parameterized by tw + u, with the latter unresolved even for forests.Neighborhood-diversity approaches face quadratic terms in selected vertices from different types; the treewidth question remains open when tw(G) = 1.Source: §7 · p. 48