×

zbMATH — the first resource for mathematics

Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review. (English) Zbl 1425.90039
Summary: Inductive \(k\)-independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard problem of finding maximum-weight induced \(c\)-colorable subgraphs, which is a generalization of finding maximum independent sets, naturally occurs when selecting \(c\) sets of pairwise non-conflicting jobs (modeled as graph vertices). We investigate the parameterized complexity of this problem on inductive \(k\)-independent graphs. We show that the Maximum Independent Set problem is W[1]-hard even on \(2\)-simplicial \(3\)-minoes – a subclass of inductive \(2\)-independent graphs. In contrast, we prove that the more general Max-Weight \(c\)-Colorable Subgraph problem is fixed-parameter tractable on edge-wise unions of cluster and chordal graphs, which are \(2\)-simplicial. In both cases, the parameter is the solution size. Aside from this, we survey other graph classes between inductive \(1\)-independent and inductive \(2\)-independent graphs with applications in scheduling.
MSC:
90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C35 Programming involving graphs or networks
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akcoglu, K., Aspnes, J., DasGupta, B., & Kao, M. Y. (2002). Opportunity-cost algorithms for combinatorial auctions. In Applied optimization 74: Computational methods in decision-making, economics and finance (pp. 455-479). Dordrecht: Kluwer. https://doi.org/10.1007/978-1-4757-3613-7_23 · Zbl 1069.91032
[2] Alon, N.; Yuster, R.; Zwick, U., Color-coding, Journal of the ACM, 42, 844-856, (1995) · Zbl 0885.68116
[3] Arkin, EM; Silverberg, EB, Scheduling jobs with fixed start and end times, Discrete Applied Mathematics, 18, 1-8, (1987) · Zbl 0636.90042
[4] Ásgeirsson, E. I., Halldórsson, M. M., & Tonoyan, T. (2017). Universal framework for wireless scheduling problems. In 44th international colloquium on automata, languages, and programming, ICALP, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (pp 129:1-129:15). https://doi.org/10.4230/LIPIcs.ICALP.2017.129.
[5] Baker, BS; Coffman, EG, Mutual exclusion scheduling, Theoretical Computer Science, 162, 225-243, (1996) · Zbl 0877.68007
[6] Bansal, N.; Blum, A.; Chawla, S., Correlation clustering, Machine Learning, 56, 89-113, (2004) · Zbl 1089.68085
[7] van Bevern, R., Komusiewicz, C., & Sorge, M. (2017). A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments. Networks, 70(3), 262-278. https://doi.org/10.1002/net.21742 (WARP 2 special issue).
[8] Bevern, R.; Mnich, M.; Niedermeier, R.; Weller, M., Interval scheduling and colorful independent sets, Journal of Scheduling, 18, 449-469, (2015) · Zbl 1328.90065
[9] Birand, B.; Chudnovsky, M.; Ries, B.; Seymour, P.; Zussman, G.; Zwols, Y., Analyzing the performance of greedy maximal scheduling via local pooling and graph theory, IEEE/ACM Transactions on Networks, 20, 163-176, (2012)
[10] Blair, J. R. S., & Peyton, B. (1993). An introduction to chordal graphs and clique trees. In Graph theory and sparse matrix computation, IMA volumes in mathematics and its applications (vol. 56, pp 1-29). Berlin: Springer. https://doi.org/10.1007/978-1-4613-8369-7_1. · Zbl 0803.68081
[11] Booth, KS; Lueker, GS, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences, 13, 335-379, (1976) · Zbl 0367.68034
[12] Corneil, DG; Olariu, S.; Stewart, L., The LBFS structure and recognition of interval graphs, SIAM Journal on Discrete Mathematics, 23, 1905-1953, (2009) · Zbl 1207.05131
[13] Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., et al. (2015). Parameterized algorithms. Berlin: Springer. https://doi.org/10.1007/978-3-319-21275-3. · Zbl 1334.90001
[14] Dirac, GA, On rigid circuit graphs, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[15] Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Berlin: Springer. https://doi.org/10.1007/978-1-4471-5559-1. · Zbl 1358.68006
[16] Faenza, Y., Oriolo, G., & Stauffer, G. (2011). An algorithmic decomposition of claw-free graphs leading to an \(O(n^3)\)-algorithm for the weighted stable set problem. In Proceedings of the 22nd ACM-SIAM symposium on discrete algorithms (SODA’11) (pp. 630-646). Philadelphia: SIAM. https://doi.org/10.1137/1.9781611973082.49. · Zbl 1376.05148
[17] Fellows, MR; Hermelin, D.; Rosamond, F.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theoretical Computer Science, 410, 53-61, (2009) · Zbl 1161.68038
[18] Fellows, MR; Jansen, BMP; Rosamond, FA, Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity, European Journal of Combinatorics, 34, 541-566, (2013) · Zbl 1448.68465
[19] Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Berlin: Springer. https://doi.org/10.1007/3-540-29953-X.
[20] Frank, A. (1975). Some polynomial algorithms for certain graphs and hypergraphs. In Proceedings of the 5th British combinatorial conference, congressus numerantium (vol. XV, pp. 211-226).
[21] Gardi, F., Mutual exclusion scheduling with interval graphs or related classes, Part I, Discrete Applied Mathematics, 157, 19-35, (2009) · Zbl 1155.90381
[22] Gaur, D. R., & Krishnamurti, R. (2003). Scheduling intervals using independent sets in claw-free graphs. In Proceedings of the international conference on computational science and its applications (ICCSA 2003) (pp. 254-262). Berlin: Springer. https://doi.org/10.1007/3-540-44839-X_28.
[23] Gyárfás, A.; West, D., Multitrack interval graphs, Congressus Numerantium, 109, 109-116, (1995) · Zbl 0904.05050
[24] Halldórsson, M. M. (2016). Invited paper: Models for wireless algorithms. In Proceedings of the 14th international symposium on modeling and optimization in mobile, ad hoc, and wireless networks (WiOpt’16) (pp. 377-381). New York: IEEE. https://doi.org/10.1109/WIOPT.2016.7492945.
[25] 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 (WG’06), Lecture notes in computer science (vol. 4271, pp. 137-146). Berlin: Springer. https://doi.org/10.1007/11917496_13.
[26] Halldórsson, M. M., & Tonoyan, T. (2015). How well can graphs represent wireless interference? In Proceedings of the 47th annual ACM symposium on theory of computing (STOC’15) (pp. 635-644). New York: ACM. https://doi.org/10.1145/2746539.2746585. · Zbl 1321.68023
[27] Höhn, W.; König, FG; Möhring, RH; Lübbecke, ME, Integrated sequencing and scheduling in coil coating, Management Science, 57, 647-666, (2011) · Zbl 1214.90042
[28] Jamison, RE; Mulder, HM, Tolerance intersection graphs on binary trees with constant tolerance 3, Discrete Mathematics, 215, 115-131, (2000) · Zbl 0947.05055
[29] Jiang, M., On the parameterized complexity of some optimization problems related to multiple-interval graphs, Theoretical Computer Science, 411, 4253-4262, (2010) · Zbl 1213.68461
[30] Jiang, M., Recognizing \(d\)-interval graphs and d-track interval graphs, Algorithmica, 66, 541-563, (2013) · Zbl 1267.68121
[31] Kammer, F., Tholey, T., & Voepel, H. (2010). Approximation algorithms for intersection graphs. In Proceedings of the 13th international workshop on approximation algorithms for combinatorial optimization problems and 14th workshop on randomized techniques in computation: Algorithms and techniques (APPROX’10 and RANDOM’10), Lecture notes in computer science (vol. 6302, pp. 260-273). Berlin: Springer. https://doi.org/10.1007/978-3-642-15369-3_20. · Zbl 1305.68338
[32] Kolen, AWJ; Lenstra, JK; Papadimitriou, CH; Spieksma, FCR, Interval scheduling: A survey, Naval Research Logistics, 54, 530-543, (2007) · Zbl 1143.90337
[33] Komusiewicz, C., & Niedermeier, R. (2012). New races in parameterized algorithmics. In Proceedings of the 37th international symposium on mathematical foundations of computer science (MFCS’12), Lecture notes in computer science (vol. 7464, pp. 19-30). Berlin: Springer. https://doi.org/10.1007/978-3-642-32589-2_2. · Zbl 1365.68286
[34] Köse, A., Evirgen, N., Gökcesu, H., Gökcesu, K., & Médard, M. (2017). Nearly optimal scheduling of wireless ad hoc networks in polynomial time. Available on arXiv:1712.00658.
[35] Köse, A., & Médard, M. (2017). Scheduling wireless ad hoc networks in polynomial time using claw-free conflict graphs. In Proceedings of the 28th IEEE annual international symposium on personal, indoor, and mobile radio communications (PIMRC’17) (pp. 1-7). New York: IEEE. https://doi.org/10.1109/PIMRC.2017.8292404.
[36] Metelsky, Y.; Tyshkevich, R., Line graphs of Helly hypergraphs, SIAM Journal on Discrete Mathematics, 16, 438-448, (2003) · Zbl 1029.05107
[37] Misra, N., Panolan, F., Rai, A., Raman, V., & Saurabh, S. (2013). Parameterized algorithms for max colorable induced subgraph problem on perfect graphs. In Proceedings of the 39th international workshop on graph-theoretic concepts in computer science (WG’13) (pp. 370-381). Berlin: Springer. https://doi.org/10.1007/978-3-642-45043-3_32. · Zbl 1417.05082
[38] Mnich, M.; Bevern, R., Parameterized complexity of machine scheduling: 15 open problems, Computers and Operations Research, 100, 254-261, (2018) · Zbl 06938906
[39] Nakajima, K.; Hakimi, SL, Complexity results for scheduling tasks with discrete starting times, Journal of Algorithms, 3, 344-361, (1982) · Zbl 0535.68017
[40] Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press. https://doi.org/10.1093/acprof:oso/9780198566076.001.0001. · Zbl 1095.68038
[41] Niedermeier, R. (2010). Reflections on multivariate algorithmics and problem parameterization. In Proceedings of the 27th international symposium on theoretical aspects of computer science (STACS’10), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, LIPIcs (vol. 5, pp. 17-32). https://doi.org/10.4230/LIPIcs.STACS.2010.2495. · Zbl 1230.68096
[42] Papadimitriou, C.; Yannakakis, M., Scheduling interval-ordered tasks, SIAM Journal on Computing, 8, 405-409, (1979) · Zbl 0421.68040
[43] Rose, DJ; Tarjan, RE; Lueker, GS, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, 5, 266-283, (1976) · Zbl 0353.65019
[44] Shamir, R.; Sharan, R.; Tsur, D., Cluster graph modification problems, Discrete Applied Mathematics, 144, 173-182, (2004) · Zbl 1068.68107
[45] Sung, SC; Vlach, M., Maximizing weighted number of just-in-time jobs on unrelated parallel machines, Journal of Scheduling, 8, 453-460, (2005) · Zbl 1123.90037
[46] Wegner, G. (1961). Eigenschaften der Nerven homologisch-einfacher Familien im\(R^n\). Ph.D. Thesis, Universität Göttingen.
[47] West, DB; Shmoys, DB, Recognizing graphs with fixed interval number is NP-complete, Discrete Applied Mathematics, 8, 295-305, (1984) · Zbl 0554.68041
[48] Yannakakis, M.; Gavril, F., The maximum \(k\)-colorable subgraph problem for chordal graphs, Information Processing Letters, 24, 133-137, (1987) · Zbl 0653.68070
[49] Ye, Y.; Borodin, A., Elimination graphs, ACM Transactions on Algorithms, 8, 14:1-14:23, (2012) · Zbl 1295.05244
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.