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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 16 '12 at 22:55
  • $\begingroup$ I have edited the question to reflect your concerns. $\endgroup$ – shortestPath Sep 17 '12 at 16:56
  • $\begingroup$ The constraint must be satisfied for all $k$ $\endgroup$ – shortestPath Sep 17 '12 at 16:58
  • 2
    $\begingroup$ So every "cut" defined by a neighborhood has weight at most $c$ ? btw your notation $e \in N$ is non-standard for cut edges. $\endgroup$ – Suresh Venkat Sep 17 '12 at 17:27
  • 1
    $\begingroup$ I have seen $E(N,\bar{N})$ for the set of cut edges. $\endgroup$ – Tsuyoshi Ito Sep 18 '12 at 0:06

Your Answer

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

Browse other questions tagged or ask your own question.