[Model] HighlyConnectedDeletion

[zhangjieqingithub]

Motivation

Highly Connected Deletion is a graph-clustering optimization problem from the biological-network literature. It asks for deleting as few edges as possible so that the remaining graph decomposes into dense clusters.

This is not the same as:

• ClusterDeletion, which requires every cluster to be a clique
• generic cut / partition problems, which do not encode the "highly connected" cluster condition

A dedicated model is useful because the objective and feasibility semantics are specific, and the paper's notion explicitly allows isolated leftover vertices.

Associated rule:

• [Rule] HighlyConnectedDeletion to ILP #1023: HighlyConnectedDeletion -> ILP

Definition

Name: HighlyConnectedDeletion
Reference:

• Falk H�cffner, Christian Komusiewicz, Adrian Liebtrau, Rolf Niedermeier, "Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage," IEEE/ACM Transactions on Computational Biology and Bioinformatics 11(3):455-467, 2014. https://doi.org/10.1109/TCBB.2013.177
• Erez Hartuv, Ron Shamir, "A clustering algorithm based on graph connectivity," Information Processing Letters 76(4-6):175-181, 2000. https://doi.org/10.1016/S0020-0190(00)00142-3

Given a simple undirected graph G = (V, E), find a minimum-cardinality edge set F subseteq E such that every connected component of G - F is either:

• an isolated vertex, or
• a highly connected graph on at least 3 vertices.

A graph H is highly connected if
lambda(H) > |V(H)| / 2,
equivalently,
delta(H) > |V(H)| / 2.

Paper-specific nuance adopted here:

• isolated vertices may remain as unclustered leftovers
• isolated edges / 2-vertex components are not valid clusters

Variables

• Count: |E| binary variables, one per edge
• Per-variable domain: {0,1}
• Meaning: x_e = 1 iff edge e is deleted

A configuration is feasible iff, after deleting exactly those edges with x_e = 1, every connected component is either an isolated vertex or a highly connected graph of size at least 3.

Schema (data type)

Type name: HighlyConnectedDeletion
Variants: none initially; simple undirected graph only

Field	Type	Description
graph	SimpleGraph	The input graph G = (V, E)

Complexity

A conservative exact baseline is brute-force over all subsets of edges to delete.

This gives the worst-case complexity
O(2^num_edges * poly(num_vertices, num_edges))

so the registry complexity string should be
2^num_edges.

Literature-backed remarks:

• the problem is NP-hard
• the paper also gives parameterized algorithms and kernelization with respect to the number of deleted edges
• since this optimization model has no deletion budget in the input, the clean registry complexity is the conservative brute-force bound above

References:

• https://doi.org/10.1109/TCBB.2013.177

Extra Remark

This model is weaker than clique-based clustering:

• every clique of size at least 3 is highly connected
• not every highly connected graph is a clique

So HighlyConnectedDeletion should not be folded into a clique-deletion model.

Reduction Rule Crossref

• [Rule] HighlyConnectedDeletion to ILP #1023

How to solve

• It can be solved by brute force.
• It can be solved by reducing to ILP via [Rule] HighlyConnectedDeletion to ILP #1023 ([Rule] HighlyConnectedDeletion to ILP).
• Other, refer to ...

Example Instance

Let

• V = {0,1,2,3}
• E = {{0,1}, {0,2}, {1,2}, {2,3}}

This is a triangle on {0,1,2} with one leaf vertex 3 attached to 2.

Expected Outcome

An optimal solution is to delete the single edge {2,3}.

Then the remaining graph has:

• one component G[{0,1,2}] = K3, which is highly connected
• one isolated vertex {3}, which is allowed as an unclustered leftover

Thus the optimal value is 1, with deletion configuration
x_(2,3) = 1
and all other deletion variables equal to 0.

Zero deletions are infeasible because the whole graph is connected on 4 vertices and has minimum degree 1, which is not greater than 4/2 = 2.

BibTeX

@article{HueffnerKomusiewiczLiebtrauNiedermeier2014,
  author  = {Falk H{"u}ffner and Christian Komusiewicz and Adrian Liebtrau and Rolf Niedermeier},
  title   = {Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage},
  journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
  volume  = {11},
  number  = {3},
  pages   = {455--467},
  year    = {2014},
  doi     = {10.1109/TCBB.2013.177},
  url     = {https://doi.org/10.1109/TCBB.2013.177}
}

@article{HartuvShamir2000,
  author  = {Erez Hartuv and Ron Shamir},
  title   = {A clustering algorithm based on graph connectivity},
  journal = {Information Processing Letters},
  volume  = {76},
  number  = {4--6},
  pages   = {175--181},
  year    = {2000},
  doi     = {10.1016/S0020-0190(00)00142-3},
  url     = {https://doi.org/10.1016/S0020-0190(00)00142-3}
}

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	Pass	Novel problem; not in pred list; companion rule [Rule] HighlyConnectedDeletion to ILP (#1023) linked
Non-trivial	Pass	Distinct feasibility (highly-connected components OR isolated vertices) — not isomorphic to ClusterDeletion (clique components) or any existing partitioning/cut problem in the catalog
Correctness	Pass	Both references verified; definition matches Hartuv–Shamir / Hüffner et al. literature; complexity bound is conservative and correct
Well-written	Pass with minor warning	All template sections present and consistent; example correctness verified; example feasible set is sparse (see Warning)

Overall: 4 passed, 1 warning

---

Usefulness

• pred show HighlyConnectedDeletion returns Unknown problem — problem is genuinely new.
• Grep over pred list shows no overlapping model: existing clustering/partition models are Clustering, GraphPartitioning, PartitionIntoCliques, PartitionIntoTriangles, AcyclicPartition, etc. None of these encode the "highly connected component" condition λ(H) > |V(H)|/2.
• Companion rule [Rule] HighlyConnectedDeletion → ILP is properly linked at [Rule] HighlyConnectedDeletion to ILP #1023, satisfying the rule that direct-ILP-solvability claims require a companion rule issue. Brute-force solver path is also checked.
• Motivation is concrete (biological-network clustering, distinct from clique-based clustering).

Non-trivial

• Distinct feasibility from ClusterDeletion (cliques only) and GraphPartitioning (no density requirement). The "highly connected" condition λ(H) > n/2 with the isolated-vertex carve-out is a genuinely different combinatorial structure, not a relabeling.
• Distinct objective (minimum-cardinality edge deletion under the highly-connected constraint) is not captured by any existing model.

Correctness

Reference 1 — Hüffner, Komusiewicz, Liebtrau, Niedermeier, IEEE/ACM TCBB 11(3):455–467, 2014, DOI 10.1109/TCBB.2013.177

• Verified to exist (PubMed PMID 26356014; dblp record journals/tcbb/HuffnerKLN14).
• Abstract confirms: "removing as few edges as possible from a graph such that the resulting graph consists of highly connected components"; NP-hard; FPT and kernelization results. Matches issue's claims.
• The Springer companion paper "Finding Highly Connected Subgraphs" (Hüffner, Komusiewicz, Sorge) also corroborates the formalization used here.

Reference 2 — Hartuv, Shamir, IPL 76(4–6):175–181, 2000, DOI 10.1016/S0020-0190(00)00142-3

• Verified (Wikipedia, Semantic Scholar). HCS algorithm uses the same λ(H) > n/2 definition the issue cites.

Definition equivalence claim: The issue states λ(H) > |V(H)|/2 ⇔ δ(H) > |V(H)|/2.

• λ ≤ δ trivially gives one direction.
• The reverse (δ > n/2 ⟹ λ = δ) is Chartrand's 1966 theorem (any graph with δ ≥ ⌈n/2⌉ has λ = δ).
• So the equivalence is correct.

Minimum cluster size ≥ 3: For n = 2, λ(H) ≤ 1 ≤ n/2 = 1 so no 2-vertex graph can be highly connected. The issue's exclusion of 2-vertex components is therefore consistent with the highly-connected definition itself, and the paper's allowance of isolated-vertex leftovers is faithfully encoded.

Complexity: 2^num_edges brute-force bound is correct (each edge kept or deleted), and the issue properly flags the FPT / kernelization results as out of scope for the registry's worst-case complexity string.

Well-written

• All template sections present: Motivation, Reference, Definition, Variables, Schema, Complexity, Reduction Rule Crossref, How to solve, Example Instance, Expected Outcome, BibTeX.
• Schema field graph: SimpleGraph and binary per-edge variable encoding are consistent with the definition (variable count = |E|, domain {0,1}).
• Notation consistent: G = (V, E), λ, δ defined inline; the size getter implied by the complexity string (num_edges) is conventional for SimpleGraph-input models.
• Naming convention OK: optimization problem without a Maximum/Minimum prefix because the model name encodes the action ("Deletion") rather than the optimization direction; this matches existing precedents like ClusterDeletion-style naming in the literature. Worth noting that some catalog conventions favor Minimum… prefixes, but the chosen name is well-established in the literature and not ambiguous.
• Expected outcome is concrete and justified (deletion of {2,3}, value 1, with explicit infeasibility argument for 0 deletions).

Warning — round-trip discriminatory power of the example:
The 4-vertex example admits essentially only two feasible solutions: the optimum (delete {2,3}, value 1) and the trivial "delete everything" solution (value 4). Most intermediate edge-deletion patterns are infeasible because they leave 2-vertex components or 3-vertex non-triangles. A buggy implementation that, say, mis-checks the λ > n/2 condition could still happen to land on the optimum. Consider augmenting the example (e.g., add a second triangle attached by a bridge edge) so the closed-loop test has at least 2 suboptimal feasible solutions in addition to the optimum.

Recommendations

• Consider citing the follow-up FPT / kernelization paper "Finding Highly Connected Subgraphs" (Hüffner, Komusiewicz, Sorge — SOFSEM 2015, LNCS 8939) as additional context for the parameterized complexity remark.
• For the paper write-up, a 5–6 vertex example with two valid highly-connected clusters plus an isolated leftover would be more illustrative and would also give the closed-loop test more discriminating power.

[isPANN]

/review-structural — commit 4794f41 (post-impl, code-quality + bug sweep)

Verdict: pass — Clean single-responsibility model commit; mathematical definition, schema, canonical example, and paper entry all match issue #1022.

Issue compliance

• Mathematical definition matches issue: yes — λ(H) > |V(H)|/2 strict, components of size 2 forbidden, isolated vertices allowed as leftovers. Doc comments quote the spec verbatim.
• Schema fields match: yes — single graph: SimpleGraph field; description reads "The underlying graph G=(V,E)" which matches the issue's table. ProblemSizeFieldEntry exposes num_vertices, num_edges per project convention.
• Canonical example: ok — triangle on {0,1,2} with leaf vertex 3 attached to 2 (edges (0,1),(0,2),(1,2),(2,3)), optimum config [0,0,0,1], value 1. Exactly matches the issue's "Example Instance" / "Expected Outcome", and the paper figure mirrors the same data.

Structural checklist

• Model file at src/models/graph/highly_connected_deletion.rs ✓
• inventory::submit! for ProblemSchemaEntry + ProblemSizeFieldEntry ✓
• #[derive(...Serialize, Deserialize)] with bound(deserialize=...) for G ✓
• Problem trait impl with type Value = Min<i64> and crate::variant_params![G] ✓
• #[cfg(test)] #[path = "../../unit_tests/..."] link present ✓
• Test file exists with 14 test functions (well over the 3-min floor): creation, name, evaluate-optimum, evaluate-zero-deletions-infeasible, evaluate-delete-all, evaluate-2-vertex-infeasible, evaluate-path-infeasible, wrong-config-length, brute-force canonical, brute-force "double triangle" discriminator (two K₃'s joined by a bridge — optimum = 1, addresses the check-issue example-strength warning), serialization, variant, plus 5 edge_connectivity helper tests (single vertex / single edge / P₃ / K₃ / K₄) ✓
• Registered in src/models/graph/mod.rs (mod decl, pub use, example-spec extend) ✓
• declare_variants! with default HighlyConnectedDeletion<SimpleGraph> => "2^num_edges" — variable name matches the num_edges() getter ✓
• Canonical example registered via canonical_model_example_specs() and called from graph/mod.rs ✓
• Paper: display-name entry at line 211; problem-def block at line 1107 with hand-authored layout (no load-model-example because the spec is shipped via canonical_model_example_specs rather than the JSON bundle, comment explains this); BibTeX entries HueffnerKomusiewiczLiebtrauNiedermeier2014 and HartuvShamir2000 added with proper H{"u}ffner umlaut encoding ✓
• No blacklisted auto-generated files in the diff ✓
• No CLI hookup changes needed: the schema-driven pred create flow handles graph: G via the existing --graph flag; alias resolution is registry-driven and no manual entry was needed (issue did not request one) ✓

Semantic review

• evaluate() performs the feasibility check first and returns Min(None) for any infeasible config, matching Min<i64> optimization semantics; the test evaluate_wrong_config_length confirms length-mismatched configs are rejected rather than panicking
• dims() returns vec![2; self.graph.num_edges()] — matches "|E| binary variables, one per edge" from the issue
• Feasibility predicate (is_feasible_deletion): rebuilds adjacency from surviving edges, BFS for components, allows size-1 components, rejects size-2 components outright, and for size ≥ 3 checks 2 * λ > size (integer-arithmetic equivalent of the strict λ > n/2 condition — avoids float comparison correctly)
• edge_connectivity uses Edmonds–Karp with unit-capacity arc pairs (forward/reverse via the standard a ^ 1 trick) and computes min over t of λ(s, t) for a fixed source s = 0. This is the standard correct reduction for undirected edge connectivity, since any minimum cut must separate s from some t. Augmenting paths use BFS for shortest-path layering, capacities are reset between (s, t) iterations, and the usize::MAX → 0 guard handles the trivial size-1 case
• Helper getters num_vertices() / num_edges() are present and match the names used in complexity = "2^num_edges", so the proc-macro variable-name validation passes
• Weight handling: model is unweighted, no weight machinery needed — correctly omitted

Findings

• Blockers (correctness): none
• Nits (quality/HCI):
  • type Value = Min<i64> is the minority convention for graph minimum-cardinality counting models in this repo (8 of 9 sampled peers — e.g. MinimumCoveringByCliques, OptimalLinearArrangement, MinimumGraphBandwidth, MinimumMaximalMatching, MinimumMetricDimension — use Min<usize>). Min<usize> would express "non-negative edge count" more naturally; Min<i64> is not wrong but slightly off-style. Pure style nit, no behavior impact.
  • The BFS loop inside edge_connectivity breaks out of the inner while let Some(u) as soon as u == t. Correct (shortest augmenting path is found, remaining queue items are irrelevant) but mildly opaque to a first-time reader — a one-line comment "early exit: shortest s→t path is fixed once t is dequeued" would help. Optional.

Net: cleanly scoped commit, mathematics matches the issue, tests are unusually thorough (14 functions including discriminatory "double triangle" instance and a 5-case edge_connectivity helper sweep), and the paper entry compiles via the hand-authored fixture path with a clearly documented reason. Safe to merge.