Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Are there necessary and sufficient conditions for a uniform hyper graph to have a perfect fractional matching ?

share|improve this question
The definition is already a nice characterization. What are you looking for? A necessary and sufficient condition that is combinatorial? – Tsuyoshi Ito Jun 14 '12 at 13:34
4  
Could you provide some context, background, and motivation? – Kaveh♦ Jun 14 '12 at 16:20
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. – Jukka Suomela Jun 15 '12 at 7:52
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. – user9755 Jun 16 '12 at 17:07

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.