# Problem understanding “connectivity” characteristic for the $k$-connected subgraph problem

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?

• Could you please make your question more self-contained by including the offending definition and some context? – Dave Clarke May 7 '13 at 10:48

I think I figured it out.

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

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

3. $Path_{H}$ are paths inside the region

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]