<p>I think I figured it out.</p>

<ol>
<li><p>$Com_{H}(v, u)$ are paths leaving the region and connecting through some vertices outside the region.
<img src="https://i.sstatic.net/ls7Zv.png" alt="CompH(u,v)"></p></li>
<li><p>$Path_{H}(v)$ are the paths connecting $v$ to the vertices that are not included in this region.
<img src="https://i.sstatic.net/C5FRR.png" alt="enter image description here"></p></li>
<li><p>$Path_{H}$ are paths inside the region<br>
<img src="https://i.sstatic.net/V77Hp.png" alt="enter image description here"></p></li>
</ol>

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

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

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

CC BY-SA 3.0
2013-05-07T21:45:18.340Z
2013-05-07T21:45:18.340Z
Ramzi Kahil
<p>I am reading <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.2589&amp;rep=rep1&amp;type=pdf" rel="nofollow">this</a> article, and I am having trouble to understand the 11th definition (page 7) about the <code>connectivity characteristic</code>. I do understand the raw definitions, but have no idea what this gives my intuitively.</p>

<p>The definition:</p>

<blockquote>
  <ul>
  <li>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.  </li>
  <li>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.  </li>
  <li>$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).  </li>
  <li>We will call the triple ($Com_{H}(v, u)$, $Path_{H}(v)$, $Path_{H}$) the $connectivity\ characteristic$ of H.</li>
  </ul>
</blockquote>

<p>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 <code>connectivity characteristic</code> 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.<br>
Note that there is also <code>(m, r)-blue</code> which is another property that should be maintained. Could be that only both give something useful.<br>
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.</p>

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

CC BY-SA 3.0
2013-05-07T10:48:45.507Z
Could you please make your question more self-contained by including the offending definition and some context?
Dave Clarke
<graph-theory><cg.comp-geom><dynamic-programming>
Problem understanding "connectivity" characteristic for the $k$-connected subgraph problem
Ramzi Kahil
# Problem understanding "connectivity" characteristic for the $k$-connected subgraph problem

(Asked by: username_0 on 2013-05-07)

I am reading [this](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.2589&rep=rep1&type=pdf) 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?

**Tags:** graph-theory, cg.comp-geom, dynamic-programming

> **Comments:**
> **username_1**: Could you please make your question more self-contained by including the offending definition and some context?  

---

## 1 answers

### Answer by username_0 on 2013-05-07. Score: 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)](https://i.sstatic.net/ls7Zv.png)
2. $Path\_{H}(v)$ are the paths connecting $v$ to the vertices that are not included in this region.
   ![enter image description here](https://i.sstatic.net/C5FRR.png)
3. $Path\_{H}$ are paths inside the region  
   ![enter image description here](https://i.sstatic.net/V77Hp.png)

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.


---

