\input zb-basic
\input zb-ioport
\iteman{io-port 05883239}
\itemau{Komusiewicz, Christian; Niedermeier, Rolf; Uhlmann, Johannes}
\itemti{Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring.}
\itemso{J. Discrete Algorithms 9, No. 1, 137-151 (2011).}
\itemab
Summary: 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,\cdots ,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.
\itemrv{~}
\itemcc{}
\itemut{interval constraint coloring; parametrized complexity; multivariate algorithmics; NP-hard problem; experiments}
\itemli{doi:10.1016/j.jda.2010.07.003}
\end