Classes of intersection digraphs with good algorithmic properties. (English) Zbl 1535.05124
Summary: While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions towards a better understanding of the algorithmic treatment of intersection digraphs. First, we introduce natural classes of intersection digraphs that generalize several classes studied in the literature. Second, we define the directed locally checkable vertex (DLCV) problems, which capture many well-studied problems on digraphs, such as (Independent) Dominating Set, Kernel, and \(H\)-Homomorphism. Third, we give a new width measure of digraphs, bi-mim-width, and show that the DLCV problems are polynomial-time solvable when we are provided a decomposition of small bi-mim-width. Fourth, we show that several classes of intersection digraphs have bounded bi-mim-width, implying that we can solve all DLCV problems on these classes in polynomial time given an intersection representation of the input digraph. We identify reflexivity as a useful condition to obtain intersection digraph classes of bounded bi-mim-width, and therefore to obtain positive algorithmic results.
© 2023 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
© 2023 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C75 | Structural characterization of families of graphs |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Keywords:
directed domination; directed \(H\)-homomorphism; \(H\)-digraphs; intersection digraphs; reflexive digraphsReferences:
| [1] | N.Alon, J.Bang‐Jensen, and S.Bessy, Out‐colourings of digraphs, J. Graph Theory. 93 (2020), no. 1, 88-112. https://doi.org/10.1002/jgt.22476 · Zbl 1495.05080 · doi:10.1002/jgt.22476 |
| [2] | S.Arumugam, K.Jacob, and L.Volkmann, Total and connected domination in digraphs, Australas. J. Combin. 39 (2007), 283-292. http://ajc.maths.uq.edu.au/pdf/39/ajc_v39_p283.pdf · Zbl 1244.05163 |
| [3] | J.Bang‐Jensen and T. M.Christiansen, Degree constrained 2‐partitions of semicomplete digraphs, Theor. Comput. Sci. 746 (2018), 112-123. https://doi.org/10.1016/j.tcs.2018.06.028 · Zbl 1401.05129 · doi:10.1016/j.tcs.2018.06.028 |
| [4] | J.Bang‐Jensen, N.Cohen, and F.Havet, Finding good 2‐partitions of digraphs II. Enumerable properties, Theor. Comput. Sci. 640 (2016), 1-19. https://doi.org/10.1016/j.tcs.2016.05.034 · Zbl 1345.68168 · doi:10.1016/j.tcs.2016.05.034 |
| [5] | J. Bang‐Jensen and G. Gutin (eds.), Classes of directed graphs, Springer Monographs in Mathematics, Springer, Cham, 2018, pp. xxii+636. https://doi.org/10.1007/978-3-319-71840-8 · Zbl 1398.05002 · doi:10.1007/978-3-319-71840-8 |
| [6] | J.Bang‐Jensen, S.Bessy, F.Havet, and A.Yeo, Out‐degree reducing partitions of digraphs, Theor. Comput. Sci. 719 (2018), 64-72. https://doi.org/10.1016/j.tcs.2017.11.007 · Zbl 1390.05184 · doi:10.1016/j.tcs.2017.11.007 |
| [7] | J.Bang‐Jensen, S.Bessy, F.Havet, and A.Yeo, Bipartite spanning sub(di)graphs induced by 2‐partitions, J. Graph Theory. 92 (2019), no. 2, 130-151. https://doi.org/10.1002/jgt.22444 · Zbl 1425.05127 · doi:10.1002/jgt.22444 |
| [8] | D. W.Bange, A. E.Barkauskas, L. H.Host, and L. H.Clark, Efficient domination of the orientations of a graph. Discret Math. 178 (1998), no. 1-3, 1-14. https://doi.org/10.1016/S0012-365X(97)81813-4 · Zbl 0906.05033 · doi:10.1016/S0012-365X(97)81813-4 |
| [9] | L. W.Beineke and C. M.Zamfirescu, Connection digraphs and second‐order line digraphs, Discrete Math. 39 (1982), no. 3, 237-254. https://doi.org/10.1016/0012-365X(82)90147-9 · Zbl 0483.05031 · doi:10.1016/0012-365X(82)90147-9 |
| [10] | R.Belmonte and M.Vatshelle, Graph classes with structured neighborhoods and algorithmic applications, Theor. Comput. Sci. 511 (2013), 54-65. https://doi.org/10.1016/j.tcs.2013.01.011 · Zbl 1408.68109 · doi:10.1016/j.tcs.2013.01.011 |
| [11] | M.Biró, M.Hujter, and Z.Tuza, Precoloring extension. I. Interval graphs, Discret. Math. 100 (1992), no. 1-3, 267-279. https://doi.org/10.1016/0012-365X(92)90646-W · Zbl 0766.05026 · doi:10.1016/0012-365X(92)90646-W |
| [12] | F.Bonomo‐Braberman, N.Brettell, A.Munaro, and D.Paulusma, Solving problems on generalized convex graphs via mim‐width, Proceedings of the 17th International Symposium on Algorithms and Data Structures (WADS 2021), Lecture Notes in Computer Science (A.Lubiw (ed.) and M. R.Salavatipour (ed.), eds.), vol. 12808, Springer, Cham, 2021, pp. 200-214. https://doi.org/10.1007/978-3-030-83508-8_15 · Zbl 07498678 · doi:10.1007/978-3-030-83508-8_15 |
| [13] | A.Brandstädt, V. B.Le, and J. P.Spinrad, Graph classes: A survey, SIAM Monographs on Discrete Mathematics and Applications (P. L.Hammer (ed.), ed.), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999, pp. xii+304. https://doi.org/10.1137/1.9780898719796 · Zbl 0919.05001 · doi:10.1137/1.9780898719796 |
| [14] | B.‐M.Bui‐Xuan, J. A.Telle, and M.Vatshelle, Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems, Theor. Comput. Sci. 511 (2013), 66-76. · Zbl 1408.68111 |
| [15] | D. M.Cardoso, M.Kaminski, and V. V.Lozin, Maximum \(k\)‐regular induced subgraphs, J. Comb. Optim. 14 (2007), no. 4, 455-463. https://doi.org/10.1007/s10878-007-9045-9 · Zbl 1149.90169 · doi:10.1007/s10878-007-9045-9 |
| [16] | M.Cary, J.Cary, and S.Prabhu, Independent domination in directed graphs, Commun. Comb. Optim. 6 (2021), no. 1, 67-80. http://comb-opt.azaruniv.ac.ir/article_14099.html · Zbl 1488.05368 |
| [17] | G.Chartrand, P.Dankelmann, M.Schultz, and H. C.Swart, Twin domination in digraphs, Ars Combin. 67 (2003), 105-114. · Zbl 1079.05064 |
| [18] | B.Courcelle, The monadic second order logic of graphs VI: On several representations of graphs by relational structures, Discret. Appl. Math. 54 (1994), no. 2-3, 117-149. https://doi.org/10.1016/0166-218X(94)90019-1 · Zbl 0809.03005 · doi:10.1016/0166-218X(94)90019-1 |
| [19] | R.Diestel, Graph theory, Graduate Texts in Mathematics (S.Axler (ed.), and K.Ribet (ed.), eds.), 4th edn., vol. 173, Springer, Heidelberg, 2010, pp. xviii+437. https://doi.org/10.1007/978-3-642-14279-6 · Zbl 1204.05001 · doi:10.1007/978-3-642-14279-6 |
| [20] | T.Feder, P.Hell, J.Huang, and A.Rafiey, Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms, Discrete Appl. Math. 160 (2012), no. 6, 697-707. https://doi.org/10.1016/j.dam.2011.04.016 · Zbl 1236.05092 · doi:10.1016/j.dam.2011.04.016 |
| [21] | F. V.Fomin, P. A.Golovach, and J.‐F.Raymond, On the tractability of optimization problems on \(H\)‐graphs, Algorithmica. 82 (2020), no. 9, 2432-2473. https://doi.org/10.1007/s00453-020-00692-9 · Zbl 1447.05142 · doi:10.1007/s00453-020-00692-9 |
| [22] | M. C.Francis, P.Hell, and D.Jacob, On the kernel and related problems in interval digraphs, Algorithmica. 85 (2023), no. 6, 1522-1559. https://doi.org/10.1007/s00453-022-01010-1 · Zbl 07691812 · doi:10.1007/s00453-022-01010-1 |
| [23] | Y.Fu, Dominating set and converse dominating set of a directed graph, Amer. Math. Monthly. 75 (1968), no. 8, 861-863. http://www.jstor.org/stable/2314337 · Zbl 0174.55203 |
| [24] | F.Gavril, A recognition algorithm for the intersection graphs of directed paths in directed trees, Discrete Math. 13 (1975), no. 3, 237-249. https://doi.org/10.1016/0012-365X(75)90021-7 · Zbl 0312.05108 · doi:10.1016/0012-365X(75)90021-7 |
| [25] | J.Ghoshal, R.Laskar, and D.Pillone, Topics on domination in directed graphs, Domination in Graphs: Advanced Topics (T. W.Haynes (ed.), S. T.Hedetniemi (ed.), and P. J.Slater (ed.), eds.), Taylor & Francis, New York, 2017. |
| [26] | P.Hell and J.Nešetřil, Graphs and homomorphisms, Oxford Lecture Series in Mathematics and its Applications (J.Ball (ed.), and D.Welsh (ed.), eds.), vol. 28, Oxford University Press, Oxford, 2004. · Zbl 1062.05139 |
| [27] | S.Høgemo, J. A.Telle, and E. R.Vågset, Linear mim‐width of trees, Graph‐Theoretic Concepts in Computer Science (I.Sau (ed.) and D. M.Thilikos (ed.), eds.), Springer International Publishing, Cham, 2019, pp. 218-231. · Zbl 1536.05436 |
| [28] | L.Jaffke, O.Kwon, T. J. F.Strømme, and J. A.Telle, Mim‐width III. Graph powers and generalized distance domination problems, Theoret. Comput. Sci. 796 (2019), 216-236. https://doi.org/10.1016/j.tcs.2019.09.012 · Zbl 1442.05157 · doi:10.1016/j.tcs.2019.09.012 |
| [29] | T.Johnson, N.Robertson, P. D.Seymour, and R.Thomas, Directed tree‐width, J. Combin. Theory Ser. B. 82 (2001), no. 1, 138-154. https://doi.org/10.1006/jctb.2000.2031 · Zbl 1027.05045 · doi:10.1006/jctb.2000.2031 |
| [30] | D. Y.Kang, O.‐j.Kwon, T. J. F.Strømme, and J. A.Telle, A width parameter useful for chordal and co‐comparability graphs, Theoret. Comput. Sci. 704 (2017), 1-17. https://doi.org/10.1016/j.tcs.2017.09.006 · Zbl 1380.05151 · doi:10.1016/j.tcs.2017.09.006 |
| [31] | M. M.Kanté, The rank‐width of directed graphs, preprint arxiv.org/abs/0709.1433 (2007). |
| [32] | M. M.Kanté and M.Rao, The rank‐width of edge‐coloured graphs, Theory Comput. Syst. 52 (2013), no. 4, 599-644. https://doi.org/10.1007/s00224-012-9399-y · Zbl 1269.05036 · doi:10.1007/s00224-012-9399-y |
| [33] | K.Kawarabayashi and S.Kreutzer, The directed grid theorem, Proceedings of the Forty‐Seventh Annual ACM on Symposium on Theory of Computing (STOC 2015) (R. A.Servedio (ed.) and R.Rubinfeld (ed.), eds.), ACM, New York, 2015, pp. 655-664. https://doi.org/10.1145/2746539.2746586 · Zbl 1321.05249 · doi:10.1145/2746539.2746586 |
| [34] | S.Mengel, Lower bounds on the mim‐width of some graph classes, Discrete Appl. Math. 248 (2018), 28-32. https://doi.org/10.1016/j.dam.2017.04.043 · Zbl 1395.05172 · doi:10.1016/j.dam.2017.04.043 |
| [35] | H.Müller, Recognizing interval digraphs and interval bigraphs in polynomial time, Discrete Appl. Math. 78 (1997), no. 1-3, 189-205. https://doi.org/10.1016/S0166-218X(97)00027-9 · Zbl 0890.68103 · doi:10.1016/S0166-218X(97)00027-9 |
| [36] | L.Ouldrabah, M.Blidia, and A.Bouchou, On the k‐domination number of digraphs, J. Comb. Optim. 38 (2019), no. 3, 680-688. https://doi.org/10.1007/s10878-019-00405-1 · Zbl 1429.05158 · doi:10.1007/s10878-019-00405-1 |
| [37] | S.Oum, Rank‐width and vertex‐minors, J. Combin. Theory Ser. B. 95 (2005), no. 1, 79-100. https://doi.org/10.1016/j.jctb.2005.03.003 · Zbl 1070.05023 · doi:10.1016/j.jctb.2005.03.003 |
| [38] | S.‐i.Oum, Rank‐width is less than or equal to branch‐width, J. Graph Theory. 57 (2008), no. 3, 239-244. https://doi.org/10.1002/jgt.20280 · Zbl 1135.05059 · doi:10.1002/jgt.20280 |
| [39] | E.Prisner, Algorithms for interval catch digraphs, Discret. Appl. Math. 51 (1994), no. 1-2, 147-157. https://doi.org/10.1016/0166-218X(94)90104-X · Zbl 0810.68104 · doi:10.1016/0166-218X(94)90104-X |
| [40] | A.Ramoul and M.Blidia, A new generalization of kernels in digraphs, Discret. Appl. Math. 217 (2017), 673-684. https://doi.org/10.1016/j.dam.2016.09.048 · Zbl 1358.05127 · doi:10.1016/j.dam.2016.09.048 |
| [41] | N.Robertson and P. D.Seymour, Graph minors. x. Obstructions to tree‐decomposition, J. Combin. Theory Ser. B. 52 (1991), no. 2, 153-190. https://doi.org/10.1016/0095-8956(91)90061-N · Zbl 0764.05069 · doi:10.1016/0095-8956(91)90061-N |
| [42] | O.Schaudt, Efficient total domination in digraphs, J. Discrete Algorithms. 15 (2012), 32-42. https://doi.org/10.1016/j.jda.2012.02.003 · Zbl 1247.05094 · doi:10.1016/j.jda.2012.02.003 |
| [43] | M.Sen, S.Das, and D. B.West, Circular‐arc digraphs: A characterization, J. Graph Theory. 13 (1989), no. 5, 581-592. https://doi.org/10.1002/jgt.3190130508 · Zbl 0689.05025 · doi:10.1002/jgt.3190130508 |
| [44] | M.Sen, S.Das, A. B.Roy, and D. B.West, Interval digraphs: An analogue of interval graphs, J. Graph Theory. 13 (1989), no. 2, 189-202. https://doi.org/10.1002/jgt.3190130206 · Zbl 0671.05039 · doi:10.1002/jgt.3190130206 |
| [45] | P.Smolíková, The simple chromatic number of oriented graphs, Electron. Notes Discrete Math. 5 (2000), 281-283. https://doi.org/10.1016/S1571-0653(05)80186-6 · Zbl 1412.05077 · doi:10.1016/S1571-0653(05)80186-6 |
| [46] | É.Sopena, The chromatic number of oriented graphs, J. Graph Theory. 25 (1997), no. 3, 191-205. https://doi.org/10.1002/(SICI)1097-0118(199707)25:3 · Zbl 0874.05026 · doi:10.1002/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G |
| [47] | É.Sopena, Homomorphisms and colourings of oriented graphs: An updated survey. Discret Math. 339 (2016), no. 7, 1993-2005. https://doi.org/10.1016/j.disc.2015.03.018 · Zbl 1334.05046 · doi:10.1016/j.disc.2015.03.018 |
| [48] | J. A.Telle and A.Proskurowski, Algorithms for vertex partitioning problems on partial \(k\)‐trees, SIAM J. Discrete Math. 10 (1997), no. 4, 529-550. https://doi.org/10.1137/S0895480194275825 · Zbl 0885.68118 · doi:10.1137/S0895480194275825 |
| [49] | M.Vatshelle, New width parameters of graphs, Ph.D. thesis, University of Bergen, 2012. |
| [50] | J.vonNeumann, and O.Morgenstern, Theory of games and economic behavior, Princeton University Press, Princeton, NJ, 1944, pp. xviii+625. · Zbl 0063.05930 |
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.
