Deconstructing intractabilityA multivariate complexity analysis of interval constrained coloring ?
The NP-hard Interval Constrained Coloring (ICC) problem appears in the interpretation of experimental data in biochemistry dealing with protein fragments. Given a set of m integer intervals in the range 1 to n and a set of m  associated multisets of colors (specifying for each interval the colors to be used for its elements), one asks whether there is a consistent coloring for all integer points from {1,,n} { 1 ,  , n } that complies with the constraints specified by the color multisets. We thoroughly analyze a known NP-hardness proof for ICC. In this way, we identify numerous parameters that naturally occur in ICC and strongly influence its practical solvability. Accordingly, we present several positive (fixed-parameter) tractability results exploiting various parameterizations. We substantiate the usefulness of this multivariate algorithmics approach by presenting experimental results with real-world data.
multivariate algorithmics interval constraint coloring parametrized complexity np-hard problem experiments