On the Weisfeiler-Leman dimension of fractional packing. (English) Zbl 1537.68106
Summary: The \(k\)-dimensional Weisfeiler-Leman procedure \((k\)-\(\mathrm{WL})\), which colors \(k\)-tuples of vertices in rounds based on the neighborhood structure in the graph, 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\)-\(\mathrm{WL}\)-equivalent if the \(k\)-dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. \(1\)-\(\mathrm{WL}\)-equivalence is known as fractional isomorphism of graphs, and the \(k\)-\(\mathrm{WL}\)-equivalence relation becomes finer as \(k\) increases.
We investigate to what extent standard graph parameters are preserved by \(k\)-\(\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\)-\(\mathrm{WL}\)-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.
We investigate to what extent standard graph parameters are preserved by \(k\)-\(\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\)-\(\mathrm{WL}\)-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C72 | Fractional graph theory, fuzzy graph theory |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q27 | Parameterized complexity, tractability and kernelization |
Keywords:
Weisfeiler-Leman algorithm; graph packing problem; fractional graph parameters; linear-programming relaxationReferences:
| [1] | Anderson, M.; Dawar, A.; Holm, B., Solving linear programs without breaking abstractions, J. ACM, 62, 6, 48:1-48:26 (2015) · Zbl 1426.68111 |
| [2] | Arvind, V.; Fuhlbrück, F.; Köbler, J.; Verbitsky, O., On the Weisfeiler-Leman dimension of fractional packing, (14th International Conference on Language and Automata Theory and Applications (LATA’20). 14th International Conference on Language and Automata Theory and Applications (LATA’20), Lecture Notes in Computer Science, vol. 12038 (2020), Springer), 357-368 · Zbl 1437.68134 |
| [3] | Atserias, A.; Dawar, A., Definable inapproximability: new challenges for duplicator, J. Log. Comput., 29, 8, 1185-1210 (2019) · Zbl 1446.68072 |
| [4] | Atserias, A.; Maneva, E. N., Sherali-Adams relaxations and indistinguishability in counting logics, SIAM J. Comput., 42, 1, 112-137 (2013) · Zbl 1286.68175 |
| [5] | Babai, L., Graph isomorphism in quasipolynomial time, (Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC’16) (2016)), 684-697 · Zbl 1376.68058 |
| [6] | Babai, L.; Erdős, P.; Selkow, S. M., Random graph isomorphism, SIAM J. Comput., 9, 3, 628-635 (1980) · Zbl 0454.05038 |
| [7] | Blass, A.; Exoo, G.; Harary, F., Paley graphs satisfy all first-order adjacency axioms, J. Graph Theory, 5, 4, 435-439 (1981) · Zbl 0472.05058 |
| [8] | Blass, A.; Gurevich, Y.; Shelah, S., On polynomial time computation over unordered structures, J. Symb. Log., 67, 3, 1093-1125 (2002) · Zbl 1020.03038 |
| [9] | Bollobás, B.; Thomason, A., Graphs which contain all small graphs, Eur. J. Comb., 2, 1, 13-15 (1981) · Zbl 0471.05037 |
| [10] | 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) · Zbl 0785.68043 |
| [11] | G. Chappell, Constructing graphs with domination number and fractional domination number far apart, An unpublished manuscript, 2017. |
| [12] | Chappell, G.; Gimbel, J.; Hartman, C., Approximations of the domination number of a graph, J. Comb. Math. Comb. Comput., 104, 287-297 (2018) · Zbl 1390.05160 |
| [13] | Chlebík, M.; Chlebíková, J., Approximation hardness of dominating set problems in bounded degree graphs, Inf. Comput., 206, 11, 1264-1275 (2008) · Zbl 1169.68037 |
| [14] | Dawar, A., The nature and power of fixed-point logic with counting, SIGLOG News, 2, 1, 8-21 (2015) |
| [15] | Dawar, A.; Severini, S.; Zapata, O., Pebble games and cospectral graphs, Electron. Notes Discrete Math., 61, 323-329 (2017) · Zbl 1378.05130 |
| [16] | Dawar, A.; Wang, P., Definability of semidefinite programming and Lasserre lower bounds for CSPs, (32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’17) (2017), IEEE Computer Society), 1-12 · Zbl 1452.90240 |
| [17] | Dor, D.; Tarsi, M., Graph decomposition is NP-complete: a complete proof of Holyer’s conjecture, SIAM J. Comput., 26, 4, 1166-1187 (1997) · Zbl 0884.05071 |
| [18] | Dross, F., Fractional triangle decompositions in graphs with large minimum degree, SIAM J. Discrete Math., 30, 1, 36-42 (2016) · Zbl 1329.05244 |
| [19] | Dvořák, Z., On recognizing graphs by numbers of homomorphisms, J. Graph Theory, 64, 4, 330-342 (2010) · Zbl 1207.05128 |
| [20] | Ebbinghaus, H.-D.; Flum, J., Finite Model Theory, Springer Monographs in Mathematics (2006), Springer-Verlag: Springer-Verlag Berlin · Zbl 1081.03026 |
| [21] | Feder, T.; Subi, C. S., Packing edge-disjoint triangles in given graphs (2012), Technical Report 13, Electronic Colloquium on Computational Complexity (ECCC) |
| [22] | Fortin, M., \(F O = F O^3\) for linear orders with monotone binary relations, (46th International Colloquium on Automata, Languages, and Programming (ICALP’19). 46th International Colloquium on Automata, Languages, and Programming (ICALP’19), LIPIcs, vol. 132 (2019), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 116:1-116:13 · Zbl 07561609 |
| [23] | Fuhlbrück, F.; Köbler, J.; Verbitsky, O., Local WL invariance and hidden shades of regularity, Discrete Appl. Math., 305, 191-198 (2021) · Zbl 1475.05177 |
| [24] | Füredi, Z., Maximum degree and fractional matchings in uniform hypergraphs, Combinatorica, 1, 2, 155-162 (1981) · Zbl 0494.05045 |
| [25] | Füredi, Z., Matchings and covers in hypergraphs, Graphs Comb., 4, 1, 115-206 (1988) · Zbl 0820.05051 |
| [26] | Fürer, M., On the power of combinatorial and spectral invariants, Linear Algebra Appl., 432, 9, 2373-2380 (2010) · Zbl 1217.05141 |
| [27] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039 |
| [28] | Grohe, M.; Kersting, K.; Mladenov, M.; Selman, E., Dimension reduction via colour refinement, (Proc. of ESA’14. Proc. of ESA’14, Lecture Notes in Computer Science, vol. 8737 (2014), Springer), 505-516, A full version in · Zbl 1425.68313 |
| [29] | Haxell, P. E.; Rödl, V., Integer and fractional packings in dense graphs, Combinatorica, 21, 1, 13-38 (2001) · Zbl 1107.05304 |
| [30] | Hella, L., Logical hierarchies in PTIME, Inf. Comput., 129, 1, 1-19 (1996) · Zbl 0864.68095 |
| [31] | Holyer, I., The NP-completeness of some edge-partition problems, SIAM J. Comput., 10, 4, 713-717 (1981) · Zbl 0468.68069 |
| [32] | Hurkens, C. A.J.; Schrijver, A., On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math., 2, 1, 68-72 (1989) · Zbl 0733.05003 |
| [33] | Immerman, N.; Kozen, D., Definability with bounded number of bound variables, Inf. Comput., 83, 2, 121-139 (1989) · Zbl 0711.03004 |
| [34] | Karp, R., Reducibility among combinatorial problems, (Miller, R.; Thatcher, J.; Bohlinger, J., Complexity of Computer Computations. Complexity of Computer Computations, The IBM Research Symposia Series (1972), Springer: Springer Boston, MA), 85-103 · Zbl 1467.68065 |
| [35] | Kiefer, S.; Neuen, D., The power of the Weisfeiler-Leman algorithm to decompose graphs, (44th International Symposium on Mathematical Foundations of Computer Science (MFCS’19). 44th International Symposium on Mathematical Foundations of Computer Science (MFCS’19), LIPIcs, vol. 138 (2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 45:1-45:15 · Zbl 1541.68291 |
| [36] | Kirkpatrick, D. G.; Hell, P., On the complexity of general graph factor problems, SIAM J. Comput., 12, 3, 601-609 (1983) · Zbl 0525.68023 |
| [37] | Kriege, N. M.; Johansson, F. D.; Morris, C., A survey on graph kernels (2019), Technical report |
| [38] | Lovász, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 4, 383-390 (1975) · Zbl 0323.05127 |
| [39] | Lovász, L., Large Networks and Graph Limits, Colloquium Publications., vol. 60 (2012), American Mathematical Society · Zbl 1292.05001 |
| [40] | Morris, C.; Ritzert, M.; Fey, M.; Hamilton, W. L.; Lenssen, J. E.; Rattan, G.; Grohe, M., Weisfeiler and Leman go neural: higher-order graph neural networks, (33rd AAAI Conference on Artificial Intelligence (AAAI’19) (2019), AAAI Press), 4602-4609 |
| [41] | Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization, Wiley Interscience Series in Discrete Mathematics and Optimization. (1988), Wiley · Zbl 0652.90067 |
| [42] | Otto, M., Bounded Variable Logics and Counting: A Study in Finite Models, Lecture Notes in Logic., vol. 9 (2017), Cambridge University Press |
| [43] | Ramana, M. V.; Scheinerman, E. R.; Ullman, D., Fractional isomorphism of graphs, Discrete Math., 132, 1-3, 247-265 (1994) · Zbl 0808.05077 |
| [44] | Rubalcaba, R. R., Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs (2005), Auburn University, PhD thesis |
| [45] | Scheinerman, E. R.; Ullman, D. H., Fractional Graph Theory. A Rational Approach to the Theory of Graphs (1997), Wiley: John Wiley & Sons · Zbl 0891.05003 |
| [46] | Schrijver, A., Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization. (1999), Wiley |
| [47] | Tinhofer, G., Graph isomorphism and theorems of Birkhoff type, Computing, 36, 285-300 (1986) · Zbl 0581.05038 |
| [48] | 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 |
| [49] | Yuster, R., Integer and fractional packing of families of graphs, Random Struct. Algorithms, 26, 1-2, 110-118 (2005) · Zbl 1061.05076 |
| [50] | Yuster, R., Combinatorial and computational aspects of graph packing and graph decomposition, Comput. Sci. Rev., 1, 1, 12-26 (2007) · Zbl 1302.05149 |
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.
