5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – smapers Apr 16 '20 at 11:21
  • $\begingroup$ @smapers How probably would a lower bound obtained that way turn out $\ge (1/4 - o(1))|G|$ ? $\endgroup$ – François Jurain Apr 16 '20 at 14:55
  • $\begingroup$ 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. $\endgroup$ – smapers Apr 16 '20 at 15:18
  • $\begingroup$ @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. $\endgroup$ – François Jurain Apr 16 '20 at 15:50
1
$\begingroup$

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|.$$

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – François Jurain Apr 16 '20 at 17:33
  • $\begingroup$ 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$. $\endgroup$ – smapers Apr 17 '20 at 6:59
  • $\begingroup$ 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). $\endgroup$ – François Jurain Apr 17 '20 at 17:01
  • $\begingroup$ Hence my question above, about the size of the surviving kernels w/r to the size of S. Not downplaying the significance of your answer, by the way: in contrast to everything I have attempted so far, your bound is valid even if the attacker is allowed to exploit every peculiarity of the graph they can think of. $\endgroup$ – François Jurain Apr 17 '20 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.