  Arkin et al.~\cite{ArkinBCCJKMM17} recently introduced \textit{partitioned
pairs} network optimization problems: given a metric-weighted graph on $n$
pairs of nodes, the task is to color one node from each pair red and the other
blue, and then to compute two separate \textit{network structures} or disjoint
(node-covering) subgraphs of a specified sort, one on the graph induced by the
red nodes and the other on the blue nodes. Three structures have been
investigated by \cite{ArkinBCCJKMM17}---\textit{spanning trees},
\textit{traveling salesperson tours}, and \textit{perfect matchings}---and the
three objectives to optimize for when computing such pairs of structures:
\textit{min-sum}, \textit{min-max}, and \textit{bottleneck}. We provide
improved approximation guarantees and/or strengthened hardness results for
these nine NP-hard problem settings.
