학술논문
On the Weisfeiler-Leman dimension of fractional packing.
Document Type
Journal
Author
Arvind, V. (6-HBNI2-IM) AMS Author Profile; Fuhlbrück, Frank (D-HUMB-NDM) AMS Author Profile; Köbler, Johannes (D-HUMB-NDM) AMS Author Profile; Verbitsky, Oleg (D-HUMB-NDM) AMS Author Profile
Source
Subject
90 Operations research, mathematical programming -- 90C Mathematical programming
90C32Fractional programming
90C35Programming involving graphs or networks
90C32
90C35
Language
English
Abstract
This paper considers the Weisfeiler-Leman invariance of the fractional packing number and its edge disjoint variant. First, the authors prove that the fractional set packing number of a hypergraph is 1-WL-invariant. Then, it is shown that the fractional packing number is $k$-WL-invariant for pattern graphs of hereditary treewidth $k$. Especially, the WL dimension of the fractional edge disjoint triangle packing number is 2. Finally, the authors discuss tight bounds in some cases for the fractional matching number, the fractional cover number, the fractional domination number and the fractional edge disjoint triangle packing number.