I am reading this article, and I am having trouble to understand the 11th definition (page 7) about the connectivity characteristic. I do understand the raw definitions, but have no idea what this gives my intuitively.

The definition:

  • For each pair of distinct vertices v, u of H: let $Com_{H}(v, u)$ be the set of portal completions which augment H to a graph with k internally vertex-disjoint paths between v and u.
  • For each vertex v of H, let $Path_{H}(v)$ be the set of pairs (U, Q) where U is a multiset of P(H) with vertex multiplicities bounded by from above by the vertex degrees in H and Q is a partial g-matching on the complete multigraph on P(H) with g(w) equal to the difference between the degree of w in UH and the multiplicity of w in U such that there are $|U|+|Q|$ internally vertex-disjoint paths in H connecting v with each copy a vertex in U, and connecting each pair of endpoints of each edge in Q, respectively.
  • $Path_{H}$ is the set of all Q for which $(\phi, Q)$ is in $Path_{H}(v)$ for an arbitrary vertex v in P(H).
  • We will call the triple ($Com_{H}(v, u)$, $Path_{H}(v)$, $Path_{H}$) the $connectivity\ characteristic$ of H.

Context: The paper presenta a PTAS for minimum-cost k-connected subgraph problem. This is done by dissecting the graph into smaller parts, brute-forcing a solution on the small parts, and then connecting them in a way that doesn't increase is stays a $(1+\epsilon)$-approximation. This connectivity characteristic is a property of the subgraphs that is maintained by the algorithm while augmenting the big graph from the smaller parts. A foot note at page 6 states that it models "missing" connectivity, that will be added later by the augmentation of the regions.
Note that there is also (m, r)-blue which is another property that should be maintained. Could be that only both give something useful.
The definition of an (m, r)-blue graph is at page 10. Mainly says that a facet is being crossed at portals, and not too often.

Could someone give me some intuitive explanation about what this characteristic is, and why its helpful?

  • 3
    $\begingroup$ Could you please make your question more self-contained by including the offending definition and some context? $\endgroup$ May 7, 2013 at 10:48

1 Answer 1


I think I figured it out.

  1. $Com_{H}(v, u)$ are paths leaving the region and connecting through some vertices outside the region. CompH(u,v)

  2. $Path_{H}(v)$ are the paths connecting $v$ to the vertices that are not included in this region. enter image description here

  3. $Path_{H}$ are paths inside the region
    enter image description here

If this is true, then the proof of Lemma 3.2 has some typing errors (the 2 a.m. kind). And it should be:

To compute $Com_{H}(v, u)$ where u, u v are non-portal vertices in $H$, for each competition $D$ in $Com_{H}(v, u)$, we insert D and the set difference $D\backslash B$ into $Com_{H \cup B}(v, u)$ (not $H \cup C$).
[The rest is good]

I am not really sure, so please let me know what you think about this via comments \ up-votes \ telepathy.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.