DAG-width and circumference of digraphs. (English) Zbl 1339.05156
Summary: We prove that every digraph of circumference \(l\) has DAG-width at most \(l\). This is best possible and solves a recent conjecture from S. Kintali [“Directed width parameters and circumference of digraphs”, Preprint, arXiv:1401.2662]. As a consequence of this result we deduce that the \(k\)-linkage problem is polynomially solvable for every fixed \(k\) in the class of digraphs with bounded circumference. This answers a question posed in [J. Bang-Jensen et al., Theor. Comput. Sci. 562, 283–303 (2015; Zbl 1303.68064)]. We also prove that the weak \(k\)-linkage problem (where we ask for arc-disjoint paths) is polynomially solvable for every fixed \(k\) in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP-hard on digraphs of DAG-width at most 5.
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C12 | Distance in graphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
DAG-width; \(k\)-linkage problem; bounded cycle length; polynomial algorithm; cops-and-robbers gameCitations:
Zbl 1303.68064References:
| [1] | J.Bang‐Jensen and G.Gutin, Digraphs: Theory, Algorithms and Applications, 2nd edn., Springer‐Verlag, London, 2009. · Zbl 1170.05002 |
| [2] | J.Bang‐Jensen, F.Havet, and A. K.Maia, Finding a subdivision of a digraph, Theor Comput Sci562 (2014), 283-303. · Zbl 1303.68064 |
| [3] | J.Bang‐Jensen and C.Thomassen, A polynomial algorithm for the 2‐path problem for semicomplete digraphs, SIAM J Disc Math5 (1992), 366-376. · Zbl 0759.05041 |
| [4] | D.Berwanger, A.Dawar, P.Hunter, S.Kreutzer, and J.Obdržálek, The DAG‐width of directed graphs, J Combin Theory Ser B102 (2012), 900-923. · Zbl 1246.05065 |
| [5] | E.Birmelé, Tree‐width and circumference of graphs, J Graph Theory43 (2003), 24-25. · Zbl 1017.05036 |
| [6] | M.Chudnovsky, A.Scott, amd P.Seymour, Disjoint paths in tournaments, Adv Math270 (2015), 582-597. · Zbl 1304.05057 |
| [7] | S.Fortune, J. E.Hopcroft, and J.Wyllie, The directed subgraph homeomorphism problem, Theor Comput Sci10 (1980), 111-121. · Zbl 0419.05028 |
| [8] | R.Ganian, P.Hliněný, J.Kneis, A.Langer, J.Obdržálek, and P.Rossmanith, Digraph width measures in parametrized algorithmics, in: J.Chen (ed.), F.Fomin (ed.) (Eds.), IWPEC 2009, Lecture Notes in Computer Science, vol. 5917, Springer Verlag, Copenhagen, Denmark, 2010, pp. 185-197. · Zbl 1273.68276 |
| [9] | R.Ganian, P.Hliněný, J.Kneis, D.Meister, J.Obdržálek, J. P.Rossmanith, and S.Sikdar, Are there any good digraph width measures? in: V.Raman (ed.), S.Saurabh (ed.) (Eds.), IPEC 2010, Lecture Notes in Computer Science, vol. 6478, Springer Verlag, Chennai, India, 2010, pp. 135-146. · Zbl 1309.68150 |
| [10] | F.Havet and A. K.Maia, On disjoint directed cycles with prescribed minimum lengths, Research report no. 8286, INRIA, Sophia Antipolis, Project‐team COATI (2013), Springer Verlag, Chennai, India. |
| [11] | P.Hunter and P.Kreutzer, Digraph measures: Kelly decompositions, games and orderings, Theor Comput Sci399 (2008), 206-219. · Zbl 1152.91015 |
| [12] | T.Johnson, N.Robertson, P. D.Seymour, and R.Thomas, Directed tree‐width, J Combin Theory Ser B82 (2001), 138-154. · Zbl 1027.05045 |
| [13] | S.Khuller, B.Raghavachari, and N.Young, On strongly connected digraphs of bounded cycle length, Disc Appl Math69 (1996), 281-289. · Zbl 0859.05057 |
| [14] | S.Kintali, Directed width parameters and circumference of digraphs. ArXiv:1401.2662v1 [math.CO], January 2014. |
| [15] | T.M.Larsen, The (weak) k‐linkage problem in directed graphs of bounded cycle length. Student project, IMADA, University of Southern Denmark, January 7, 2013. |
| [16] | J.Obdržálek, DAG‐width: Connectivity measure for directed graphs, SODA’06: Proceedings of the 17th Annual ACM‐SIAM Symposium on Discrete Algorithm, ACM, New York, 2006, pp. 814-821. · Zbl 1192.05065 |
| [17] | N.Robertson and P. D.Seymour, Graph minors XIII: The disjoint paths problem, J Combin Theory Ser B63 (1995), 65-110. · Zbl 0823.05038 |
| [18] | P. D.Seymour and R.Thomas, Graph searching and a min‐max theorem for tree‐width, J Combin Theory Ser B58 (1993), 22-33. · Zbl 0795.05110 |
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.
