PaperlayerView exact revision on arXiv

Source-linked AI summary

Objective Transfer in Single-Node Network Criticality: Optimal Constants and Exact Separation Thresholds

Onur Ugurlu

arXiv:2609.34394v1cs.DM

TL;DR

The paper asks how much damage an objective-optimal attack retains when evaluated under another criticality objective. It formalizes transfer ratios for single-vertex attacks on connected graphs and proves sharp PC–LCC guarantees alongside vanishing NC transfers and exact disagreement thresholds.

  • Problem

    Prior work treats critical-node damage objectives mostly separately or compares their solutions empirically, leaving directed worst-case bounds on cross-objective damage transfer unestablished.

    Source: §1 · pp. 1–2

  • Method

    The paper defines transfer ratios between objective-optimal vertices for PC, LCC, and NC on connected graphs, with attacked vertices counted as lost and ties resolved optimistically.

    Source: §1 · p. 2

  • Results

    The sharp PC → LCC and LCC → PC guarantees are 2 − √2 and 2/3, while all NC-involving directions vanish; triple champion separation first occurs at order 11.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Reusing one objective’s optimal vertex has guaranteed cross-objective value for PC and LCC, but not for transfers involving NC.

    Source: §1 · p. 2

    For fixed budgets above one, the results over all connected graphs do not determine whether trees or bounded-degree graphs admit better constants; budgets growing with n are also outside the claims.

    Source: §7.4 · p. 17, §9 · p. 17

Abstract

from arXiv · show

When a vertex is selected as the most damaging single attack target under one damage objective, how much of the optimal damage under a different objective does it retain? We study this for the three objectives commonly used in critical node detection -- pairwise connectivity (PC), size of the largest surviving component (LCC) and number of components (NC) -- for single-vertex attacks on connected graphs, with the attacked vertex counted in the damage and ties resolved optimistically. For the pair PC, LCC the loss is bounded: a PC-optimal vertex retains at least a $2-\sqrt2$ fraction of the optimal LCC damage, an LCC-optimal vertex at least 2/3 of the optimal PC damage, and both constants are best possible. Neither bound depends on the choice among tied optimal vertices or on whether the attacked vertex is counted, and both remain valid as lower bounds for attack sets of any fixed size. For the four directions involving NC no positive constant exists; explicit families have ratios decaying like 1/k, and no single attack set retains a positive fraction of all three optima uniformly. We also determine the smallest orders at which the sets of optimal vertices become disjoint: 7 for LCC/NC, 8 for PC/NC, 9 for PC/LCC and 11 for all three pairwise, with trees realising the triple separation for every n>=11; these values rest on an exhaustive enumeration of the 11,989,762 connected graphs with 3<=n<=10. Finally, the most critical vertex in a Birnbaum-type sense may depend on the failure probability: a six-vertex graph, of smallest possible order, changes leader once, at $p^*=3-\sqrt5$. Adding universal vertices lifts the budget-one examples to every fixed budget, so over all connected graphs the same constants are optimal at every fixed budget; behaviour within restricted classes such as trees is left open.

1 Introduction

The paper asks how much damage a vertex optimal for one criticality objective retains under another, addressing a gap in prior empirical and joint-objective comparisons. It establishes sharp transfer bounds and additional results on objective disagreement and failure-probability-dependent rankings.

1 Introduction

  • The study fixes single-vertex attacks on connected graphs, counts the attacked vertex as lost, and resolves ties optimistically; positive bounds also hold for every tied source optimum.The optimistic tie rule strengthens the negative results but does not affect the positive bounds.Source: §1 · p. 2
  • PC- and LCC-optimal vertices retain at least 2 − √2 and 2/3 of the other objective’s optimal damage, respectively; every direction involving NC has no positive uniform bound.The positive constants are best possible, and explicit families witness vanishing NC ratios.Source: §1 · p. 2
  • Optimal-vertex sets first become disjoint at orders 7 for LCC/NC, 8 for PC/NC, 9 for PC/LCC, and 11 for all three pairwise.The triple-separation threshold is realized by trees for every order n ≥11.Source: §1 · p. 2
  • A six-vertex graph has a Birnbaum-type most-critical vertex that changes once with failure probability, at p* = 3 − √5, and no smaller graph does.The threshold and minimality are exact.Source: §1 · p. 2

1.1 Related work

  • Earlier work studies the three damage objectives and their optimizers, but the paper targets directed worst-case transfer rather than proposing an optimization algorithm [3, 13, 23].Prior comparisons include bi-objective formulations and empirical rankings on real-world networks.Source: §1.1 · p. 2, §1 · p. 2

2 Definitions and conventions

The paper formalizes exact-cardinality attacks, objective-specific champion sets, and transfer ratios, while fixing damage and tie conventions. It also defines a probability-dependent marginal criticality score.

2 Definitions and conventions

  • An attack removes an exact-cardinality set S from a finite connected graph, whose remaining components are recorded by their ordered component profile.The setup allows budgets from 1 through n − 1 and defines the empty remainder by convention when extending to arbitrary attack sets.Source: §2 · p. 3
  • Champion sets contain all maximizers of an objective, and two objectives disagree when their champion sets are disjoint.For single-vertex attacks, a champion set is identified with its vertex when it is a singleton.Source: §2 · p. 3
  • The optimistic transfer ratio is the best target-objective damage among source-objective champions divided by the target optimum; the pessimistic version uses the worst such champion.A positive constant lower bound independent of graph and order is distinguished from a vanishing ratio.Source: §2 · p. 3
  • The Birnbaum-type signed marginal effect evaluates a vertex under independently failing other vertices and selects the vertex with greatest objective-specific effect at probability p.The regime champion is determined from exact polynomials with isolated real roots; for NC the quantity may be negative.Source: §2 · p. 3
  • Damages count attacked vertices as lost, while survivor-based alternatives subtract the budget and can change transfer ratios or create zero denominators.The paper states its main conventions for this damage definition and separately proves which bounds persist under survivor-based shifts.Source: §2 · pp. 3–4

3 Transfer ratios at budget one

At budget one, the PC–LCC transfer guarantees are positive and sharp, whereas every transfer direction involving NC vanishes. The positive guarantees are robust to tie-breaking and damage conventions and extend as lower bounds to fixed-size attack sets.

3 Transfer ratios at budget one

  • 2 − √2 and 2/3 are the sharp worst-case transfer ratios for PC → LCC and LCC → PC, respectively.Explicit families approach both constants.Source: §3 · p. 4
  • All four directions involving NC have zero worst-case transfer, with explicit witness-family ratios decaying at rates Θ(1/k).Examples include rates 6k/(k^2 + 3k + 1), 2/k, and 1/k.Source: §3 · p. 4
  • The two positive guarantees are unchanged by tie-breaking or by counting only surviving vertices, and hold for every source maximizer.The pessimistic and optimistic constants coincide under either damage convention where the target damage is positive.Source: §3 · p. 4
  • The positive lower bounds extend to attack sets of every fixed size, and over all connected graphs the full transfer classification remains the same at each fixed budget.The fixed-budget sharpness and vanishing results are established by lifting budget-one witnesses with universal vertices.Source: §3 · p. 4

4 Separation thresholds

The paper establishes exact smallest orders for objective-optimal vertex sets to disagree, including a threshold of 11 for pairwise separation of all three objectives. Exhaustive enumeration supports the finite thresholds, and trees realize triple separation from order 11 onward.

4 Separation thresholds

  • The first disjoint champion sets occur at order 7 for LCC/NC, 8 for PC/NC, and 9 for PC/LCC.Theorem 7 reports examples at each threshold and exhaustive checks of smaller orders.Source: §4 · pp. 4–5
  • In the smallest example, deleting h creates four components, deleting c bisects the tree, and deleting p wins PC by trading balance for an extra component.The graph is an 11-vertex tree, W(3) up to isomorphism.Source: Figure 1 · p. 5
  • 11 is the smallest order for pairwise disjoint champion sets for all three objectives; trees with this separation exist for every n ≥11.No connected graph of order at most 10 achieves triple separation.Source: §4 · p. 5, Figure 1 · p. 5
  • The finite thresholds rely on exhaustive enumeration, while the infinite family of triple-separating trees is established separately.The paper identifies enumeration as the basis for the finite part and Theorem 18 for the infinite construction.Source: §4 · p. 5

5 Dependence on the failure probability

The paper studies whether Birnbaum-type PC-criticality rankings depend on failure probability. A six-vertex graph has one exact leadership change, while no connected graph of order at most five has one.

5 Dependence on the failure probability

  • At order six, R6 has one leadership change at p*=3−√5: v1 leads below the breakpoint, all three vertices tie at it, and v0 and v2 lead above it.No connected graph with n≤5 has a leadership change anywhere in (0, 1).Source: §5 · pp. 5–6

7 Larger budgets

For every fixed attack budget, the PC–LCC transfer guarantees persist, while directions involving NC still lack uniform positive guarantees. The section also shows that optimal attack sets need not nest across budgets and uses universal-vertex lifts to establish fixed-budget results over all connected graphs.

7.1 Optimal sets at consecutive budgets

  • For 4 ≤ n ≤ 7, the minimum budget-extension ratio is 3/4, attained at n = 7; even on P5, the budget-one champion belongs to no optimal pair.Thus optimal attack sets at consecutive budgets need not be nested.Source: §7.1 · p. 12

7.2 Lower bounds at every exact budget

  • At every exact budget, PC-optimal attack sets retain at least 2 − √2 of optimal LCC damage, and LCC-optimal sets retain at least 2/3 of optimal PC damage.Both bounds hold under either damage convention, when the target optimum is positive, and for every tied champion.Source: §7.2 · pp. 12–13

7.3 Simultaneous guarantees

  • For PC/NC, LCC/NC, and the triple, the best simultaneous guarantee has infimum zero along tree families, while PC/LCC admits a 2/3 lower bound.The 2/3 bound for a PC/LCC compromise is not claimed to be optimal.Source: §7.3 · p. 14
  • Two scenarios suffice for a 2/3 guarantee across PC, LCC, and NC: an LCC champion and an NC champion cover these objectives componentwise.The guarantee uses separate attacks, each starting from the original graph; it does not assert that two tests are necessary on every graph.Source: §7.3 · p. 15

7.4 Fixed budgets over all connected graphs

  • For each fixed budget, universal-vertex lifts make the single-vertex constants sharp over all connected graphs and preserve the vanishing results involving NC.The lifts do not settle whether trees or bounded-degree graphs have better constants at budgets b ≥ 2, or what happens when budgets grow with n.Source: §7.4 · pp. 15–17

8 Computational methods

The finite-size separation thresholds were established by exhaustive graph enumeration, with independent implementations reproducing the counts. Exact arithmetic was used to check ratios and failure-probability comparisons.

8 Computational methods

  • The separation counts were reproduced by two independently written implementations with identical results.Connected graphs and trees were generated with geng from nauty, and connected-graph counts were checked against OEIS A001349.Source: §8 · p. 17
  • Ratios were compared in exact rational arithmetic, and failure-probability comparisons used exact polynomials with isolated real roots.Computer search guided witness-family construction, whose properties were then proved analytically.Source: §8 · p. 17
  • The code, raw outputs, witness graphs in graph6 format, and a computation-to-statement map are supplied as supplementary material.Table 1 summarizes the computational outcomes.Source: §8 · p. 17

9 Open problems

The open problems concern whether fixed-budget transfer guarantees change within restricted graph classes and how results extend to growing budgets. The paper also leaves open which other component-profile functionals admit uniform transfer constants and how graph breakpoint structure depends on topology.

9 Open problems

  • For budgets b ≥ 2, it remains open whether transfer bounds improve or NC directions remain vanishing on trees or bounded-degree graphs; budgets proportional to n are also uncovered.The universal-vertex construction leaves these classes and does not address budgets growing with graph order.Source: §9 · p. 17
  • It remains open which other component-profile functionals admit uniform transfer constants and which normalisations support them.The paper asks this beyond the three objectives and the two normalisations it settles.Source: §9 · p. 17
  • The full set of graph regime breakpoints—including their number, algebraic degrees, and dependence on topology—remains unknown.The paper reports no answers beyond its stated results.Source: §9 · p. 17
Loading 2609.34394v1…