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?