On the Complexity of Finding 1-Center Spanning Trees

We reduce IndependentSet to CycleFreeCut-D. Precisely, for an instance $(G,k)$ of IndependentSet, we construct an instance $(G^{\prime },k+1)$ of CycleFreeCut-D as follows (see Fig. 2). The vertex set of $G^{\prime }$ is $V^{\prime }\cup X\cup Y$, where $|V^{\prime }|=|V(G)|$ and $|X|=|Y|=|E(G)|$. Each member of $V^{\prime }$ corresponds to a vertex of $G$, and each member of $X$ or $Y$ corresponds to an edge of $G$. We use the bijections $f:V(G)\to V^{\prime }$, $f_X:E(G)\to X$, and $f_Y:E(G)\to Y$ to describe the correspondences, and for convenience let $g=f^{-1}$, $g_X=f_X^{-1}$, and $g_Y=f_Y^{-1}$. Two vertices $a$ and $b$ of $G^{\prime }$ are adjacent if

• $\mathrm{■}$

  $a$ and $b$ are incident in $G$; namely, one of them corresponds to an edge of $G$ and the other corresponds to an endpoint of the edge, or

• $\mathrm{■}$

  $\{a,b\}\subseteq X\cup Y$.

We claim the following.

For $k=1$, the claim holds due to Observation 5 so we assume that $k\ge 2$. For necessity, let $I$ be an independent set of size $k$ and let $I^{\prime }=f(I)$. Consider the set of edges $F=\{e\in E(G^{\prime }):e\text{ has an endpoint in }{I}^{\prime }\}$. Clearly, $G^{\prime }-F$ contains at least $k+1$ components. Moreover, every member $x$ in $X\cup Y$ has at most one neighbor in $I^{\prime }$ since otherwise the two neighbors $a$ and $b$ of $x$ have the corresponding vertices $g(a)$ and $g(b)$ adjacent in $G$. Thus, there is no cycle between $I^{\prime }$ and $(V^{\prime }\setminus I^{\prime })\cup X\cup Y$, showing that $F$ is cycle-free.

For sufficiency, let $F$ be a cycle-free $(k+1)$-cut of $G^{\prime }$. We show that

• $\mathrm{■}$

  $X\cup Y$ is contained in a component of $G^{\prime }-F$, and

• $\mathrm{■}$

  the other components, each consisting of a single vertex, together correspond to an independent set of $G$.

First, $G^{\prime }-F$ contains at least three components. If the clique $X\cup Y$ is not contained in a component, then by Observation 5 there exists $x\in X\cup Y$ with $x$ in a component and $(X\cup Y)-x$ contained in another. Without loss of generality, assume that $x\in X$. The third component contains a vertex, say $v^{\prime }$, in $V^{\prime }$. Let $v=g(v^{\prime })$, $e=g_X(x)$, and $y=f_Y(e)$. If $v$ is an endpoint of $e$, then $x$, $y$, and $v^{\prime }$ form a triangle contained in $F$. Otherwise, $v$ is an endpoint of an edge $e^{\prime }$ of $G$. Let $x^{\prime }=f_X(e^{\prime })$ and $y^{\prime }=f_Y(e^{\prime })$. Then $v^{\prime }$, $x^{\prime }$, $y^{\prime }$, and $x$ form a 4-cycle contained in $F$. Therefore, $X\cup Y$ is contained in a component of $G^{\prime }-F$.

For the second, except the component containing $X\cup Y$, all components consist of vertices from $V^{\prime }$. Since $V^{\prime }$ induces an independent set of $G^{\prime }$, each of these components consists of a single vertex. In addition, let $u$ and $v$ be the endpoints of an edge $e$ in $G$, and let $u^{\prime }=f(u)$, $v^{\prime }=f(v)$, $x=f_X(e)$ and $y=f_Y(e)$ be the corresponding vertices in $G^{\prime }$. If both $u^{\prime }$ and $v^{\prime }$ are in components not containing $X\cup Y$, then $u^{\prime }$, $v^{\prime }$, $x$ and $y$ form a 4-cycle, violating that $F$ is cycle-free. Thus, the components not containing $X\cup Y$ correspond to an independent set of $G$ of size at least $k$.

Since $V^{\prime }$ induces an independent set and $X\cup Y$ induces a clique, the graph $G^{\prime }$ is a split graph. Thus, the theorem follows. $◀$

Suppose to the contrary that there is a complete $s$-partite graph $G$ that has a cycle-free $k$-cut $F$, for $k\ge 3$. Observe that there is a component of $G-F$ that intersects at least two partite sets since otherwise $F$ induces a $C_3$. Let $Q$ be such a component. We claim that there is a $C_3$ or a $C_4$ connecting $Q$ and two other components $Q^{\prime }$ and $Q^{\prime \prime }$.

If $Q$ intersects only two partite sets, we take $Q^{\prime }$ as a component that intersects another partite set, say $U$, and $Q^{\prime \prime }$ an arbitrary component other than $Q$ and $Q^{\prime \prime }$. Let $q^{\prime }$ and $q^{\prime \prime }$ be two vertices from $Q^{\prime }$ and $Q^{\prime \prime }$, respectively, with $q^{\prime }\in U$. If $q^{\prime }$ and $q^{\prime \prime }$ are adjacent, then there is a $C_3$ induced by $q^{\prime }$, $q^{\prime \prime }$, and a vertex in $Q$; otherwise, both $q^{\prime }$ and $q^{\prime }$ belong to $U$, and there is a $C_4$ formed by $q^{\prime }$, $q^{\prime \prime }$, and two vertices from different partite sets in $Q$.

If $Q$ intersects three or more partite sets, $Q^{\prime }$ and $Q^{\prime \prime }$ can be arbitrary. Then an argument similar to the above applies. Consequently, $F$ is not cycle-free in either case, which is a contradiction. $◀$

We reduce 3-IndependentSet to CycleFreeCut-D. Let $(G,k)$ be an instance of 3-IndependentSet. The reduced instance, $(G^{\prime },k+2)$, is constructed like the reduction given in the proof of Lemma 11. The vertex set $V(G^{\prime })$ is $V^{\prime }\cup X\cup Y\cup \{a,b\}$, where $|V^{\prime }|=|V(G)|$, $|X|=|Y|=|E(G)|$. The correspondences are the following bijections:

• $\mathrm{■}$

  $f:V(G)\to V^{\prime }$,

• $\mathrm{■}$

  $f_X:E(G)\to X$, and

• $\mathrm{■}$

  $f_Y:E(G)\to Y$.

Also, for convenience, let $g=f^{-1}$, $g_X=f_X^{-1}$, and $g_Y=f_Y^{-1}$. The adjacency in $G^{\prime }$ is defined as follows. The subgraph induced by $X\cup Y\cup \{a,b\}$ is a complete $3$-partite graph, with partite sets $\{a\}$, $\{b\}$, and $X\cup Y$. In addition, for every edge $e$ of $G$ with endpoints $u$ and $v$, we make a $4$-cycle $f(u)\to f_X(e)\to f(v)\to f_Y(e)\to f(u)$. See Fig. 3 for an illustration.

We claim that $G$ has an independent set of size $k$ if and only if $G^{\prime }$ has a cycle-free $(k+2)$-cut. For sufficiency, let $F$ be a cycle-free $(k+2)$-cut. Then $G^{\prime }-F$ has at least $k+2$ components. By Lemma 13, $X\cup Y\cup \{a,b\}$ intersects at most two components so at least $k$ components consist of vertices from $V^{\prime }$. Since $V^{\prime }$ induces an independent set of $G^{\prime }$, each of these components consists of a single vertex. Let $u$ and $v$ be two such components. There is no edge $e$ of $G$ with endpoints $g(u)$ and $g(v)$ since otherwise $u$, $f_X(e)$, $v$, and $f_Y(e)$ form a $4$-cycle. Thus, the components consisting of vertices in $V^{\prime }$ correspond to an independent set of $G$, with size at least $k$.

For necessity, let $I$ be an independent set of $G$ with $|I|\ge k$. Let $F$ be the cut of $G^{\prime }$ such that the components $G^{\prime }-F$ are the subgraphs induced by the following vertex subsets:

• $\mathrm{■}$

  $\{f(u)\}$, for each $u\in I$,

• $\mathrm{■}$

  $(X\cup Y\cup \{a,b\}\cup (V^{\prime }\setminus f(I)))-f_X(e)$, where $e$ is an arbitrary edge of $G$, and

• $\mathrm{■}$

  $\{f_X(e)\}$.

Clearly, $F$ is a $(k+2)$-cut. We show that $F$ is cycle-free below. Let $C$ be the component induced by $(X\cup Y\cup \{a,b\}\cup (V^{\prime }\setminus f(I)))-f_X(e)$. Each vertex of $C$ has at most one neighbor outside $C$, which implies that $F$ induces no cycle passing through $C$. The remaining subgraph, induced by $f_X(e)\cup f(I)$, contains at most two edges so there is no cycle, either. Thus, $F$ is a cycle-free $(k+2)$-cut.

The graph $G^{\prime }$ in the reduced instance is sparse. The reason is that it has $n+2m+2$ vertices and $8m+1$ edges, where $n$ and $m$ are the numbers of vertices and edges of $G$, respectively. In addition, when the maximum degree of $G$ is no more than three, we have $N=O(n)$, and by Theorem 8 the theorem follows. $◀$

Since the number of spanning trees in an $N$-vertex sparse graph is of $2^{O(N)}$, the naive method of enumerating all spanning trees and keeping the one with minimum eccentricity is optimal for sparse graphs.

Recall that for a given graph $G$, the requested graph $G^{\prime }$ has $V(G^{\prime })=V^{\prime }\cup X\cup Y$, where there are one-to-one correspondences between $V(G)$ and $V^{\prime }$, $E(G)$ and $X$, and $E(G)$ and $Y$, respectively. Each edge of $G$ corresponds to a $4$-cycle in $G^{\prime }$, and $X\cup Y$ forms a clique (see Fig. 2). We show

1. (i)

   how a spanning tree $T$ of $G^{\prime }$ corresponds to an independent set $I$ of $G$, and

2. (ii)

   the error parameter is linearly preserved; i.e., if $\mathrm{ecc}(T)\le (1+\delta \epsilon ){\mathrm{𝖮𝖯𝖳}}_{\mathrm{ecc}}$, then $|I|\ge (1-\epsilon ){\mathrm{𝖮𝖯𝖳}}_{\mathrm{𝗂𝗇𝖽}}$.

Let $N=|V(G^{\prime })|$. For (i), we choose $I$ to be the set of vertices that correspond to the single-vertex components of $G^{\prime }-T$. Moreover, we claim the following.

Since every spanning tree is a cycle-free cut, the sufficiency follows immediately from Claim 12. For necessity, by Claim 12 there is a cycle-free $(k+1)$-cut, say $F$, with $c(G^{\prime }-F)=k+1$. Specifically, there is a subset $U^{\prime }$ of $V^{\prime }$ forming $k$ of the components, where every single vertex forms one. The remaining component, say $C$, is the subgraph induced by $X\cup Y\cup (V^{\prime }\setminus U^{\prime })$. Since $X\cup Y$ is a clique and every vertex of $V^{\prime }\setminus U^{\prime }$ has degree at least two in $C$, there is a spanning tree $T_F$ of $G^{\prime }$ containing all edges in $F$ without disconnecting $C$. By Proposition 3, $\mathrm{ecc}(T_F)=2\left(N-(k+1)\right)$. According to the analysis above, it can be further derived that

and

For (ii), assume that $\mathrm{ecc}(T)\le (1+\delta \epsilon ){\mathrm{𝖮𝖯𝖳}}_{\mathrm{ecc}}$. We claim that $|I|\ge (1-\epsilon ){\mathrm{𝖮𝖯𝖳}}_{\mathrm{𝗂𝗇𝖽}}$. Let $n=|V(G)|$. Since the maximum degree of $G$ is upper bounded by $B$, we have

The chromatic number of a graph is upper bounded by the maximum degree plus one [9]. It follows that

Along with Eq. (2),

Thus, we have

$◀$

The APX-hardness follows immediately from Lemma 16. For the inapproximability factor, by Theorem 10 we have that $4$-MaxIndepSet is NP-hard to approximate within a factor of $48/47$. Taking $B=4$, $\delta ={(B^2+2B)}^{-1}$, and $\epsilon =1/48$ in Lemma 16, the corollary is established. $◀$

Analogous to how we modify the proof of Lemma 11 to obtain Lemma 14, by replacing $G^{\prime }$ in Lemma 16 with the sparse graph in Lemma 14, we have the following results.

We give a reduction from 3SAT. We assume that each clause contains exactly three literals and each variable appears in some clauses. Consider a 3SAT instance $\mathrm{\Phi }$ with $n$ variables $x_1,\mathrm{\dots },x_n$ and $m$ clauses $c_1,\mathrm{\dots },c_m$. In the reduced instance $(G,s,t)$, there are

• $\mathrm{■}$

  two distinguished vertices, one for $s$ and the other for $t$;

• $\mathrm{■}$

  $n$ variable gadgets, $𝗏\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_1,\mathrm{\dots },𝗏\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_n$, each consisting of two $P_{4n}$s;

• $\mathrm{■}$

  $m$ clause gadgets, $𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_1,\mathrm{\dots },𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_m$, each consisting of three $P_{8m-2}$s;

• $\mathrm{■}$

  an assignment gadget, consisting of $n+2m-1$ double stars; for each double star, the internal nodes $u$ and $v$ of the left and the right stars are connected to $s$ and $t$, respectively, each with a path of specific length. We denote the $s,u$-path by $R_s(u)$ and the $v,t$-path by $R_t(v)$.

Each path in the variable gadgets and the clause gadgets is called a literal path. For the two literal paths in a variable gadget, one corresponds to the positive literal and the other the negative one. For the three literal paths in a clause gadget, there is a one-to-one correspondence to the literals in the clause. To ease the presentation, we embed each literal path in the plane horizontally, with a left end and a right end. Vertices on a literal path are numbered from left to right. Let $D(X,i)=\{v:v\text{ is the }i\text{th vertex on a path in gadget }X\}$, where $X$ is a variable gadget or a clause gadget. The gadgets are interrelated as follows. The left end of each literal path in a variable gadget is made adjacent to $s$; the right end of each literal path in a clause gadget is made adjacent to $t$; for each pair of literal paths $(P,Q)$, with $P$ in a variable gadget and $Q$ in a clause gadget, if both $P$ and $Q$ correspond to an identical literal, concatenate these two paths by making the right end of $P$ and the left end of $Q$ adjacent. We call the resulting graph $H$. See Fig. 4 for an example.

Consecutive variable gadgets, consecutive clause gadgets, and the literal paths in a clause gadget are bridged using the double stars in the assignment gadget. Details are given below.

• $\mathrm{■}$

  Each of the first $n-1$ double stars is an $S_{2,2}$, bridging a pair of consecutive variable gadgets. To bridge $𝗏\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_i$ and $𝗏\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_{i+1}$, for $i\in [n-1]$, the designated sets of vertices are $D(𝗏\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_i,4i-2)$ and $D(𝗏\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_{i+1},4i+1)$.

• $\mathrm{■}$

  The $n$th double star is an $S_{2,3}$, bridging the $n$th variable gadget with the first clause gadget. The designated sets of vertices are $D(𝗏\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_n,4n-2)$ and $D(𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_1,1)$.

• $\mathrm{■}$

  The following $2m-1$ double stars are $S_{3,3}$s. Except for the last one, every two of them bridge a clause gadget with itself, and the clause gadget with the next one; the last double star bridges the last clause gadget with itself only. For $i\in [m]$, to bridge $𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_i$ with itself, the designated sets of vertices are $D(𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_i,8i-6)$ and $D(𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_i,8i-3)$; to bridge $𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_i$ with $𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_{i+1}$, the designated sets of vertices are $D(𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_i,8i-2)$ and $D(𝖼\mathrm{\_}{\mathrm{𝗀𝖺𝖽𝗀𝖾𝗍}}_{i+1},8i+1)$.

For a critical edge $uv$ of a double star in an assignment gadget, the numbers of vertices on $R_s(u)$ and $R_t(v)$ are chosen so that the path $s\underset{R_s(u)}{\rightsquigarrow }u\to v\underset{R_t(v)}{\rightsquigarrow }t$ has length equal to a shortest $s,t$-path in $H$ and remains a shortest $s,t$-path in $G$. This completes the construction of $(G,s,t)$. See Fig. 5 for an example.

We now show that $\mathrm{\Phi }$ is satisfiable if and only if there is a shortest $s,t$-path that hits all shortest $s,t$-paths in $G$. For necessity, given a satisfiable assignment, we consider a shortest $s,t$-path $P$ such that

• $\mathrm{■}$

  $P$ passes through all critical edges in the assignment gadget;

• $\mathrm{■}$

  $P$ touches the path corresponding to a true literal of every variable gadget;

• $\mathrm{■}$

  $P$ touches two of the three paths of every clause gadget, excluding an arbitrary one corresponding to a true literal in the clause.

If there is a path $Q$ not hit by $P$, then $Q$ contains no critical edges. By Observation 21, $Q$ contains two disjoint subpaths corresponding to the same literal. However, the one from the variable gadget corresponds to a false literal, and the other, which is from a clause gadget, corresponds to a true literal. This leads to a contradiction, so $P$ is the requested path. For sufficiency, observe that the path $P$ contains all critical edges. In addition, $P$ touches exactly one literal path in each variable gadget. Let $A$ be the truth assignment such that true literals have their corresponding literal paths in the variable gadgets touched by $P$. We claim that $A$ satisfies $\mathrm{\Phi }$. Suppose to the contrary that there is a clause that contains no true literal. Then, there is a literal whose corresponding literal paths in the variable gadget and the clause gadget are not hit by $P$, and so is the shortest $s,t$-path that passes through these two literal paths, a contradiction. $◀$

The necessity follows immediately from the definition. For sufficiency, we claim that there is an $S$-governed forward $s,t$-path $P$ such that $g={g_{i-1}|}_P$ and $h={h_i|}_P$, and then by Eq. (7)

for all $v\in U_i$. Such a path $P$ can be constructed in a straightforward manner. Let $\{P^{\prime },P^{\prime \prime }\}\subseteq {𝒮}_{s,t}$ such that $g={g_{i-1}|}_{P^{\prime }}$ and $h={h_i|}_{P^{\prime \prime }}$. Clearly, the path $s\underset{P^{\prime }}{\rightsquigarrow }x\underset{P^{\prime \prime }}{\rightsquigarrow }y\underset{P^{\prime \prime }}{\rightsquigarrow }t$ is the requested one. $◀$

A thick layer has size greater than $\sqrt{n}$, so there are no more than $\sqrt{n}$ ones. Since each thick layer has size at most $n$, there are $O(n^{\sqrt{n}})$ different exact hitting sets of the thick layers. For each exact hitting set $S$ of the thick layers, since all $S$-governed forward $s,t$-paths $P$ coincide on $S$, there is exactly one function in ${{\mathscr{H}}_i|}_{x,y}$, given $x\in U_{i-1}$ and $y\in U_i$. This function can be computed in polynomial time by finding a forward $x,y$-path that uses the edges on $P$ as little as possible. For $x\in U_{i-1}$, the set ${{𝒢}_{i-1}|}_x$ contains $O\left({(l+1)}^{\sqrt{n}}\right)$ functions so along with Lemma 24 computing ${{𝒢}_i|}_y$ for all $y\in U_i$ takes $O\left({\left(|U_{i-1}|\cdot |U_i|\right)}^2\cdot {(l+1)}^{\sqrt{n}}\right)$ time. The overall running time is $O\left(n^{\sqrt{n}}\cdot \left(\sqrt{n}+{\sum }_{i=1}^k\left(\mathrm{𝗉𝗈𝗅𝗒}(n)+{\left(|U_{i-1}|\cdot |U_i|\right)}^2\cdot {(l+1)}^{\sqrt{n}}\right)\right)\right)=2^{\tilde{O}(\sqrt{n})}$. See Algorithm 1 for the pseudocode.