Are there necessary and sufficient conditions for a uniform hyper graph to have a perfect fractional matching ?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ The definition is already a nice characterization. What are you looking for? A necessary and sufficient condition that is combinatorial? $\endgroup$– Tsuyoshi ItoJun 14, 2012 at 13:34
-
4$\begingroup$ Could you provide some context, background, and motivation? $\endgroup$– KavehJun 14, 2012 at 16:20
-
$\begingroup$ To me it seem that if you can solve the problem quickly in uniform hypergraphs, you can also solve the problem quickly in arbitrary hypergraphs – just add gadgets that make the hypergraph uniform while preserving the existence of a perfect fractional matching. And in the case of arbitrary hypergraphs, it seems to me that the problem is almost as difficult as solving a general 0/1 packing LP. Hence I would not expect that there is a particularly useful formulation of a necessary & sufficient condition. $\endgroup$– Jukka SuomelaJun 15, 2012 at 7:52
-
$\begingroup$ 1. Yes, combinatorial condition, like Tuttes's theorem 2. No it is not like 1/0, because for ex. regular graph has perfect fractional matching, but very few is known about 1/0 problem for it. $\endgroup$– user9755Jun 16, 2012 at 17:07
Add a comment
|