6
$\begingroup$

Given a connected $d$-regular graph $G=(V,E)$, generate a sequence of minors by performing only edge contractions and loop deletions (as, e.g., in Karger's algorithm) until the graph collapses to a single vertex. I am interested in protocols for which one can obtain (asymptotic) upper bounds on the maximum degree across all minors generated as a function of $|V|$.

A naive contraction sequence and bound: pick a vertex and keep contracting its incident edges. Then the maximum degree encountered during the process will scale as $|V|$, unless $G$ is a cycle.

Intuition (and some numerical experiments) suggest that there must be algorithms and / or other subclasses of graphs (i.e., planar, small $d$, or others) for which the scaling is slower (possibly sublinear in $|V|$). For example, choosing an edge contraction sequence according to the minimum cut of $G$ and each subsequent minor seems to always be scaling better than the naive scheme.

It seems to me that this problem must have been studied before. Are there any examples in the literature?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I think there is a better bound for planar graphs with maximum degree $\Delta$. Is the following correct / obvious? If yes, is it (or a simpler way to prove the same thing) generally known? If yes, is there a reference?

Claim: Let $G=(V,E)$ be a planar graph with maximum degree $\Delta$. Then a sequence of edge contractions that leads from $G$ to $K_1$, such that the maximum degree of all minors generated during the contractions is $O((\Delta|V|)^{1/2})$, always exists.

To prove this, make the following construction. Via the planar separator theorem, find an edge separator hierarchy that partitions $G$ into $|V|$ subgraphs of size $1$. Perform at most $\log_{3/2}|V|$ steps of contracting all edges belonging to the smallest separators in the hierarchy. At each step, the edges incident to any vertex belong to $O(1)$ separators, and hence they are at most $O((\Delta|V|)^{1/2})$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I suspect this is far from optimal. An edge adjacent to a vertex of degree 1 or 2 can be contracted without increasing the maximum degree. Also, a 3-connected planar graph has an edge whose two degrees sum to at most 13 (Kotzig, 1955) so contracting gives the new vertex degree at most 11. So we can continue without exceeding $\max\{\Delta,11\}$ unless we meet something which is not 3-connected but still has minimum degree at least 3. I'm assuming we keep the graph simple, otherwise this is all wrong. $\endgroup$
    – Brendan McKay
    Commented Aug 27, 2019 at 12:57
  • 1
    $\begingroup$ Apparently Kotzig's theorem only requires minimum degree 3, see sciencedirect.com/science/article/pii/S0012365X1200489X . So if we are dealing with simple planar graphs and contractions remove loops and multiple edges, $\max\{\Delta,11\}$ is good. With multiple allowed I didn't figure it out; see Thm 3.1 and realise that "normal plane map" has more than one definition. $\endgroup$
    – Brendan McKay
    Commented Aug 27, 2019 at 13:27
  • $\begingroup$ I think that if one does not simplify multiple edges (only loops), the square-root scaling is the best one can hope for. This is implied by the NP-hardness of various decision problems on planar graphs. I wonder whether there are specific upper bounds for length of separators in e.g. $d$-regular planar graphs. $\endgroup$
    – delete000
    Commented Aug 27, 2019 at 21:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .