<p>Assume we are given an arbitrary undirected graph $G = (V, E)$ where $|V| = n$. We are also given real numbers $x_e \in [0, 1]$ for each $e \in E$. These numbers satisfy the following constraint:</p>

<p>\begin{equation}
\sum_{e \in E(N, \bar N)} x_e \leq c
\end{equation}</p>

<p>for each neighborhood $N$, and for some fixed constant $c$ ($c$ may be given as part of the input. The crucial point is that it independent of $n$). A "neighborhood" is a $k$-hop neighborhood of any vertex, for any $k$. A $k$-hop neighborhood of a vertex $v$ is the set of all vertices that can be reached from $v$ using $k$ or less edges. 
$E(A, B)$ denotes the edges between sets $A$ and $B$, $E(N, \bar N)$ is thus the set of edges crossing the cut defined by $N$.</p>

<p>I am interested in (randomized?) rounding $x_e$ that will give me a binary solution that is of approximately the same size and satisfies the constraints approximately.</p>

<p>In other words, how can I round $x_e$ to binary $x'_e$ such that $\sum_{e \in E} x'_e = \Omega(\sum_{e\in E} x_e)$ and </p>

<p>\begin{equation}
\sum_{e \in E(N, \bar N)} x'_e \leq O(c)
\end{equation}
for each neighborhood $N$.</p>

<p>Randomized rounding seems to give only $\sum_{e \in E(N, \bar N)} x'_e \leq O(\log n)$ since we need to union bound over polynomially many neighborhoods.</p>

CC BY-SA 3.0
2012-09-16T22:55:48.713Z
I do not know how you define “k-hop neighborhood” of a vertex.  In addition, from the question, I cannot tell whether k is a constant, k is part of input, or the constraint must be satisfied for all k.  Please consider to edit the question to clarify these points.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-17T16:56:34.753Z
I have edited the question to reflect your concerns.
shortestPath
CC BY-SA 3.0
2012-09-17T16:58:08.893Z
The constraint must be satisfied for all $k$
shortestPath
CC BY-SA 3.0
2012-09-17T17:27:10.823Z
So every "cut" defined by a neighborhood has weight at most $c$ ? btw your notation $e \in N$ is non-standard for cut edges.
Suresh Venkat
CC BY-SA 3.0
2012-09-17T20:11:04.957Z
Yes. Any advise on the right notation?
shortestPath
CC BY-SA 3.0
2012-09-18T00:06:53.133Z
I have seen $E(N,\bar{N})$ for the set of cut edges.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-18T13:54:50.000Z
right now you define $N$ as a set of vertices but then you write $e \in N$. despite being non-standard, I just don't know what this means: should both endpoints of $e$ be in $N$ or at least one of them?
Sasho Nikolov
CC BY-SA 3.0
2012-09-18T16:12:57.483Z
I've updated the notation to use $E(N, \bar N)$.
shortestPath
<ds.algorithms><graph-algorithms><randomized-algorithms>
Randomized rounding on a graph
shortestPath
# Randomized rounding on a graph

(Asked by: username_0 on 2012-09-16)

Assume we are given an arbitrary undirected graph $G = (V, E)$ where $|V| = n$. We are also given real numbers $x\_e \in [0, 1]$ for each $e \in E$. These numbers satisfy the following constraint:

\begin{equation}
\sum\_{e \in E(N, \bar N)} x\_e \leq c
\end{equation}

for each neighborhood $N$, and for some fixed constant $c$ ($c$ may be given as part of the input. The crucial point is that it independent of $n$). A "neighborhood" is a $k$-hop neighborhood of any vertex, for any $k$. A $k$-hop neighborhood of a vertex $v$ is the set of all vertices that can be reached from $v$ using $k$ or less edges.
$E(A, B)$ denotes the edges between sets $A$ and $B$, $E(N, \bar N)$ is thus the set of edges crossing the cut defined by $N$.

I am interested in (randomized?) rounding $x\_e$ that will give me a binary solution that is of approximately the same size and satisfies the constraints approximately.

In other words, how can I round $x\_e$ to binary $x'\_e$ such that $\sum\_{e \in E} x'\_e = \Omega(\sum\_{e\in E} x\_e)$ and

\begin{equation}
\sum\_{e \in E(N, \bar N)} x'\_e \leq O(c)
\end{equation}
for each neighborhood $N$.

Randomized rounding seems to give only $\sum\_{e \in E(N, \bar N)} x'\_e \leq O(\log n)$ since we need to union bound over polynomially many neighborhoods.

**Tags:** ds.algorithms, graph-algorithms, randomized-algorithms

> **Comments:**
> **username_1**: I do not know how you define “k-hop neighborhood” of a vertex.  In addition, from the question, I cannot tell whether k is a constant, k is part of input, or the constraint must be satisfied for all k.  Please consider to edit the question to clarify these points.  
> **username_0**: I have edited the question to reflect your concerns.  
> **username_0**: The constraint must be satisfied for all $k$  
> **username_2**: So every "cut" defined by a neighborhood has weight at most $c$ ? btw your notation $e \in N$ is non-standard for cut edges.  
> **username_0**: Yes. Any advise on the right notation?  
> **username_1**: I have seen $E(N,\bar{N})$ for the set of cut edges.  
> **username_3**: right now you define $N$ as a set of vertices but then you write $e \in N$. despite being non-standard, I just don't know what this means: should both endpoints of $e$ be in $N$ or at least one of them?  
> **username_0**: I've updated the notation to use $E(N, \bar N)$.  

---

## 0 answers

