Approximability of Connected Factors

NEW

Problem: For each fixed integer $k\ge 0$, let $d=\lceil n/2\rceil-k$. Given a finite simple undirected graph $G=(V,E)$ on $n$ vertices, decide whether $G$ has a spanning connected $d$-regular subgraph, i.e. a connected $d$-factor. This is the $(\lceil n/2\rceil-k)$-RCS problem. The reconstruction follows from the paper’s notation: RCS is the connected regular factor decision problem.

Result: The conjecture is true. For every fixed $k$, $(\lceil n/2\rceil-k)$-RCS is decidable in polynomial time, in fact in time $n^{O(k)}$ using the standard polynomial-time $f$-factor algorithm.

Proof sketch with full correctness ingredients.

Let $d=\lceil n/2\rceil-k$, and assume $n>14k$; the remaining finitely many $n$ are constant-size for fixed $k$ and can be brute-forced.

First compute a $d$-factor using the polynomial-time $f$-factor algorithm. If none exists, reject.

Key lemma 1. Suppose a $d$-factor $H$ has exactly two components $A,B$. Put

Then $\rho_A+\rho_B=n-2-2d\le 2k-2$. If the bipartite graph $G[A,B]$ has a matching of size at least $\rho_A+\rho_B+2$, then $G$ has a connected $d$-factor.

Indeed, among the matched cross edges $a_i b_i$, each $a_i$ has at most $\rho_A$ non-neighbours inside $H[A]$, and each $b_i$ at most $\rho_B$ non-neighbours inside $H[B]$. Hence two matched edges $a_i b_i,a_j b_j$ satisfy $a_i a_j\in E(H)$ and $b_i b_j\in E(H)$. Removing $a_i a_j,b_i b_j$ and adding $a_i b_i,a_j b_j$ preserves all degrees and connects the two components. The removed internal edges are not bridges because each component has order $d+1+O(k)<2d+2$ and is $d$-regular.

By König’s theorem, if no such matching exists, then $G[A,B]$ has a vertex cover of size at most $2k-1$, hence $G$ has a separator of size at most $2k-1$.

So if $G$ has no separator of size $\le 2k-1$, then any disconnected $d$-factor can be switched into a connected one. Thus accept.

It remains to handle the case where $G$ has a separator $S$ with $|S|\le 2k-1$. Since a $d$-factor exists, $\delta(G)\ge d$. For $n>14k$, every component $C$ of $G-S$ has

so $G-S$ has exactly two components, say $C_1,C_2$. Moreover, for any $d$-factor $F$, each induced graph $F[C_i]$ is connected: otherwise two components inside some $C_i$, together with the other side of $G-S$, would give three disjoint sets each of size at least $d-|S|+1$, contradicting $n>14k$.

Therefore, for this fixed separator $S$, a $d$-factor $F$ is connected iff the auxiliary graph on bags

is connected, where two bags are adjacent if $F$ uses at least one edge between them.

There are only $O(k)$ bags. Enumerate every spanning tree on these bags, and for each tree edge enumerate one actual graph edge between the corresponding bags. Force those $O(k)$ edges to be present and run the $f$-factor algorithm with reduced degree demands. If some forced instance succeeds, the resulting $d$-factor has connected auxiliary graph and is therefore connected. Conversely, any connected $d$-factor contains such a spanning tree of bag-adjacencies, so the enumeration will find it.

This gives an $n^{O(k)}$-time algorithm for each fixed $k$. Hence $(\lceil n/2\rceil-k)$-RCS is in P for every constant $k$.

Citation: No prior resolution is used here. The algorithm relies on the standard polynomial-time $f$-factor algorithm from Tutte’s factor theory and Edmonds’ matching algorithm.