Source-linked AI summary
Parameterized Complexity of Edge-Constrained Graph Partitioning
Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla
TL;DR
The paper asks how edge-constrained graph partitioning and its balanced and signed variants behave computationally under natural and structural parameterizations. It develops kernelization and FPT techniques, proves broad hardness results, and identifies remaining open parameterized cases.
Problem
The paper studies whether graph vertices can be partitioned into parts satisfying local edge or signed-utility thresholds, including equal-size parts, and seeks their complexity under natural and structural parameters.
Method
The authors combine polynomial-kernel reductions with ILP-based and structural parameterized algorithms, and use parameter-preserving reductions for hardness results.
Results
Both unsigned problems have polynomial kernels for r + γ and several FPT parameterizations, but remain W[1]-hard for combinations involving r and structural parameters; signed variants are hard under strong restrictions.
Takeaways & Limitations
The complexity landscape contains both tractable structural regimes and persistent hardness, while signed interactions substantially change the complexity of the problem.
Takeaways & Limitations
The parameterized complexity remains open for neighborhood diversity and for treewidth plus γ, including forests in the latter case.
Abstract
from arXiv · showhide
We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We also consider a balanced variant (BECGP), requiring equal-sized parts, and signed variants, where the utility of a part is the difference between its numbers of positive and negative edges. We show that ECGP and BECGP remain NP-hard for fixed gamma, while BECGP is also NP-hard for fixed r. For the natural parameterization r+gamma, both problems admit polynomial kernels. We obtain FPT algorithms for ECGP and BECGP parameterized by maximum leaf number, vertex deletion distance to a clique, cluster vertex deletion number plus gamma, and vertex integrity. Furthermore, ECGP is FPT parameterized by vertex deletion distance to stars plus gamma and vertex deletion distance to paths plus gamma. On the negative side, ECGP and BECGP are W[1]-hard when parameterized by r together with several structural parameters. In particular, hardness holds for feedback edge set, vertex deletion distance to stars or paths, and modular width even when the corresponding parameter is zero. The problems are also W[1]-hard parameterized by cluster vertex deletion number plus r, and by clique-width even when gamma=3. For signed graphs, both variants are NP-hard even when r+gamma=3 and the input is a disjoint union of two cliques. Finally, the balanced signed variant is W[1]-hard parameterized by treedepth plus r, even when gamma=0.
1 Introduction
The paper formulates edge-constrained graph partitioning and systematically studies its classical and parameterized complexity, including balanced and signed variants. It establishes polynomial kernels and several FPT results, alongside broad W[1]-hardness and open cases.
- Problem setting: ECGP partitions vertices into r parts, each inducing at least γ edges; BECGP additionally requires equal-sized parts.The signed variants replace induced-edge utility with the difference between positive and negative induced edges.
- Classical complexity: Both ECGP and BECGP remain NP-hard for fixed constants r and γ.
- Parameterized tractability: Both problems admit polynomial kernels parameterized by r + γ, with ECGP using O(rγ^2) vertices and BECGP using O(rγ^2 + r^2) vertices.The ECGP kernel also has O((rγ)^2) edges.
- Parameterized tractability: ECGP and BECGP are FPT for vertex integrity and vertex deletion distance to a clique, while additional ECGP algorithms cover maximum leaf number and deletion distance to paths plus γ.The clique-based approach linearizes edge-counting constraints after guessing bounded variables; neighborhood diversity remains open.
- Hardness and open cases: ECGP and BECGP are W[1]-hard under r combined with several structural parameters, and remain W[1]-hard by clique-width even when γ = 3.The hardness parameters include deletion distance to stars or paths, feedback edge set, modular width, and cluster vertex deletion.
- Signed variants: Signed variants are NP-hard on disjoint unions of two cliques when r + γ = 3, while balanced signed ECGP is W[1]-hard for treedepth + r + γ even when γ = 0.
2 Preliminaries
The preliminaries establish graph notation, partitioning terminology, the ECGP and BECGP decision problems, and their signed counterparts. They also define the structural parameters used throughout the complexity analysis.
- Problem definitions: ECGP asks whether V can be partitioned into r parts, each inducing at least γ edges.
- Problem definitions: BECGP adds the requirement that r divides n and every part has size n/r.
- Signed variants: Signed ECGP requires each part’s positive-edge count minus negative-edge count to be at least γ.Signed BECGP adds the same equal-size condition as BECGP.
- Structural parameters: The paper also uses clique-width, maximum leaf number, treedepth, feedback vertex or edge sets, and deletion-distance parameters including vdc, cvd, vdp, and vds.
- Structural parameters: Treewidth is the minimum width of a tree decomposition, whose bags cover vertices, contain every edge’s endpoints somewhere, and satisfy the connectedness condition for each vertex.Pathwidth restricts the decomposition tree to be a path.
- Structural parameters: Cluster vertex deletion number is the minimum vertices whose removal leaves a disjoint union of cliques, while vertex integrity bounds both the deletion set and remaining component sizes.
3 Basic Complexity
The basic-complexity results separate easy boundary cases from fixed-parameter hardness. ECGP and BECGP are polynomial-time solvable for r = 1 and γ = 1, but become NP-hard under fixed nontrivial thresholds.
- Polynomial-time cases: For r = 1, both ECGP and BECGP are solvable in polynomial time by checking whether |E(G)| ≥ γ.
- NP-hardness: BECGP is NP-hard for r = 2 via a reduction from Minimum Bisection on cubic graphs.The reduction translates a balanced cut with at most k crossing edges into two equal parts each meeting the edge threshold γ.
- Polynomial-time cases: For γ = 1, both problems are solvable in polynomial time exactly when the graph contains a matching of size at least r.A matching supplies one internal edge to each part, and feasible parts yield vertex-disjoint witness edges.
- NP-hardness: Both BECGP and ECGP are NP-hard for γ = 2 via P3-Partition on bipartite graphs of maximum degree 3.In these graphs, three vertices induce at least two edges exactly when they induce a three-vertex path.
4 Algorithmic Results
The paper develops kernels and fixed-parameter algorithms for ECGP and BECGP across several structural parameters, while also identifying parameter regimes with tractability or hardness. Its positive results combine reduction rules, ILP formulations, N-fold ILP, and dynamic programming.
- Kernelization: ECGP has a polynomial kernel with O(rγ2) vertices and O((rγ)2) edges for parameter r + γ.The kernelization uses reduction rules and expansion arguments.
- Kernelization: BECGP has a polynomial kernel with O(rγ2 + r2) vertices for parameter r + γ.The reduction rules preserve equivalence and can return trivial YES- or NO-instances.
- ILP-based algorithms: ECGP and BECGP are FPT parameterized by vertex deletion distance to a clique, maximum leaf number, vertex integrity, and cluster vertex deletion number plus γ.The clique-deletion algorithms use bounded-variable ILPs, while vertex integrity uses N-fold ILP; cluster deletion combines structural reduction with ILP.
- ILP-based algorithms: The vertex-integrity algorithms solve each N-fold ILP instance in time 2^(2^O(vi^2))r^log(r), with at most vi^vi instances.The resulting total running time remains fixed-parameter tractable in vertex integrity.
- Dynamic programming and structural reductions: ECGP is FPT parameterized by vertex deletion distance to disjoint unions of paths plus γ and by vertex deletion distance to disjoint unions of stars plus γ.The path algorithm uses signatures and dynamic programming, while the star algorithm applies a reduction to bound vertex integrity.
- Dynamic programming and structural reductions: The path-based algorithm bounds global states by a function of k + γ and invokes the vertex-integrity algorithm on residual graphs with vertex integrity at most γ.Reduction Rule 4 produces completed feasible parts and a residual instance whose solution completes the partition.
5 Hardness Results
The hardness section establishes W[1]-hardness for ECGP across broad structural parameterizations, including cases where the structural parameter is zero, and transfers these results to BECGP. It also gives a general reduction framework and a separate clique-width hardness result that holds even for γ = 3.
- General hardness framework: A graph class closed under disjoint union and containing connected graphs with every positive edge count yields ECGP W[1]-hardness parameterized by r + vddH, even when vddH = 0.The reduction represents each bin-packing item by a connected graph with the corresponding number of edges and takes their disjoint union.
- Structural hardness: ECGP is W[1]-hard parameterized by r + fes + vds + mw, even when fes = 0, vds = 0, and mw = 2.
- Structural hardness: ECGP is W[1]-hard parameterized by r + fes + vdp + ∆, even when fes = 0, ∆ = 2, and vdp = 0.
- Structural hardness: ECGP is W[1]-hard parameterized by r + cvd.The construction uses r bin vertices, and deleting them leaves a disjoint union of cliques and isolated vertices, giving cvd(G) = r.
- Balanced variant: The same structural W[1]-hardness results extend from ECGP to BECGP through a parameter-preserving reduction that adds (r − 1)n isolated vertices.The resulting graph has rn vertices, so each balanced part has size n while isolated vertices preserve the edge requirements and relevant parameters.
- Clique-width hardness: Both ECGP and BECGP are W[1]-hard parameterized by clique-width even when γ = 3.With 3r vertices, every feasible part must contain exactly three vertices and therefore be a triangle, yielding a reduction from K3-clique partition.
6 Hardness on Signed Graphs
The signed variants are computationally hard even on highly restricted graphs and with fixed natural parameters. Reductions from 3-Coloring and Unary Bin Packing establish NP-hardness and W[1]-hardness for the signed problems.
- SECGP is NP-hard on a disjoint union of two cliques, even when r = 3 and γ = 0.
- The reduction from 3-Coloring creates two cliques whose feasible three-part partitions correspond exactly to proper 3-colorings.
- SBECGP is NP-hard on a disjoint union of two cliques, even when r = 3 and γ = 0, via Equitable 3-Coloring.
- SBECGP is W[1]-hard parameterized by tw + r + γ, even when γ = 0.
- The Unary Bin Packing reduction forces each green cycle into one part and distributes every red K_{r+1} with exactly two vertices in one part and one in each other part.
- Replacing each reduction cycle by a graph of treedepth at most 3 yields W[1]-hardness parameterized by td + r + γ, even when γ = 0.
7 Conclusion
The paper develops a complexity framework for local-utility graph partitioning, combining hardness results with kernels and fixed-parameter algorithms. Signed interactions remain especially difficult, while neighborhood diversity and treewidth parameterizations remain open.
- The framework requires every part to meet a prescribed local utility threshold rather than optimizing a global clustering objective.
- Both ECGP and BECGP remain NP-hard under several restricted settings, while both admit polynomial kernels parameterized by r+u.
- FPT algorithms are obtained for structural parameters including vertex deletion distance to a clique and vertex integrity, with additional ECGP results for several deletion and leaf-number parameters.
- Signed variants remain hard on disjoint unions of two cliques, and balanced signed ECGP is W[1]-hard parameterized by treedepth plus r + u even when the utility threshold is zero.
- The parameterized complexity under neighborhood diversity and tw + u remains open, including the case of forests for the latter.