nach oben

Theory of Computing Systems

Erschienen in:

22.04.2019

Comparing Linear Width Parameters for Directed Graphs

verfasst von: Frank Gurski, Carolin Rehs

Erschienen in: Theory of Computing Systems | Ausgabe 6/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we introduce the linear clique-width, linear NLC-width, neighbourhood-width, and linear rank-width for directed graphs. We compare these parameters with each other as well as with the previously defined parameters directed path-width and directed cut-width. It turns out that the parameters directed linear clique-width, directed linear NLC-width, directed neighbourhood-width, and directed linear rank-width are equivalent in that sense, that all of these parameters can be upper bounded by each of the others. For the restriction to digraphs of bounded vertex degree directed path-width and directed cut-width are equivalent. Further for the restriction to semicomplete digraphs of bounded vertex degree all six mentioned width parameters are equivalent. We also show close relations of the measures to their undirected versions of the underlying undirected graphs, which allow us to show the hardness of computing the considered linear width parameters for directed graphs. Further we give first characterizations for directed graphs defined by parameters of small width.

Vorheriger Artikel Bounds on the Bend Number of Split and Cocomparability Graphs

Nächster Artikel Weak Completeness Notions for Exponential Time

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Thus we do not consider directed graphs with loops.

Please note that there are some works which define the path-width of a digraph G in a different and not equivalent way by using the path-width of und(G), see Section 7.

Please note that condition (3) in Definition 3 is the only difference to the undirected path-width [57], where i = j has to be fulfilled.

We use the complete biorientations of the two forbidden minors for the set of all graphs of vertex separation number 1, see [48, Fig. 1].

The abbreviation NLC results from the node label controlled embedding mechanism originally defined for graph grammars.

We denote by rg⁽⁴⁾(M) the rank of some matrix over

https://static-content.springer.com/image/art%3A10.1007%2Fs00224-019-09919-x/MediaObjects/224_2019_9919_Figm_HTML.gif

, i.e. the number of independent lines or rows of M. A set of rows R (i.e. vectors) are independent, if there is no linear combination of a subset R^′ of R to define a row in R − R^′. A linear combination for some n-tuple r is \({\sum }_{i = 1}^{n} a_{i}r_{i}\) for a_i ∈

https://static-content.springer.com/image/art%3A10.1007%2Fs00224-019-09919-x/MediaObjects/224_2019_9919_Fign_HTML.gif

Please note that two parameters are equivalent, if and only if the same families of digraphs have bounded width for them.

Please note that in [24] a different notation for directed path-width was used. In Definition 3(2) the arcs are directed from bags X_i to X_j for i ≤ j. The authors of [24] take arcs from bags X_i to X_j for i ≥ j into account. Since an optimal directed path-decomposition (X₁,…,X_r) w.r.t. Definition 3 leads to an optimal directed path-decomposition (X_r,…,X₁) w.r.t. the definition of [24], and vice versa, both definitions lead to the same value for the directed path-width.

When considering the directed path-width of almost semicomplete digraphs in [50] the class of semicomplete digraphs was suggested to be “a promising stage for pursuing digraph analogues of the splendid outcomes, direct and indirect, from the Graph Minors project”.

Adolphson, D., Hu, T.C.: Optimal linear ordering. SIAM J. Appl. Math. 25(3), 403–423 (1973)MathSciNetCrossRefMATH

Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability – a survey. BIT 25, 2–23 (1985)MathSciNetCrossRefMATH

Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discret. Methods 8(2), 277–284 (1987)MathSciNetCrossRefMATH

Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discret. Appl. Math. 23, 11–24 (1989)MathSciNetCrossRefMATH

Bang-Jensen, J., Gutin, G.: Digraphs. Theory Algorithms and Applications. Springer, Berlin (2009)MATH

Bang-Jensen, J., Gutin, G. (eds.): Classes of Directed Graphs. Springer, Berlin (2018)MATH

Barát, J.: Directed pathwidth and monotonicity in digraph searching. Graphs Comb. 22, 161–172 (2006)CrossRefMATH

Bechet, D., de Groote, P., Retoré, C.: A complete axiomatisation of the inclusion of series-parallel partial orders. In: Rewriting Techniques and Applications, vol. 1232 of LNCS, pp. 230–240. Springer (1997)

Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1–45 (1998)MathSciNetCrossRefMATH

10.

Boeckner, D.: Oriented threshold graphs. Australas. J. Combin. 71(1), 43–53 (2018)MathSciNetMATH

11.

Brandstädt, A., Dragan, F.F., Le, H.-O., Mosca, R.: New graph classes of bounded clique width. Theory Comput. Syst. 38(5), 623–645 (2005)MathSciNetCrossRefMATH

12.

Chudnovsky, M., Fradkin, A.O., Seymour, P.D.: Tournament immersion and cutwidth. J. Comb. Theory, Ser. B 102(1), 93–101 (2012)MathSciNetCrossRefMATH

13.

Chvátal, V., Hammer, P.L.: Aggregation of inequalities in integer programming. Ann. Discret. Math. 1, 145–162 (1977)MathSciNetCrossRefMATH

14.

Courcelle, B.: From tree-decompositions to clique-width terms. Discret. Appl. Math. 248, 125–144 (2018)MathSciNetCrossRefMATH

15.

Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. A Language-Theoretic Approach. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (2012)MATH

16.

Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)MathSciNetCrossRefMATH

17.

Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101, 77–114 (2000)MathSciNetCrossRefMATH

18.

Crespelle, C., Paul, C.: Fully dynamic recognition algorithm and certificate for directed cographs. Discret. Appl. Math. 154(12), 1722–1741 (2006)MathSciNetCrossRefMATH

19.

Dehmer, M., Emmert-Streib, F. (eds.): Quantitative Graph Theory: Mathematical Foundations and Applications. Crc Pr Inc., New York (2014)MATH

20.

Espelage, W., Gurski, F., solve, E. Wanke.: How to NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Proceedings of Graph-Theoretical Concepts in Computer Science (WG), volume 2204 of LNCS, pp. 117–128. Springer (2001)

21.

Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discret. Math. 23(2), 909–939 (2009)MathSciNetCrossRefMATH

22.

Fomin, F.V., Golovach, P., Lokshtanov, D., Saurabh, S., Zehavi, M.: Cliquewidth III: The odd case of graph coloring parameterized by cliquewidth. ACM Trans. Algorithms 15(1), 9:1–9:27 (2018)CrossRefMATH

23.

Fomin, F.V., Oum, S., Thilikos, D.: Rank-width and tree-width of H-minor-free graphs. Eur. J. Comb. 31(7), 1617–1628 (2010)MathSciNetCrossRefMATH

24.

Fomin, F.V., Pilipczuk, M.: Jungles, bundles, and fixed parameter tractability. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 396–413. ACM-SIAM (2013)

25.

Fomin, F.V., Pilipczuk, M.: Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. In: Proceedings of the Annual European Symposium on Algorithms (ESA), vol. 8125 of LNCS, pp. 505–516. Springer (2013)

26.

Ganian, R.: Thread graphs, linear rank-width and their algorithmic applications. In: Proceedings of International Workshop on Combinatorial Algorithms, vol. 6460 of LNCS, pp. 38–42. Springer (2011)

27.

Ganian, R., Hlinený, P., Kneis, J., Langer, A., Obdrzálek, J., Rossmanith, P.: Digraph width measures in parameterized algorithmics. Discret. Appl. Math. 168, 88–107 (2014)MathSciNetCrossRefMATH

28.

Ganian, R., Hlinený, P., Kneis, J., Meisters, D., Obdrzálek, J., Rossmanith, P., Sikdar, S.: Are there any good digraph width measures?. J. Comb. Theory Ser. B 116, 250–286 (2016)MathSciNetCrossRefMATH

29.

Gavril, F.: Some NP-complete problems on graphs. In: Proceedings of the 11th Conference on Information Sciences and Systems, pp. 91–95. Johns Hopkins University, Baltimore (1977)

30.

Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423–443 (2000)MathSciNetCrossRefMATH

31.

Gurski, F.: Characterizations for co-graphs defined by restricted NLC-width or clique-width operations. Discret. Math. 306(2), 271–277 (2006)MathSciNetCrossRefMATH

32.

Gurski, F.: Linear layouts measuring neighbourhoods in graphs. Discret. Math. 306(15), 1637–1650 (2006)MathSciNetCrossRefMATH

33.

Gurski, F.: Graph parameters measuring neighbourhoods in graphs – bounds and applications. Discret. Appl. Math. 156(10), 1865–1874 (2008)MathSciNetCrossRefMATH

34.

Gurski, F., Rehs, C.: Directed path-width and directed tree-width of directed co-graphs. In: Proceedings of the International Conference on Computing and Combinatorics (COCOON), vol. 10976 of LNCS, pp .255–267. Springer (2018)

35.

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, pp. 79–93. Springer (2018)

36.

Gurski, F., Wanke, E.: The tree-width of clique-width bounded graphs without K _{n, n}. In: Proceedings of Graph-Theoretical Concepts in Computer Science (WG), vol. 1938 of LNCS, pp. 196–205. Springer (2000)

37.

Gurski, F., Wanke, E.: On the relationship between NLC-width and linear NLC-width. Theor. Comput. Sci. 347(1-2), 76–89 (2005)MathSciNetCrossRefMATH

38.

Gurski, F., Wanke, E.: Vertex disjoint paths on clique-width bounded graphs. Theor. Comput. Sci. 359(1-3), 188–199 (2006)MathSciNetCrossRefMATH

39.

Gurski, F., Wanke, E., Yilmaz, E.: Directed NLC-width. Theor. Comput. Sci. 616, 1–17 (2016)MathSciNetCrossRefMATH

40.

Hagerup, T.: Dynamic algorithms for graphs of bounded treewidth. Algorithmica 27(3), 292–315 (2000)MathSciNetCrossRefMATH

41.

Heggernes, P., Meister, D., Papadopoulos, C.: A complete characterisation of the linear clique-width of path powers. In: Proceedings of the Annual Conference on Theory and Applications of Models of Computation, vol. 5532 of LNCS, pp. 241–250. Springer (2009)

42.

Heggernes, P., Meister, D., Papadopoulos, C.: Graphs of linear clique-width at most 3. Theor. Comput. Sci. 412(39), 5466–5486 (2011)MathSciNetCrossRefMATH

43.

Hlinený, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326–362 (2008)CrossRef

44.

Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory, Ser. B 82, 138–155 (2001)MathSciNetCrossRefMATH

45.

Kanté, M., Rao, M.: The rank-width of edge-coloured graphs. Theory Comput. Syst. 52(4), 599–644 (2013)MathSciNetCrossRefMATH

46.

Kashem, M.A., Zhou, X., Nishizeki, T.: Algorithms for generalized vertex-rankings of partial k-trees. Theor. Comput. Sci. 240(2), 407–427 (2000)MathSciNetCrossRefMATH

47.

Kashyap, N.: Matroid pathwidth and code trellis complexity. SIAM J. Discret. Math. 22(1), 256–272 (2008)MathSciNetCrossRefMATH

48.

Kinnersley, N.G., Langston, M.A.: Obstruction set isolation for the gate matrix layout problem. Discret. Appl. Math. 54, 169–213 (1994)MathSciNetCrossRefMATH

49.

Kitsunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., Tano, T.: Computing directed pathwidth in O(1.89ⁿ) time. Algorithmica 75, 138–157 (2016)MathSciNetCrossRefMATH

50.

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, pp. 816–827. Springer (2015)

51.

Kobayashi, Y.: Computing the pathwidth of directed graphs with small vertex cover. Inf. Process. Lett. 115(2), 310–312 (2015)MathSciNetCrossRefMATH

52.

Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)MathSciNetCrossRefMATH

53.

Nagamochi, H.: Linear layouts in submodular systems. In: Proceedings of the International Symposium on Algorithms and Computation, vol. 7676 of LNCS, pp. 475–484. Springer (2012)

54.

Oum, S.: Rank-width and vertex-minor. J. Comb. Theory, Ser. B 95, 79–100 (2005)MathSciNetCrossRefMATH

55.

Oum, S.: Rank-width: algorithmic and structural results. Discret. Appl. Math. 231, 15–24 (2017)MathSciNetCrossRefMATH

56.

Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Comb. Theory, Ser. B 96(4), 514–528 (2006)MathSciNetCrossRefMATH

57.

Robertson, N., Seymour, P.D.: Graph minors I. Excluding a forest. J. Comb. Theory, Ser. B 35, 39–61 (1983)MathSciNetCrossRefMATH

58.

Robertson, N., Seymour, P.D.: Graph minors II. Algorithmic aspects of tree width. J. Algorithm. 7, 309–322 (1986)MathSciNetCrossRefMATH

59.

Tamaki, H.: A Polynomial Time Algorithm for Bounded Directed Pathwidth. In: Proceedings of Graph-Theoretical Concepts in Computer Science (WG), vol. 6986 of LNCS, pp. 331–342. Springer (2011)

60.

Wanke, E.: k-NLC graphs and polynomial algorithms. Discret. Appl. Math. 54, 251–266 (1994)MathSciNetCrossRefMATH

61.

Yang, B., Cao, Y.: Digraph searching, directed vertex separation and directed pathwidth. Discret. Appl. Math. 156(10), 1822–1837 (2008)MathSciNetCrossRefMATH

Titel: Comparing Linear Width Parameters for Directed Graphs
verfasst von: Frank Gurski
Carolin Rehs
Publikationsdatum: 22.04.2019
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 6/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-019-09919-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 6/2019

Weak Completeness Notions for Exponential Time

On the Relative Succinctness of Sentential Decision Diagrams

On Stackelberg Strategies in Affine Congestion Games

The Number of Clones Determined by Disjunctions of Unary Relations

Bounds on the Bend Number of Split and Cocomparability Graphs

Strategic Network Formation Through an Intermediary