What did we do?

We present piecewise analysis, a new general method that analyzes the running time of branching algorithms.

What did we get?

• We reanalyze two 17-year-old algorithms from Fomin et al. [2007] that solve 4-Coloring and #3-Coloring respectively and improve the analysis of both.

• We obtain a new running time O(1.7215^n) upper bound for 4-Coloring, which is the first improvement in the best known running time since 2007.

What did we do?

• We consider exponential-time algorithms for NP-hard problems that combine a pathwidth-based approach and a branching approach. In this context, we investigate how a running time analysis can decide thresholds to balance the two methods, thereby improving the running times for such NP-hard problems. We approach this question from two complementary angles: advancing algorithmic analysis and developing novel algorithms. We first introduce piecewise analysis, a general method for analyzing the running time of branching algorithms. Unlike traditional approaches that apply a single measure uniformly across all instances, piecewise analysis partitions the instance space into subsets of structurally similar instances. For each subset, we construct a tailored measure based on some properties of the subset. This measure remains fixed during branching, meaning that sub-instances inherit it from their parent instance. This partitioning enables us to exploit relationships between structural parameters among instances, leading to a more refined analysis of the algorithm’s running time. To demonstrate the effectiveness of piecewise analysis, we reanalyze two algorithms originally developed by Fomin et al. for c-Coloring and #c-Coloring, both of which combine branching with a pathwidth-based approach. Using piecewise analysis, we tighten the running time bounds by exploiting how a graph’s pathwidth correlates with the presence of many high-degree vertices and by determining these thresholds to obtain tighter running times. We improve the running time bounds for their algorithms: specifically, from O(1.7272n) to O(1.7207n) for 4-Coloring and from O(1.6262n) to O(1.6225n) for #3-Coloring. We also present a novel algorithm for Independent Dominating Set (IDS). Our algorithm begins with a branching approach, deciding at various stages whether to invoke a pathwidth-based subroutine or continue branching, guided by thresholds precalculated in the analysis. While the algorithm for c-Coloring from Fomin et al. uses pathwidth as a complete replacement for branching when certain thresholds are met, our algorithm for IDS integrates pathwidth as a subroutine within branching.