Return to Question

A target system is modelled as a giant, undirected, simple graph $G$ (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 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 target system is modelled as a giant, undirected, simple graph $G$ (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 attacker only accepts a cost $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 (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 target system is modelled as a giant, undirected, simple graph $G$ (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 target system is modelled as a giant, undirected, simple graph G (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| >> 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 attacker only accepts a cost 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 (multiple) edges, nor any subgraph that is a rooted tree or a chain. In particular G has only nodes of degree >= 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'; 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 target system is modelled as a giant, undirected, simple graph $G$ (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 attacker only accepts a cost $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 (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.