Top

Published in:

2020 | OriginalPaper | Chapter

On the Weisfeiler-Leman Dimension of Fractional Packing

Authors : Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky

Published in: Language and Automata Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The k-dimensional Weisfeiler-Leman procedure (\(k\text {-}\mathrm {WL}\)) has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are \(k\text {-}\mathrm {WL} \)-equivalent if dimention k does not suffice to distinguish them. \(1\text {-}\mathrm {WL}\)-equivalence is known as fractional isomorphism of graphs, and the \(k\text {-}\mathrm {WL} \)-equivalence relation becomes finer as k increases.

We investigate to what extent standard graph parameters are preserved by \(k\text {-}\mathrm {WL} \)-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of \(k\text {-}\mathrm {WL} \)-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas

next chapter Input Strictly Local Tree Transducers

Anderson, M., Dawar, A., Holm, B.: Solving linear programs without breaking abstractions. J. ACM 62(6), 48:1–48:26 (2015)MathSciNetCrossRef

Arvind, V., Fuhlbrück, F., Köbler, J., Verbitsky, O.: On the Weisfeiler-Leman dimension of Fractional Packing. Technical report, arxiv.org/abs/1910.11325 (2019)

Atserias, A., Dawar, A.: Definable inapproximability: new challenges for duplicator. In: Proceedings of CSL 2018. LIPIcs, vol. 119, pp. 7:1–7:21 (2018)

Babai, L.: Graph isomorphism in quasipolynomial time. In: Proceedings of STOC 2016, pp. 684–697 (2016)

Cai, J., Fürer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identifications. Combinatorica 12(4), 389–410 (1992)MathSciNetCrossRef

Chappell, G., Gimbel, J., Hartman, C.: Approximations of the domination number of a graph. J. Combin. Math. Combin. Comput. 104, 287–297 (2018)MathSciNetMATH

Dawar, A.: The nature and power of fixed-point logic with counting. SIGLOG News 2(1), 8–21 (2015)CrossRef

Dawar, A., Severini, S., Zapata, O.: Pebble games and cospectral graphs. Electron. Notes Discrete Math. 61, 323–329 (2017)CrossRef

Dell, H., Grohe, M., Rattan, G.: Lovász meets Weisfeiler and Leman. In: Proceedings of ICALP 2018. LIPIcs, vol. 107, pp. 40:1–40:14 (2018)

10.

Dor, D., Tarsi, M.: Graph decomposition is NP-complete: a complete proof of Holyer’s conjecture. SIAM J. Comput. 26(4), 1166–1187 (1997)MathSciNetCrossRef

11.

Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Springer Monographs in Mathematics. Springer, Berlin (2006)MATH

12.

Füredi, Z.: Matchings and covers in hypergraphs. Graphs Comb. 4(1), 115–206 (1988)MathSciNetCrossRef

13.

Fürer, M.: On the power of combinatorial and spectral invariants. Linear Algebra Appl. 432(9), 2373–2380 (2010)MathSciNetCrossRef

14.

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)MATH

15.

Glebov, R., Liebenau, A., Szabó, T.: On the concentration of the domination number of the random graph. SIAM J. Discrete Math. 29(3), 1186–1206 (2015)MathSciNetCrossRef

16.

Grohe, M., Kersting, K., Mladenov, M., Selman, E.: Dimension reduction via colour refinement. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 505–516. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44777-2_42. arXiv version: arxiv.org/abs/1307.5697CrossRef

17.

Haxell, P.E., Rödl, V.: Integer and fractional packings in dense graphs. Combinatorica 21(1), 13–38 (2001)MathSciNetCrossRef

18.

Kim, J., Vu, V.: Sandwiching random graphs: universality between random graph models. Adv. Math. 188(2), 444–469 (2004)MathSciNetCrossRef

19.

Kirkpatrick, D.G., Hell, P.: On the complexity of general graph factor problems. SIAM J. Comput. 12(3), 601–609 (1983)MathSciNetCrossRef

20.

Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13(4), 383–390 (1975)MathSciNetCrossRef

21.

Otto, M.: Bounded Variable Logics and Counting: A Study in Finite Models. Lecture Notes in Logic, vol. 9. Cambridge University Press, Cambridge (2017)

22.

Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of STOC 1997, pp. 475–484. ACM (1997)

23.

Rubalcaba, R.R.: Fractional domination, fractional packings, and fractional isomorphisms of graphs. Ph.D. thesis, Auburn University (2005)

24.

Scheinerman, E.R., Ullman, D.H.: Fractional Graph Theory. A Rational Approach to the Theory of Graphs. Wiley, Hoboken (1997)MATH

25.

Weisfeiler, B., Leman, A.: The reduction of a graph to canonical form and the algebra which appears therein. NTI Ser. 2 9, 12–16 (1968). English translation is available at https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf

26.

Yuster, R.: Integer and fractional packing of families of graphs. Random Struct. Algorithms 26(1–2), 110–118 (2005)MathSciNetCrossRef

Title: On the Weisfeiler-Leman Dimension of Fractional Packing
Authors: Vikraman Arvind
Frank Fuhlbrück
Johannes Köbler
Oleg Verbitsky
Publisher: Springer International Publishing
Book: Language and Automata Theory and Applications
Print ISBN: 978-3-030-40607-3

Electronic ISBN: 978-3-030-40608-0

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-40608-0_25

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner