# Attacking a network at minimum cost

A target system is modelled as a giant, undirected, simple graph $$G$$ (simple meaning no hyperedge) that can be scrutinized in adequate detail to budget and plan the attack: its topology changes slowly w/r to the time it takes to complete the attack. Although the graph has size $$|G| \gg 1$$, it is sparse: all its nodes have degree $$O(1)$$.

An attack against the graph consists in carefully choosing a subset of its nodes to disable them; that is, to cut all their incident edges. The attack is successful if the remaining subgraph has all its connected components of size $$o(|G|)$$. The cost of the attack is the total number of disabled nodes. I seek to establish that the graph will sustain any attack as long as the attackers limit their costs to $$o(|G|)$$.

Since it would be pointless to disable a node of degree $$1$$ or $$2$$, assume WLOG that suitable preprocessing has reduced the graph $$G$$ to its $$3$$-kernel: the largest minor containing neither loops, nor redundant (that is, multiple) edges, nor any subgraph that is a rooted tree or a chain. In particular $$G$$ has only nodes of degree $$\ge 3$$. To make the problem interesting, assume planarity analysis will not help any further.

Now, my question: is it true that, against a given connected kernel "in general position", successful attacks cost at least $$1/4 - o(1)$$ of its nodes, a tight estimate when the graph is $$3$$-regular? Else, is there a non-trivial lower bound on the cost?

By "in general position", I mean the attacker can only collect $$O(1)$$ statistics about the graph, such as # of nodes of degree $$j$$ for each $$j$$ (of which only $$O(1)$$ are non-zero), or # of edges connecting a node of degree $$j$$ to a node of degree $$j^\prime$$; then, they must postulate their assigned target is just any random instance from amongst a parametric family of graphs, one that happens to match the statistics at hand.

• A non-trivial lower bound probably follows from looking at the vertex expansion of a random 3-regular graph. This lower bound would also hold even if the attacker knows the entire graph. – smapers Apr 16 '20 at 11:21
• @smapers How probably would a lower bound obtained that way turn out $\ge (1/4 - o(1))|G|$ ? – François Jurain Apr 16 '20 at 14:55
• Good question - where did you get this number? Interestingly, exercise 1 here suggests that $(1/4+o(1))|G|$ indeed would be the best bound achievable for 3-regular graphs using an expansion argument. – smapers Apr 16 '20 at 15:18
• @smapers Pick a node at random from giant, random, 3-regular graph $G$. A. c., which I suspect means with probability $1 - O(1/|G|)$ in the present case, neither the chosen node nor its 3 neighbors are on a "small cycle", one of length $O(1)$; so, disable the chosen node and recompute the kernel, it is now smaller by 4 nodes and still 3-regular. – François Jurain Apr 16 '20 at 15:50

You can find a lower bound by considering $$d$$-regular Ramanujan graphs, which have a spectral expansion $$\lambda \leq 2\sqrt{d-1}$$, and therefore an edge expansion $$h(G) \geq 1/2(d-2\sqrt{d-1})$$ (see e.g. here).
Now if the graph is disconnected into components of size $$o(|V|)$$, then there must be a set $$S$$ of size $$|V|/2 - o(|V|)$$ that was disconnected from its complement. If $$G$$ has edge expansion $$h$$ then at least $$h(|V|/2-o(|V|))$$ edges must have been removed, and hence at least $$\frac{h}{d}(|V|/2-o(|V|))$$ nodes. If $$G$$ is a Ramanujan graph, then this gives a lower bound of $$\left(\frac{1}{2}-\frac{\sqrt{d-1}}{d}\right)\left(\frac{|V|}{2}-o(|V|)\right) = \left(\frac{1}{4}-O\left(\frac{1}{\sqrt{d}}\right)\right)|V|.$$
• Looks promising, if this is a guaranteed lower bound of $(1/4 - \sqrt 2 / 6)|G|$ for any 3-kernel. Regarding your set $S$ and its complement, is there a way to estimate the sizes of their kernels? I'd love to submit them to the same treatment as you did for $G$. – François Jurain Apr 16 '20 at 17:33
• You can get a bit better: below Theorem 5 here it is mentioned that whp a random 3-regular graph has edge expansion at least $0.18$, which gives you a better lower bound of $\approx 0.03|G|$. Also, it is mentioned that any 3-regular graph has edge expansion at most $h \leq 1$, so that this method cannot prove you anything better than $|G|/6$. – smapers Apr 17 '20 at 6:59
• The promising look comes from the fact that any acceptable separator (any set of nodes that, when disabled, let only connected components of size $o(|G|)$ survive) must leave a kernel of size $o(|G|)$ in the surviving subgraph. It is a consequence of the fact that WLOG the surviving kernel, if any, is connected; if it were giant, then by your result, no addition of size $o(|G|)$ to the separator could break it down. Conversely, a remaining subgraph w/o kernel is planar, and can be broken down into small components at a cost o(its size). – François Jurain Apr 17 '20 at 17:01