Prerequisite: DFS-Trees
Consider the following problem:
Given a graph 𝐺(𝑉,𝐸) on 𝑛 nodes, find a simple path with at least 𝑛/2 nodes in either 𝐺 or its complement 𝐺′.
Let's ask ourselves a dumb question: Given some simple path 𝑃 in 𝐺, can we find a simple path 𝑃′ in 𝐺′ that contains every node that's not in 𝑃?
If this was possible for any path 𝑃, then at least one of 𝑃 or 𝑃′ would satisfy our requirements, as max(|𝑃|,|𝑃′|) =max(|𝑃|,𝑛 −|𝑃|) ≥𝑛/2.
There can of course be exponentially many paths 𝑃 in 𝐺, so we restrict our analysis to a convenient subset of paths. Let's construct some "DFS-Forest" 𝐹 of 𝐺 (a DFS-Tree for every connected component). In fact, let's simplify our analysis even further for the moment, and assume that 𝐺 is connected, so it yields just one DFS-Tree.
Now, consider paths 𝑃 from the root 𝑟 to some node 𝑙. This simple path clearly exists in 𝐺, but what about 𝑃′? Can we somehow chain together nodes that don't lie in 𝑃 into a simple path?
The DFS-Tree, along with 𝑃 can be visualised in the above manner. Can we think of some connection between DFS-trees and complement graphs that would allow us to chain together the red nodes to construct 𝑃′?
If you've read the blog I've linked at the top, the following observation will seem fairly natural:
Lemma 1
Neither 𝑢 nor 𝑣 is an ancestor of the other in 𝐹 ⟹ edge (𝑢,𝑣) exists in 𝐺′.
Now consider the subtrees 𝑠1,𝑠2,…𝑠𝑘 hanging off 𝑃. The above observation implies that there's an edge in 𝐺′ between every pair of nodes that belong to different subtrees!
Therefore, one (of possibly many) way to construct a path in 𝐺′ that visits every node in 𝑆 =𝑠1 ∪𝑠2 ∪⋯ ∪𝑠𝑘 could be to start at some node outside 𝑃, and then repeatedly jump to a previously unvisited node that lies in a different hanging subtree from the current one.
What condition on 𝑠1,𝑠2,…𝑠𝑘 will allow us to always construct 𝑃′ in such a manner? We just want max(|𝑠𝑖|) ≤⌈|𝑆|2⌉!
Proof
Necessary and sufficient condition for rearranging a string such that no two adjacent characters are equal.
But wait a minute, does there always exist a 𝑃 such that the induced 𝑠1,𝑠2,…𝑠𝑘 satisfy this property?
Lemma 2
For any rooted tree, we can always find a path 𝑃 starting at the root such that the induced 𝑠1,𝑠2,…𝑠𝑘 satisfy max(|𝑠𝑖|) ≤⌈|𝑆|2⌉.
Proof
Denote the path between 𝑟 and 𝑙 by 𝑃, and 𝑆 =𝑉 ∖𝑃.
Let's start at the root, with 𝑙 =𝑟. If this path satisfies the required condition, then we're done. But what if it doesn't? This would mean that exactly one child 𝑐 of 𝑙 has a subtree of size >⌈|𝑆|2⌉.
Clearly, any valid 𝑙 must lie in the subtree of 𝑐, as any other choice would result in the hanging subtree of 𝑐 having >⌈|𝑆|2⌉ nodes. We then set 𝑙 =𝑐 and recursively continue (𝑃 and 𝑆 are updated). At every step, if there's some child of 𝑙 with subtree-size >⌈|𝑆|2⌉, we're forced to place 𝑙 somewhere in its subtree. Since we'll eventually hit a leaf (which has no children), we're guaranteed to reach a node 𝑙 where there's no "dominant" child. Note that whenever we're at a node with a dominant child, no induced hanging subtree outside the subtree of the current node can be dominant.
When we reach such a node 𝑙, can there be some dominant 𝑠𝑖 induced outside 𝑙's subtree? Let 𝑝 be the parent of 𝑙, and 𝑥 be the subtree size of 𝑙. Since 𝑝 doesn't satisfy the condition, we must have 𝑥 >⌈(|𝑆|+1)2⌉. This implies that the maximum possible size of any hanging-subtree outside the subtree of 𝑙 is ≤⌈|𝑆|2⌉.
Hence, 𝑙 must be valid.
So, that's it. You find 𝑙 such that the path 𝑃 from 𝑟 to 𝑙 satisfies this property. If |𝑃| ≥𝑛/2, you're done. Otherwise, you can just construct a path from the hanging subtrees.
The observant reader will now exclaim, "[user:DNR,2026-11-18]! Your analysis holds only under the assumption that 𝐺 is connected (so 𝐹 has only one DFS-tree)!"
First, notice that Lemma 1 holds for arbitrary DFS-forests, so if we pick a rooted path in some DFS tree in 𝐹, then we can treat any other tree as an induced subtree 𝑠𝑖 too! But what about lemma 2? We did need it to guarantee the existence of 𝑙.... Can we get an analogous lemma for DFS-forests?
Lemma 3
For any rooted forest, we can always find a path 𝑃 starting at some root such that the induced 𝑠1,𝑠2,…𝑠𝑘 satisfy max(|𝑠𝑖|) ≤⌈|𝑆|2⌉.
Proof
Construct the DFS-forest, and then add a "virtual root node" which has all the other roots as children.
The argument we used for Lemma 2 works out again.
Therefore, we've solved the problem. It's easy to implement this solution in 𝑂(𝑛 +𝑚).
More
The blog was inspired by the following problem, and one may realise that we have solved it:
Given a graph 𝐺(𝑉,𝐸) on 𝑛 nodes, find a Hamiltonian path that first only uses edges in 𝐺, and then only uses edges in 𝐺′.
The only additional observation that we need (after finding 𝑃 and 𝑃′) is that we can always travel from the last node in 𝑃 to the first node in 𝑃′, because an edge between them must be present in either 𝐺 or 𝐺′.
There's a much simpler 5-line solution that I won't expand upon.