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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Apr 16, 2020 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
    Commented Apr 16, 2020 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
    Commented Apr 16, 2020 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
    Commented Apr 16, 2020 at 15:50

1 Answer 1

Reset to default
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|.$$

Improve this answer
$\endgroup$
4
  • $\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
    Commented Apr 16, 2020 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
    Commented Apr 17, 2020 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
    Commented Apr 17, 2020 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
    Commented Apr 17, 2020 at 17:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .