{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:52Z","timestamp":1740109372990,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T00:00:00Z","timestamp":1669161600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T00:00:00Z","timestamp":1669161600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["388221852"],"award-info":[{"award-number":["388221852"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003484","name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003484","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Computing the directed path-width of a directed graph is an NP-hard problem. Even for digraphs of maximum semi-degree 3 the problem remains hard. We propose a decomposition of an input digraph <jats:italic>G<\/jats:italic> = (<jats:italic>V<\/jats:italic>,<jats:italic>A<\/jats:italic>) by a number <jats:italic>k<\/jats:italic> of sequences with entries from <jats:italic>V<\/jats:italic>, such that (<jats:italic>u<\/jats:italic>,<jats:italic>v<\/jats:italic>) \u2208 <jats:italic>A<\/jats:italic> if and only if in one of the sequences there is an occurrence of <jats:italic>u<\/jats:italic> appearing before an occurrence of <jats:italic>v<\/jats:italic>. We present several graph theoretical properties of these digraphs. Among these we give forbidden subdigraphs of digraphs which can be defined by <jats:italic>k<\/jats:italic> =\u20091 sequence, which is a subclass of semicomplete digraphs. Given the decomposition of digraph <jats:italic>G<\/jats:italic>, we show an algorithm which computes the directed path-width of <jats:italic>G<\/jats:italic> in time <jats:inline-formula><jats:alternatives><jats:tex-math>$\\mathcal {O}(k\\cdot (1+N)^{k})$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>O<\/mml:mi>\n                  <mml:mo>(<\/mml:mo>\n                  <mml:mi>k<\/mml:mi>\n                  <mml:mo>\u22c5<\/mml:mo>\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>+<\/mml:mo>\n                      <mml:mi>N<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                  <mml:mo>)<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>N<\/jats:italic> denotes the maximum sequence length. This leads to an XP-algorithm w.r.t. <jats:italic>k<\/jats:italic> for the directed path-width problem. Our result improves the algorithms of Kitsunai et al. for digraphs of large directed path-width which can be decomposed by a small number of sequences and confirm their conjecture that semicompleteness is a useful restriction when considering digraphs.<\/jats:p>","DOI":"10.1007\/s00224-022-10104-w","type":"journal-article","created":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T13:59:35Z","timestamp":1669298375000},"page":"310-347","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Characterizations and Directed Path-Width of Sequence Digraphs"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1212-1796","authenticated-orcid":false,"given":"Frank","family":"Gurski","sequence":"first","affiliation":[]},{"given":"Carolin","family":"Rehs","sequence":"additional","affiliation":[]},{"given":"Jochen","family":"Rethmann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,23]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Gurski, F., Rehs, C., Rethmann, J.: Directed pathwidth of sequence digraphs. In: Proceedings of the international conference on combinatorial optimization and applications (COCOA), vol. 11346 of LNCS, Springer, 2018, pp. 79\u201393 (2018)","key":"10104_CR1","DOI":"10.1007\/978-3-030-04651-4_6"},{"issue":"2","key":"10104_CR2","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1134\/S1990478918020084","volume":"12","author":"S Kitaev","year":"2018","unstructured":"Kitaev, S., Pyatkin, A.: Word-representable graphs: a survey. J. Appl. Industr. Math. 12(2), 278\u2013296 (2018)","journal-title":"J. Appl. Industr. Math."},{"issue":"2016","key":"10104_CR3","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/s00453-015-0015-9","volume":"75","author":"K Kitsunai","year":"2016","unstructured":"Kitsunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., Tano, T.: Computing directed pathwidth in O(1.89n) time. Algorithmica 75(2016), 138\u2013157 (2016)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Nagamochi, H.: Linear layouts in submodular systems. In: Proceedings of the international symposium on algorithms and computation, vol. 7676 of LNCS, Springer, 2012, pp. 475\u2013484 (2012)","key":"10104_CR4","DOI":"10.1007\/978-3-642-35261-4_50"},{"doi-asserted-by":"crossref","unstructured":"Kitsunai, K., Kobayashi, Y., Tamaki, H.: On the pathwidth of almost semicomplete digraphs. In: Proceedings of the annual european symposium on algorithms (ESA), vol. 9294 of LNCS, Springer, 2015, pp. 816\u2013827 (2015)","key":"10104_CR5","DOI":"10.1007\/978-3-662-48350-3_68"},{"issue":"2","key":"10104_CR6","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.ipl.2014.10.002","volume":"115","author":"Y Kobayashi","year":"2015","unstructured":"Kobayashi, Y.: Computing the pathwidth of directed graphs with small vertex cover. Inf. Process. Lett. 115(2), 310\u2013312 (2015)","journal-title":"Inf. Process. Lett."},{"key":"10104_CR7","volume-title":"Digraphs. Theory, Algorithms and Applications","author":"J Bang-Jensen","year":"2009","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs. Theory, Algorithms and Applications. Springer, Berlin (2009)"},{"issue":"1","key":"10104_CR8","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s00186-015-0518-9","volume":"83","author":"F Gurski","year":"2016","unstructured":"Gurski, F., Rethmann, J., Wanke, E.: On the complexity of the FIFO stack-up problem. Math. Methods Oper. Res. 83(1), 33\u201352 (2016)","journal-title":"Math. Methods Oper. Res."},{"key":"10104_CR9","volume-title":"Graph Theory","author":"R Gould","year":"2012","unstructured":"Gould, R.: Graph Theory. Dover Publications Inc, New York (2012)"},{"key":"10104_CR10","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley Publishing Company, Massachusetts (1969)"},{"issue":"2006","key":"10104_CR11","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00373-005-0627-y","volume":"22","author":"J Bar\u00e1t","year":"2006","unstructured":"Bar\u00e1t, J.: Directed pathwidth and monotonicity in digraph searching. Graphs Combinatorics 22(2006), 161\u2013172 (2006)","journal-title":"Graphs Combinatorics"},{"issue":"2001","key":"10104_CR12","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P., Thomas, R.: Directed tree-width. J. Combinatorial Theory Series B 82(2001), 138\u2013155 (2001)","journal-title":"J. Combinatorial Theory Series B"},{"issue":"1983","key":"10104_CR13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P., Graph Minors, I.: Excluding a forest. J. Combinatorial Theory Series B 35(1983), 39\u201361 (1983)","journal-title":"J. Combinatorial Theory Series B"},{"unstructured":"Kashiwabara, T., Fujisawa, T.: NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph. In: Proceedings of the international symposium on circuits and systems, 1979, pp. 657\u2013660 (1979)","key":"10104_CR14"},{"issue":"2","key":"10104_CR15","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algeb. Discrete Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algeb. Discrete Methods"},{"issue":"3","key":"10104_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(93)90012-D","volume":"45","author":"J Gusted","year":"1993","unstructured":"Gusted, J.: On the pathwidth of chordal graphs. Discrete Appl. Math. 45(3), 233\u2013248 (1993)","journal-title":"Discrete Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"Kloks, T., Bodlaender, H., M\u00fcller, H., Kratsch, D.: Computing treewidth and minimum fill-in: all you need are the minimal separators. In: Proceedings of the annual european symposium on algorithms (ESA), vol. 726 of LNCS, Springer, 1993, pp. 260\u2013271 (1993)","key":"10104_CR17","DOI":"10.1007\/3-540-57273-2_61"},{"issue":"1988","key":"10104_CR18","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B Monien","year":"1988","unstructured":"Monien, B., Sudborough, I.: Min cut is NP-complete for edge weighted trees. Theor. Comput. Sci. 58(1988), 209\u2013229 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"10104_CR19","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H Bodlaender","year":"1996","unstructured":"Bodlaender, H.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10104_CR20","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.jctb.2011.05.001","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M., Fradkin, A., Seymour, P.: Tournament immersion and cutwidth. J. Combinatorial Theory Series B 102(1), 93\u2013101 (2012)","journal-title":"J. Combinatorial Theory Series B"},{"issue":"1998","key":"10104_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H Bodlaender","year":"1998","unstructured":"Bodlaender, H.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1998), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"10","key":"10104_CR22","doi-asserted-by":"publisher","first-page":"1822","DOI":"10.1016\/j.dam.2007.08.045","volume":"156","author":"B Yang","year":"2008","unstructured":"Yang, B., Cao, Y.: Digraph searching, directed vertex separation and directed pathwidth. Discrete Appl. Math. 156(10), 1822\u20131837 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"10104_CR23","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/s00224-011-9312-0","volume":"50","author":"H Bodlaender","year":"2012","unstructured":"Bodlaender, H., Fomin, F., Koster, A., Kratsch, D., Thilikos, D.: A note on exact algorithms for vertex ordering problems on graphs. Theory Comput. Syst. 50(3), 420\u2013432 (2012)","journal-title":"Theory Comput. Syst."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10104-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10104-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10104-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,14]],"date-time":"2023-03-14T10:07:31Z","timestamp":1678788451000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10104-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,23]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10104"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10104-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,11,23]]},"assertion":[{"value":"3 October 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}