3
$\begingroup$

Let $l_1,l_2,\dots,l_m$ be parallel lines in the plane, say $l_k=\mathbb R\times\{k\}$. On the $k$th line fix a set $V_k$ consisting of $n_k$ points.

Let $(V,E)$ be a directed graph whose set of vertices is $V=\bigcup_{k=1}^mV_k$ and set of edges $E\subset\bigcup_{k=1}^{m-1}V_k\times V_{k+1}$. For an edge $(u,v)\in E$ let $I(u,v)=\{tu+(1-t)v:0<t<1\}$ be the convex segment without the endpoints $u,v$.

We shall assume that for any distinct edges $(a,b),(c,d)\in E$ the open intervals $I(a,b)$ and $I(c,d)$ are disjoint.

The graph $(V,E)$ represents a computer network. Now assume that some set $I\subset V$ of vertices is infected by a virus.

Question. What is the smallest number of cuts, necessary for isolating the ``infected'' set $I$ from its complement $V\setminus I$?

By a cut we understand deleting all edges that start at some vertex or end at some vertex. More precesely, we say that a subset $E''\subset E$ is obtained by a cut from a subset $E'\subset E$ if $E''=E'\setminus C$ where $C$ is equal to $\{(x,y)\in E':x=v\}$ or $\{(x,y)\in E':y=v\}$ for some vertex $v\in V$.

Let $c(V,E;H)$ be the smallest length $l$ of a sequence $E_1,\dots,E_l$ such that $E_1=E$, each $E_{i}$ is obtained by a cut from $E_{i-1}$, and $E_l$ contains no directed edge $(x,y)$ with $x\in H$ and $y\in V\setminus H$.

Problem 1. Find (a reasonable upper bound for) $\max_{E,H}c(V,E;H)$ as a function of $n_1,\dots, n_m$ (where $n_k=|V_k|$).

Problem 2. Elaborate an efficient algorithm for cutting a set $H\subset V$ from its complement $V\setminus H$ in a given digraph $(V,E)$.

This problem (in a bit modified form) was posed on 27.11.2019 by Vladislav Shapiro (from Bedford, Massachusetts) on page 34 of Volume 3 of the Lviv Scottish Book.

Prize. 2 tickets to Boston Bruins.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ This would be easier to read with bulletpoints in the definition of $n$. As it stands, I read it the first time as “disjoint with the vertices and the unbounded connected component”. $\endgroup$
    – user44143
    Commented Jan 30, 2020 at 11:42
  • 1
    $\begingroup$ @MattF Thank you for the comment. I corrected the definition of $n$ using (i) and (ii), because bulleting yields too wide horizontal spaces between the items. $\endgroup$
    – Lviv Scottish Book
    Commented Jan 31, 2020 at 10:22
  • $\begingroup$ I still have some difficulty in understanding, what the setting if the question really is: -first of all: is it a geometric problem, where the location coordinates of the As and Hs and of the other knots play a role or is it a graphtheoretic one where the As have to be separated from the Hs by deleting a minimal set of edges that yields two connected components, such that there is no path from an A to a H? -Second: how does the direction of edges come into play? This are not all questions that remain open. I'd appreciate a precise definition of the problem. $\endgroup$
    – Manfred Weis
    Commented Feb 1, 2020 at 8:22
  • $\begingroup$ Just checked the Lviv book and the open questions reduce to "what is the definition of a level" in that problem? Otherwise the formulation of the problem is much clearer: given a directed graph with one source and (I guess) $m$ parallel lines(not drawn) on which $n_1, \cdots,\ n_m$ of the nodes must be placed, what is the maximal number of paths in a straight-line drawing, that can be intersected by a single line. The formulation via admins and hackers obscures more than it elucidates. $\endgroup$
    – Manfred Weis
    Commented Feb 1, 2020 at 8:50
  • 1
    $\begingroup$ @ManfredWeis Maybe you are right. Before writing down this problem I discussed with Vlad Shapiro what exactly he had in mind and he said me that the problem was motivated by the network security and the problem of cutting the hackers, as I wrote. Since the graph represents a genuine computer network, the problem has a geometric flavour. The question is how to reduce this real-life problem to a graph-theoretic one. $\endgroup$
    – Lviv Scottish Book
    Commented Feb 1, 2020 at 14:41

0

Reset to default

You must log in to answer this question.