{'fraction_non_alphanumeric': 0.0349809885931559, 'fraction_numerical': 0.003041825095057034, 'mean_word_length': 5.120930232558139, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Fixed-Parameter Intractability and Tractability of Multiple-Interval Graph Problems

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more then one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for better robustness in the modeling of the specific application. In this paper, we study the fixed-parameter tractability and intractability of three classical graph problems restricted to multiple-interval graphs. These problems are the k-Independent Set, k-Dominating Set, and k-Clique problems, which are known to W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that the the latter problem is in FPT, while the first two are W[1]-hard. The importance of our results is twofold. First, we determine the parameterized complexity status of three elegantly defined combinatorial problems that have real life applications in various areas. Second, for proving our hardness results, we develop a useful framework for showing W[1]-hardness using a reduction from the k-Multicolored Clique problem, a variant of k-Clique. This problem seems to be very useful in reductions, and we believe that it can be used for showing other W[1]-hardness results.