×

On the parameterized complexity of multiple-interval graph problems. (English) Zbl 1161.68038

Summary: Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are \(k\)-Independent Set, \(k\)-Dominating Set, and \(k\)-Clique, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that \(k\)-Clique is in FPT, while \(k\)-Independent Set and \(k\)-Dominating Set are both W[1]-hard. We also prove that \(k\)-Independent Dominating Set, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the \(k\)-Multicolored Clique problem, a variant of \(k\)-Clique. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI

References:

[1] Alon, N.; Yuster, R.; Zwick, U., Color coding, Journal of the ACM, 42, 4, 844-856 (1995) · Zbl 0885.68116
[2] Y. Aumann, M. Lewenstein, O. Melamud, R.Y. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: Proceedings of the 16th Annual Symposium on Discrete Algorithms, SODA, 2005, pp. 339-348; Y. Aumann, M. Lewenstein, O. Melamud, R.Y. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: Proceedings of the 16th Annual Symposium on Discrete Algorithms, SODA, 2005, pp. 339-348 · Zbl 1297.05166
[3] Bafna, V.; Narayanan, B. O.; Ravi, R., Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles), Discrete Applied Mathematics, 71, 41-53 (1996) · Zbl 0873.92011
[4] R. Bar-Yehuda, M.M. Halldórsson, J. Naor, H. Shachnai, I. Shapira, Scheduling split intervals, in: Proceedings of the 13th Annual ACM/SIAM Symposium on Discrete Algorithms, SODA, 2002, pp. 732-741; R. Bar-Yehuda, M.M. Halldórsson, J. Naor, H. Shachnai, I. Shapira, Scheduling split intervals, in: Proceedings of the 13th Annual ACM/SIAM Symposium on Discrete Algorithms, SODA, 2002, pp. 732-741 · Zbl 1093.68548
[5] R. Bar-Yehuda, D. Rawitz, Using fractional primal-dual to schedule split intervals with demands, in: Proceedings of the 13th Annual European Symposium on Algorithms, 2005, pp. 714-725; R. Bar-Yehuda, D. Rawitz, Using fractional primal-dual to schedule split intervals with demands, in: Proceedings of the 13th Annual European Symposium on Algorithms, 2005, pp. 714-725 · Zbl 1162.90443
[6] Blin, G.; Fertin, G.; Vialette, S., Extracting constrained 2-interval subsets in 2-interval sets, Theoretical Computer Science, 385, 241-263 (2007) · Zbl 1125.68085
[7] A. Butman, D. Hermelin, M. Lewenstein, D Rawitz, Optimization problems in multiple-interval graphs, in: Proceedings of the 18th Annual ACM/SIAM Symposium on Discrete Algorithms, SODA, 2007, pp. 268-278; A. Butman, D. Hermelin, M. Lewenstein, D Rawitz, Optimization problems in multiple-interval graphs, in: Proceedings of the 18th Annual ACM/SIAM Symposium on Discrete Algorithms, SODA, 2007, pp. 268-278 · Zbl 1302.05179
[8] Cai, L.; Chen, J.; Downey, R. G.; Fellows, M. R., On the parameterized complexity of short computation and factorization, Archive for Mathematical Logic, 36, 4-5, 321-337 (1997) · Zbl 0944.68069
[9] L. Cai, D.W. Juedes, Subexponential parameterized algorithms collapse the W-hierarchy, in: Proceedings of the 28th International Colloquium on Automata, Languages and Programming, ICALP, 2001, pp. 273-284; L. Cai, D.W. Juedes, Subexponential parameterized algorithms collapse the W-hierarchy, in: Proceedings of the 28th International Colloquium on Automata, Languages and Programming, ICALP, 2001, pp. 273-284 · Zbl 0986.68038
[10] M. Crochemore, D. Hermelin, G.M. Landau, S. Vialette, Approximating the 2-interval pattern problem, in Proceedings of the 13th Annual European Symposium on Algorithms, ESA, 2005, pp. 426-437; M. Crochemore, D. Hermelin, G.M. Landau, S. Vialette, Approximating the 2-interval pattern problem, in Proceedings of the 13th Annual European Symposium on Algorithms, ESA, 2005, pp. 426-437 · Zbl 1123.68143
[11] Downey, R.; Fellows, M., Parameterized Complexity (1999), Springer-Verlag · Zbl 0961.68533
[12] Downey, R. G.; Fellows, M. R., Fixed-parameter tractability and completeness, Congressus Numerantium, 87, 161-187 (1992) · Zbl 0768.68136
[13] Downey, R. G.; Fellows, M. R., Fixed-parameter tractability and completeness I: Basic results, SIAM Journal on Computing, 24, 873-921 (1995) · Zbl 0830.68063
[14] Downey, R. G.; Fellows, M. R., Fixed-parameter tractability and completeness II: On completeness for W[1], Theoretical Computer Science, 141, 1-2, 109-131 (1995) · Zbl 0873.68059
[15] R.G. Downey, M.R. Fellows, Parameterized computational feasibility, in: Proceedings of Feasible Mathematics II, 1995, pp. 273-284; R.G. Downey, M.R. Fellows, Parameterized computational feasibility, in: Proceedings of Feasible Mathematics II, 1995, pp. 273-284 · Zbl 0834.68046
[16] Farber, M., Domination, independent domination, and duality in strongly chordal graphs, Discrete Applied Mathematics, 7, 115-130 (1984) · Zbl 0531.05045
[17] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[18] Gaur, D. R.; Ibaraki, T.; Krishnamurti, R., Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem, Journal of Algorithms, 43, 138-152 (2002) · Zbl 1005.68179
[19] Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph, SIAM Journal on Computing, 1, 180-187 (1972) · Zbl 0227.05116
[20] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[21] Griggs, J. R., Extremal values of the interval number of a graph, II, Discrete Mathematics, 28, 37-47 (1979) · Zbl 0454.05039
[22] Griggs, J. R.; West, D. B., Extremal values of the interval number of a graph, SIAM Journal on Algebraic and Discrete Methods, 1, 1, 1-14 (1980) · Zbl 0499.05033
[23] Gyráfás, A.; West, D., Multitrack interval graphs, Congressus Numerantium, 109, 109-116 (1995) · Zbl 0904.05050
[24] Hassin, R.; Megiddo, N., Approximation algorithms for hitting objects with straight lines, Discrete Applied Mathematics, 30, 1, 29-42 (1991) · Zbl 0800.68619
[25] R. Hassin, D. Segev, Rounding to an integral program, in: 4th International Workshop on Efficient and Experimental Algorithms, 2005, pp. 44-54; R. Hassin, D. Segev, Rounding to an integral program, in: 4th International Workshop on Efficient and Experimental Algorithms, 2005, pp. 44-54 · Zbl 1121.68345
[26] Hassin, R.; Tamir, A., Improved complexity bounds for location problems on the real line, Operations Research Letters, 10, 7, 395-402 (1991) · Zbl 0742.90050
[27] Hochbaum, D. S.; Levin, A., Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms, Discrete Optimization, 3, 4, 327-340 (2006) · Zbl 1112.90023
[28] D. Marx, Efficient approximation schemes for geometric problems? in: Proceedings of the 13th Annual European Symposium on Algorithms, ESA, 2005, pp. 448-459; D. Marx, Efficient approximation schemes for geometric problems? in: Proceedings of the 13th Annual European Symposium on Algorithms, ESA, 2005, pp. 448-459 · Zbl 1162.68822
[29] D. Marx, Parameterized complexity of independence and domination on geometric graphs, in: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, IWPEC, 2006, pp. 154-165; D. Marx, Parameterized complexity of independence and domination on geometric graphs, in: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, IWPEC, 2006, pp. 154-165 · Zbl 1154.68431
[30] Scheinerman, E. R.; West, D. B., The interval number of a planar graph: Three intervals suffice, Journal of Combinatorial Theory B, 35, 224-239 (1983) · Zbl 0528.05053
[31] Vialette, S., On the computational complexity of 2-interval pattern matching problems, Theoretical Computer Science, 312, 335-379 (2004)
[32] West, D. B.; Shmoys, D. B., Recognizing graphs with fixed interval number is NP-complete, Discrete Applied Mathematics, 8, 295-305 (1984) · Zbl 0554.68041
[33] J. Zhao, R.L. Malmberg, L. Cai, Rapid ab initio rna folding including pseudoknots via graph tree decomposition, in: Proceedings of the 6th Workshop on Algorithms in BioInformatics, WABI, 2006, pp. 262-273; J. Zhao, R.L. Malmberg, L. Cai, Rapid ab initio rna folding including pseudoknots via graph tree decomposition, in: Proceedings of the 6th Workshop on Algorithms in BioInformatics, WABI, 2006, pp. 262-273
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.