Author: | Alex Popa, Adrian Miclaus |
Prepared by: | Adrian Miclaus |
Solved by: | |
First to solve: | N/A |
Let G=(V,E) be a simple, undirected graph together with a coloring c:V\to\mathcal{C}. A subgraph G'=(V,E') is feasible if every connected component of G' is colorful (i.e., contains no two vertices with the same color).
Notation. For X\subseteq V let N(X)=\{u\in V\setminus X:\exists v\in X,\ (u,v)\in E\}. For X\subseteq V and \mathcal{C}_0\subseteq\mathcal{C} let N_{\mathcal{C}_0}(X)=\{u\in N(X):c(u)\in\mathcal{C}_0\}. For a color \gamma\in\mathcal{C} let V_\gamma=\{v\in V:c(v)=\gamma\}. We call a tree of diameter 2 a star.
For each color define s_\gamma \;=\; \max_{X\subseteq V_\gamma}\ \bigl(|X|-\lvert N_{\mathcal{C}\setminus\{\gamma\}}(X)\rvert\bigr). Then any feasible subgraph has at least s_\gamma singletons of color .
Proof. Fix a feasible G'=(V,E') and with s_\gamma>0. Let X\subseteq V_\gamma attain the maximum. For every x\in X that is not a singleton in G', pick an arbitrary neighbor of inside its (component of) G'. Such lies in N_{\mathcal{C}\setminus\{\gamma\}}(X), and distinct lie in distinct components of G', so the are pairwise distinct. Hence at most |N_{\mathcal{C}\setminus\{\gamma\}}(X)| vertices of are non-singletons in G', implying at least |X|-\lvert N_{\mathcal{C}\setminus\{\gamma\}}(X)\rvert=s_\gamma singletons of color . ◻
Every feasible subgraph has at least \sum_{\gamma\in\mathcal{C}} s_\gamma singletons in total.
We maintain a feasible G'=(V,E'), starting from E'=\varnothing. As an invariant, every component of G' is always a singleton, an edge, or a star. We process colors \gamma\in\mathcal{C}; for a fixed let S_\gamma\subseteq V_\gamma be the set of -singletons in G'.
An alternating path (for ) in w.r.t. G' is a simple path whose edges alternate between E\setminus E' and E', starting at a vertex of S_\gamma with the first edge in E\setminus E', and ending at a vertex that satisfies one of:
is a leaf of a star component of G'; or
the component of in G' contains no vertex of color .
Applying such a path means replacing E' by the symmetric difference E'\triangle E(p).
A BFS from S_\gamma (expanding via E\setminus E' to non- vertices and via E' back to vertices) either finds a valid endpoint and reconstructs through predecessors, or certifies that none exists.
Let be an alternating path for color found by the BFS above, and let \widetilde{G} be the result of applying to G'. Then:
the number of -singletons drops by one;
for every \gamma'\neq\gamma, the number of \gamma'-singletons does not increase;
every component of \widetilde{G} is colorful; and
every component of \widetilde{G} is a singleton, an edge, or a star.
Proof. Edges along are toggled. Because starts at a -singleton and the first edge added connects it to a different color, that start vertex ceases to be a singleton. The endpoint conditions ensure we either detach a leaf from a star or insert a vertex into a component without color ; in both cases colorful feasibility is preserved and no other color gains new singletons. Local structure along keeps components within the invariant (singleton/edge/star) family. ◻
If the BFS for color finds no alternating path, then |S_\gamma|=s_\gamma.
Proof. The explored search layers implicitly define a maximizing set X\subseteq V_\gamma with |X|-\lvert N_{\mathcal{C}\setminus\{\gamma\}}(X)\rvert=|S_\gamma|: new neighbors that could enable a decrease are exactly the certified non-existent endpoints. Comparing with Lemma [lem:lower] gives equality. ◻
Repeating: for each \gamma\in\mathcal{C}, while an alternating path exists, apply it; otherwise move to the next color. The final G' is a feasible subgraph minimizing the number of singletons, and the procedure runs in O(|V| \cdot |E|).
Proof. By Lemma [lem:effect], each successful application strictly decreases the count of -singletons and preserves feasibility and the invariant, hence at most successes occur overall. When the process halts for color , Lemma [lem:tight] yields |S_\gamma|=s_\gamma; after all colors are processed we have exactly \sum_\gamma s_\gamma singletons, which matches the lower bound of Corollary [cor:sum-lb]. ◻