Summary: A \(k\)-proper connected 2-coloring for a graph is an edge bipartition which ensures the existence of at least \(k\) vertex disjoint simple alternating paths (i.e., paths where no two adjacent edges belong to the same partition) between all pairs of vertices. In this work, for every \(k \in \mathbb{N}_{>0} \), we show that exactly counting such colorings is #P-hard under many-one counting reductions, as well as #P-complete under many-one counting reductions for \(k=1\). Furthermore, for every \(k \in \mathbb{N}_{>0} \), we rule out the existence of a \(2^{o\left( \frac{n}{k^2}\right) }\) time algorithm for finding a \(k\)-proper connected 2-coloring of an order \(n\) graph under the ETH, or for exactly counting such colorings assuming the moderated Counting Exponential Time Hypothesis (#ETH) of (Dell et al.; ACM Trans. Algorithms 10(4); 2014). Finally, assuming the Exponential Time Hypothesis (ETH), and as a consequence of a recent result of (Dell & Lapinskas; ACM Trans. Comput. Theory 13(2); 2021), for every \(k \in \mathbb{N}_{>0}\) and every \(\epsilon > 0\), we are able to rule out the existence of a \(2^{o\left( \frac{n}{k^2}\right) }/\epsilon^2\) time algorithm for approximating the number of \(k\)-proper connected 2-colorings of an order \(n\) graph within a multiplicative factor of \(1 + \epsilon \).
For the entire collection see [Zbl 07831397].