DOI: https://doi.org/10.14710/jfma.v8i1.24222

BOUNDING LINEAR-WIDTH AND DISTANCE-WIDTH USING FEEDBACK VERTEX SET AND MM-WIDTH FOR GRAPH

*Takaaki Fujita  -  Gunma University, Japan

Citation Format:
Abstract

Studying the upper and lower bounds of graph parameters is crucial for understanding the complexity and tractability of computational problems, optimizing algorithms, and revealing structural properties of various graph classes. In this brief paper, we explore the upper and lower bounds of graph parameters, including path-distance-width, MM-Width, Feedback Vertex Set, and linear-width. These bounds are crucial for understanding the complexity and structure of graphs.

Fulltext View|Download
Keywords: Path-distance-width; Linear-width; Maximum-matching-width; Feedback Vertex Set

Article Metrics:

Article Info
Section: FUNDAMENTAL MATHEMATICS AND APPLICATIONS
Language : EN
Recent articles
COORDINATING AND OPTIMIZING TWO-WAREHOUSE INVENTORY SYSTEMS: A MATHEMATICAL PROGRAMMING APPROACH Construction of the Rough Quotient Modules over the Rough Ring by Using Coset Concepts EPIDEMIC ANALYSIS, MATHEMATICAL MODELLING AND NUMERICAL SIMULATION OF COVID-19 TRANSMISSION More recent articles
  1. Vikraman Arvind, Bireswar Das, Johannes Köbler, and Sebastian Kuhnert. The isomorphism problem for k-trees is complete for logspace. Information and Computation, 217:1–11, 2012
  2. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics, 12(3):289–297, 1999
  3. Daniel Bienstock. Graph searching, path-width, tree-width and related problems (a survey). Reliability of computer and communication networks, 5:33–50, 1989
  4. Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. On the parameterized complexity of computing tree-partitions. arXiv preprint arXiv:2206.11832, 2022
  5. Hans L Bodlaender and Arie MCA Koster. Treewidth computations I. Upper bounds. Information and Computation, 208(3):259–275, 2010
  6. Hans L Bodlaender and Arie MCA Koster. Treewidth computations II. Lower bounds. Information and Computation, 209(7):1103–1119, 2011
  7. Édouard Bonnet. Treewidth inapproximability and tight ETH lower bound. arXiv preprint arXiv:2406.11628, 2024
  8. Jannis Bulian and Anuj Dawar. Graph isomorphism parameterized by elimination distance to bounded degree. Algorithmica, 75(2):363–382, 2016
  9. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set: New measure and new structures. Algorithmica, 73:63–86, 2015
  10. Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 177–186, 2008
  11. François Clautiaux, Jacques Carlier, Aziz Moukrim, and Stéphane Nègre. New lower and upper bounds for graph treewidth. In Experimental and Efficient Algorithms: Second International Workshop, WEA 2003, Ascona, Switzerland, May 26–28, 2003 Proceedings 2, pages 70–80. Springer, 2003
  12. Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted space algorithms for isomorphism on bounded treewidth graphs. Information and Computation, 217:71–83, 2012
  13. Reinhard Diestel. Tangles in the social sciences. arXiv preprint arXiv:1907.07341, 2019
  14. Guoli Ding and Bogdan Oporowski. On tree-partitions of graphs. Discrete Mathematics, 149(1–3):45–58, 1996
  15. Gal Elidan and Stephen Gould. Learning bounded treewidth Bayesian networks. Advances in Neural Information Processing Systems, 21, 2008
  16. Fedor V Fomin and Dimitrios M Thilikos. On the monotonicity of games generated by symmetric submodular functions. Discrete Applied Mathematics, 131(2):323–335, 2003
  17. Takaaki Fujita. Relation between ultra matroid and linear decomposition. Italian Journal of Pure and Applied Mathematics. Accepted
  18. Takaaki Fujita. Matroid, ideal, ultrafilter, tangle, and so on: Reconsideration of obstruction to linear decomposition. International Journal of Mathematics Trends and Technology (IJMTT), 70:18–29, 2024
  19. Takaaki Fujita. Various properties of various ultrafilters, various graph width parameters, and various connectivity systems. arXiv preprint arXiv:2408.02299, 2024
  20. Takaaki Fujita and Koichi Yamazaki. Linear width and single ideal. IEICE Technical Report; IEICE Tech. Rep., 117(269):21–27, 2017
  21. Takaaki Fujita and Koichi Yamazaki. Equivalence between linear tangle and single ideal. Open Journal of Discrete Mathematics, 9(01):7, 2018
  22. Takaaki Fujita and Koichi Yamazaki. Tangle and ultrafilter: Game theoretical interpretation. Graphs and Combinatorics, 36(2):319–330, 2020
  23. Jim Geelen, Bert Gerards, and Geoff Whittle. Obstructions to branch-decomposition of matroids. Journal of Combinatorial Theory, Series B, 96(4):560–570, 2006
  24. Jonathan L Gross, Jay Yellen, and Mark Anderson. Graph theory and its applications. Chapman and Hall/CRC, 2018
  25. Frank Gurski and Carolin Rehs. Comparing linear width parameters for directed graphs. Theory of Computing Systems, 63:1358–1387, 2019
  26. Daniel J Harvey and David R Wood. Parameters tied to treewidth. Journal of Graph Theory, 84(4):364–385, 2017
  27. Sang-il Oum. Rank-width and vertex-minors. Journal of Combinatorial Theory, Series B, 95(1):79–100, 2005
  28. Jisu Jeong, Sigve Hortemo Sæther, and Jan Arne Telle. Maximum matching width: New characterizations and a fast algorithm for dominating set. Discrete Applied Mathematics, 248:114–124, 2018
  29. T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138–154, 2001
  30. David R Karger and Nathan Srebro. Learning Markov networks: Maximum bounded treewidth graphs. In SODA, pages 392–401, 2001
  31. Chun-Hung Liu and David R. Wood. Quasi-tree-partitions of graphs with an excluded subgraph. arXiv preprint arXiv:2408.00983, 2024
  32. Yota Otachi. Isomorphism for graphs of bounded connected-path-distance-width. In International Symposium on Algorithms and Computation, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg
  33. Sang-il Oum. Rank-width: Algorithmic and structural results. Discrete Applied Mathematics, 231:15–24, 2017
  34. William Pettersson and John Sylvester. Bounds on the twin-width of product graphs. Discrete Mathematics & Theoretical Computer Science, 25(Graph Theory), 2023
  35. Neil Robertson and Paul D. Seymour. Graph minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B, 35(1):39–61, 1983
  36. Neil Robertson and Paul D. Seymour. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49–64, 1984
  37. Neil Robertson and Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991
  38. Robert Sasak. Comparing 17 graph parameters. Master’s thesis, The University of Bergen, 2010
  39. Borislav Slavchev, Evelina Masliankova, and Steven Kelk. A machine learning approach to algorithm selection for exact computation of treewidth. Algorithms, 12(10):200, 2019
  40. Nathan Srebro. Maximum likelihood bounded tree-width Markov networks. Artificial Intelligence, 143(1):123–138, 2003
  41. Dimitrios M Thilikos. Algorithms and obstructions for linear-width and related search parameters. Discrete Applied Mathematics, 105(1-3):239–271, 2000
  42. Duc Long Tran. Expanding the Graph Parameter Hierarchy. PhD thesis, Institute of Software, 2022
  43. Douglas Brent West et al. Introduction to Graph Theory, volume 2. Prentice Hall Upper Saddle River, 2001
  44. David R. Wood. On tree-partition-width. European Journal of Combinatorics, 30(5):1245–1253, 2009
  45. Jinbo Xu, Feng Jiao, and Bonnie Berger. A tree-decomposition approach to protein structure prediction. In 2005 IEEE Computational Systems Bioinformatics Conference (CSB’05), pages 247–256. IEEE, 2005
  46. Takaaki Fujita. “Matroid, Ideal, Ultrafilter, Tangle, and so on: Reconsideration of Obstruction to linear decomposition”. In: International Journal of Mathematics Trends and Technology (IJMTT) 70 (2024), pp. 18–29
  47. Takaaki Fujita. “The Interplay between Quasi-Matroid and Connectivity Systems”. In: Asian Research Journal of Mathematics 21.1 (2025), pp. 115–129
  48. Jisu Jeong, Seongmin Ok, and Geewon Suh. “Characterizing graphs of maximum matching width at most 2”. In: Discrete Applied Mathematics 248 (2018), pp. 102–113
  49. Kwangjun Ahn and Jisu Jeong. “Computing the maximum matching width is NP-hard”. In: arXiv preprint arXiv:1710.05117 (2017)
  50. Jisu Jeong, Sigve Hortemo Sæther, and Jan Arne Telle. “Maximum matching width: New characterizations and a fast algorithm for dominating set”. In: Discrete Applied Mathematics 248 (2018), pp. 114–124
  51. Yixin Cao, Jianer Chen, and Yang Liu. "On feedback vertex set: New measure and new structures." In: *Algorithmica* 73 (2015), pp. 63–86
  52. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. "A 2-approximation algorithm for the undirected feedback vertex set problem." In: *SIAM Journal on Discrete Mathematics* 12.3 (1999), pp. 289–297
  53. Jianer Chen et al. "A fixed-parameter algorithm for the directed feedback vertex set problem." In: *Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing.* 2008, pp. 177–186
  54. Douglas Brent West et al. *Introduction to Graph Theory.* Vol. 2. Prentice Hall Upper Saddle River, 2001
  55. Reinhard Diestel. "Graduate Texts in Mathematics: Graph Theory." In: *().*
  56. Reinhard Diestel. "Graph Theory 3rd ed." In: *Graduate Texts in Mathematics* 173.33 (2005), p. 12
  57. Evelyn L. Tan. "Some notes on cycle graphs." In: *Discrete Mathematics* 105.1–3 (1992), pp. 221–226
  58. Haitze J. Broersma and Cornelis Hoede. "Path graphs." In: *Journal of Graph Theory* 13.4 (1989), pp. 427–444
  59. Richard J. Lipton and Robert Endre Tarjan. "A separator theorem for planar graphs." In: *SIAM Journal on Applied Mathematics* 36.2 (1979), pp. 177–189
  60. Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. "Improved approximation algorithms for minimum-weight vertex separators." In: *Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing.* 2005, pp. 563–572
  61. Armen S. Asratian, Tristan M. J. Denley, and Roland Häggkvist. *Bipartite Graphs and Their Applications.* Vol. 131. Cambridge University Press, 1998
  62. Sarbari Mitra and Soumya Bhoumik. "Graceful labeling of triangular extension of complete bipartite graph." In: *Electron. J. Graph Theory Appl.* 7 (2019), pp. 11–30. URL: https://api.semanticscholar.org/CorpusID:145850349
  63. David R. Wood. "On tree-partition-width." In: *European Journal of Combinatorics* 30.5 (2009), pp. 1245–1253
  64. Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. "On the parameterized complexity of computing tree-partitions." In: *arXiv preprint arXiv:2206.11832* (2022)
  65. Guoli Ding and Bogdan Oporowski. "On tree-partitions of graphs." In: *Discrete Mathematics* 149.1–3 (1996), pp. 45–58
  66. Chun-Hung Liu and David R. Wood. "Quasi-tree-partitions of graphs with an excluded subgraph." In: *arXiv preprint arXiv:2408.00983* (2024)
  67. Claude Berge. *Hypergraphs: Combinatorics of Finite Sets.* Vol. 45. Elsevier, 1984
  68. Alain Bretto. "Hypergraph theory." In: *An Introduction. Mathematical Engineering. Cham: Springer* 1 (2013)
  69. Yue Gao et al. "Hypergraph learning: Methods and practices." In: *IEEE Transactions on Pattern Analysis and Machine Intelligence* 44.5 (2020), pp. 2548–2566
  70. Yifan Feng et al. "Hypergraph neural networks." In: *Proceedings of the AAAI Conference on Artificial Intelligence.* Vol. 33. 01. 2019, pp. 3558–3565
  71. Song Feng et al. "Hypergraph models of biological networks to identify genes critical to pathogenic viral response." In: *BMC Bioinformatics* 22.1 (2021), p. 287
  72. Nanao Kita. "Bidirected Graphs I: Signed General Kotzig-Lovász Decomposition." In: *arXiv: Combinatorics* (2017). URL: https://api.semanticscholar.org/CorpusID:119320661
  73. Jesús Arturo Jiménez González and Andrzej Mróz. "Bidirected graphs, integral quadratic forms and some Diophantine equations." In: 2023. URL: https://api.semanticscholar.org/CorpusID:258309617
  74. Takaaki Fujita. "Extensions of MultiDirected Graphs: Fuzzy, Neutrosophic, Plithogenic, Soft, Hypergraph, and Superhypergraph Variants." In: *preprint* (2025)
  75. Takaaki Fujita and Florentin Smarandache. "Mixed graph in fuzzy, neutrosophic, and plithogenic graphs." In: *Neutrosophic Sets and Systems* 74 (2024), pp. 457–479
  76. Takaaki Fujita and Florentin Smarandache. "A Concise Study of Some Superhypergraph Classes." In: *Neutrosophic Sets and Systems* 77 (2024), pp. 548–593. URL: https://fs.unm.edu/nss8/index.php/111/article/view/5416
  77. Florentin Smarandache. "n-SuperHyperGraph and Plithogenic n-SuperHyperGraph." In: *Nidus Idearum* 7 (2019), pp. 107–113
  78. Takaaki Fujita and Florentin Smarandache. *Superhypergraph Neural Networks and Plithogenic Graph Neural Networks: Theoretical Foundations.* Infinite Study, 2025
  79. Takaaki Fujita. *Advancing Uncertain Combinatorics through Graphization, Hyperization, and Uncertainization: Fuzzy, Neutrosophic, Soft, Rough, and Beyond.* Biblio Publishing, 2025. ISBN: 978-1-59973-812-3
  80. Takaaki Fujita. "Superhypertree-length and superhypertree-breadth in superhypergraphs." In: *Advancing Uncertain Combinatorics through Graphization, Hyperization, and Uncertainization: Fuzzy, Neutrosophic, Soft, Rough, and Beyond* (2025), p. 41
  81. Takaaki Fujita. "Exploration of Graph Classes and Concepts for SuperHypergraphs and n-th Power Mathematical Structures." In: *Advancing Uncertain Combinatorics through Graphization, Hyperization, and Uncertainization: Fuzzy, Neutrosophic, Soft, Rough, and Beyond* 3.4 (), p. 512
  82. Florentin Smarandache. *Extension of HyperGraph to n-SuperHyperGraph and to Plithogenic n-SuperHyperGraph, and Extension of HyperAlgebra to n-ary (Classical-/Neutro-/Anti-) HyperAlgebra.* Infinite Study, 2020

Last update:

No citation recorded.

Last update:

No citation recorded.