×

Interval scheduling and colorful independent sets. (English) Zbl 1328.90065

Summary: Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer \(k\), find a set of at least \(k\) pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains NP-hard but admits constant ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural “compactness” parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are as follows: 1. We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is NP-hard otherwise. 2. We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization). 3. We extend M. M. Halldórsson and R. K. Karlsson’s fixed-parameter algorithm [Lecture Notes in Computer Science 4271, 137–146 (2006; Zbl 1167.68409)] for Independent Set on strip graphs parameterized by the structural parameter “maximum number of live jobs” to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter \(k\) and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to 15 jobs and \(5\cdot 10^5\) intervals can be solved optimally in less than \(5\) min.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
05C15 Coloring of graphs and hypergraphs
90C35 Programming involving graphs or networks
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 1167.68409
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., Yuster, R., & Zwick, U. (1995). Color-coding. Journal of the ACM, 42(4), 844-856. · Zbl 0885.68116 · doi:10.1145/210332.210337
[2] Bafna, V., Narayanan, B. O., & Ravi, R. (1996). Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Applied Mathematics, 71(1-3), 41-53. · Zbl 0873.92011 · doi:10.1016/S0166-218X(96)00063-7
[3] Bar-Yehuda, R., Halldórsson, M. M., Naor, J., Shachnai, H., & Shapira, I. (2006). Scheduling split intervals. SIAM Journal on Computing, 36(1), 1-15. · Zbl 1111.68046 · doi:10.1137/S0097539703437843
[4] Bodlaender, H. L., Jansen, B. M. P., & Kratsch, S. (2014). Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics, 28(1), 277-305. · Zbl 1295.05222 · doi:10.1137/120880240
[5] Brandstädt, A., Le, V. B., & Spinrad, J. P. (1999). Graph classes: A survey. Philadelphia: SIAM. · Zbl 0919.05001 · doi:10.1137/1.9780898719796
[6] Chen, J., Lu, S., Sze, S. H., Zhang, F. (2007). Improved algorithms for path, matching, and packing problems. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 298-307). New York: SIAM. · Zbl 1302.90169
[7] Chuzhoy, J., Ostrovsky, R., & Rabani, Y. (2006). Approximation algorithms for the job interval selection problem and related scheduling problems. Mathematics of Operations Research, 31(4), 730-738. · Zbl 1278.90146 · doi:10.1287/moor.1060.0218
[8] Corneil, D. G., Olariu, S., & Stewart, L. (2009). The LBFS structure and recognition of interval graphs. SIAM Journal on Discrete Mathematics, 23(4), 1905-1953. · Zbl 1207.05131 · doi:10.1137/S0895480100373455
[9] Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. New York: Springer. · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1
[10] Fellows, M. R., Gaspers, S., & Rosamond, F. A. (2012). Parameterizing by the number of numbers. Theory of Computing Systems, 50(4), 675-693. · Zbl 1253.68173 · doi:10.1007/s00224-011-9367-y
[11] Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Berlin: Springer. · Zbl 1143.68016
[12] Fulkerson, D. R., & Gross, O. A. (1965). Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15(3), 835-855. · Zbl 0132.21001 · doi:10.2140/pjm.1965.15.835
[13] Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237-267. · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[14] Guo, J., & Niedermeier, R. (2007). Invitation to data reduction and problem kernelization. SIGACT News, 38(1), 31-45. · doi:10.1145/1233481.1233493
[15] Gyárfas, A., & West, D. B. (1995). Multitrack interval graphs. Congressus Numerantium, 109, 109-116. · Zbl 0904.05050
[16] Halldórsson, M. M., Karlsson, R. K. (2006). Strip graphs: Recognition and scheduling. In: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science (Vol. 4271, pp. 137-146). Berlin: Springer. · Zbl 1167.68409
[17] Höhn, W., König, F. G., Möhring, R. H., & Lübbecke, M. E. (2011). Integrated sequencing and scheduling in coil coating. Management Science, 57(4), 647-666. · Zbl 1214.90042 · doi:10.1287/mnsc.1100.1302
[18] Impagliazzo, R., Paturi, R., & Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4), 512-530. · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774
[19] Jiang, M. (2010). On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theoretical Computer Science, 411, 4253-4262. · Zbl 1213.68461 · doi:10.1016/j.tcs.2010.09.001
[20] Jiang, M. (2013). Recognizing d-interval graphs and d-track interval graphs. Algorithmica, 66(3), 541-563. · Zbl 1267.68121 · doi:10.1007/s00453-012-9651-5
[21] Kolen, A. W., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. R. (2007). Interval scheduling: A survey. Naval Research Logistics, 54(5), 530-543. · Zbl 1143.90337 · doi:10.1002/nav.20231
[22] Koutis, I., Williams, R. (2009). Limits and applications of group algebras for parameterized problems. In: Proceedings of the 36th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science (Vol. 5555, pp. 653-664). New York: Springer. · Zbl 1248.68251
[23] Kratsch, S. (2014). Recent developments in kernelization: A survey. Bulletin of the European Association for Theoretical Computer Science, 113, 58-97. · Zbl 1409.68144
[24] Kung, H. T., Luccio, F., & Preparata, F. P. (1975). On finding the maxima of a set of vectors. Journal of the ACM, 22(4), 469-476. · Zbl 0316.68030 · doi:10.1145/321906.321910
[25] Lokshtanov, D., Marx, D., & Saurabh, S. (2011). Lower bounds based on the exponential time hypothesis. Bulletin of the European Association for Theoretical Computer Science, 105, 41-72. · Zbl 1258.68068
[26] Marx, D. (2011). Fixed-parameter tractable scheduling problems. In: Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091). · Zbl 1278.90146
[27] Mnich, M., Wiese, A. (2014). Scheduling and fixed-parameter tractability. In: Proceedings of the 17th Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science (Vol. 8494, pp. 381-392). Berlin: Springer. · Zbl 1332.68088
[28] Möhring, R. H. (2011). Algorithm engineering and industrial applications. Information Technology, 53(6), 302-311. · doi:10.1524/itit.2011.0657
[29] Nakajima, K., & Hakimi, S. L. (1982). Complexity results for scheduling tasks with discrete starting times. Journal of Algorithms, 3(4), 344-361. · Zbl 0535.68017 · doi:10.1016/0196-6774(82)90030-X
[30] Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press. · Zbl 1095.68038
[31] Scheinerman, E. (1988). Random interval graphs. Combinatorica, 8(4), 357-371. · Zbl 0659.05078 · doi:10.1007/BF02189092
[32] Schrijver, A. (2003). Combinatorial optimization: Polyhedra and efficiency (Vol. A). Berlin: Springer. · Zbl 1041.90001
[33] Spieksma, F. C. R. (1999). On the approximability of an interval scheduling problem. Journal of Scheduling, 2(5), 215-227. · Zbl 0938.90034 · doi:10.1002/(SICI)1099-1425(199909/10)2:5<215::AID-JOS27>3.0.CO;2-Y
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.