From: ladanyi@CS.Cornell.EDU (Laszlo Ladanyi)
Newsgroups: sci.math.research,sci.op-research
Subject: Re: Please look at this hypothesis
Date: 26 Jun 1998 12:36:19 -0400

busygin@a-teleport.com writes:

>  Tuomo Takkula <tuomo@cs.chalmers.se> wrote:
>>
>> busygin@a-teleport.com writes:
>>
>> >
>> > Hello All,
>> >
>> > I consider relations between real and boolean solutions of linear
>> > algebraic systems of equations, which have a boolean matrix and always 1 in
>> > the right part (i.e. Ax=b; a(i,j) \in {0,1}; b(i)=1 for all i). I need to
>> > determine cases when the set of real solutions is the convex hull of the set
>> > of boolean solutions. I have a hypothesis on a sufficient condition for such
>> > relations. In order to formulate it let's introduce a graph by the following
>> > rule. The set of vertices of the graph is the set of variables of the system
>> > and there is an edge between two vertices if two corresponding variables are
>> > included in the same equation. In this case we will say that the edge is
>> > induced by the equation. Obviously, one edge can be induced by many
>> > equations.
>> >
>> > The Hypothesis: If there is no odd cycle in the graph or in every
>> > odd cycle there are at least two edges induced by the same equation then the
>> > set of real solutions of the system is the convex hull of all boolean
>> > solutions of the system.
>> >
>> > I believe that the hypothesis is true and I try to
>> > prove it for some months. But I am not an expert in convex analysis and
>> > algebra. So, if you have an idea about this problem or can suggest me
>> > something, please help me. It is very important for my research on universal
>> > solving methods for class NP.
>>
>> 	Hi.
>>
>> Your approach sounds remotely familiar. Have a look at the keywords
>> (totally) unimodular matrices, balanced matrices, network matrices
>> in Schrijver, Theory of linear and integer programming, Wiley, 1986.

>These concepts are relevant if the vector in the right part is arbitrary
>integer (because arbitrariness is used in the proof of necessity of
>unimodularity). But I consider a particular case when all components of the
>vector in the right part are 1. So I think unimodularity is not necessary in
>this case.

>P.S. In the previous message I forgot to mention that I mean the set
>non-negative integer solutions.

The model you describe is called Set Partitioning Problem. There is a
base set, its elements correspond to the rows of the matrix. There
are subsets, these correspond to the columns (an element of the base
set is in the subset if there is a 1 in the matrix at the intersection
of the corresponding row and column). The objective is to select (with
minimal cost) a disjoint set of subsets so that they cover the base
set, i.e., partition the base set.
The graph you describe is called the intersection graph corresponding
to the given SPP. 
Odd cycles do play an important role in the SPP, they generate valid
inequalities, and if they are odd holes (cycles without a chord) then
the generated valid inequalities are facet defining. 

Try to search for these keywords. Your hypothesis might be true, even
though the SPP is NP complete in general. If your hypothesis is true
then you have characterized a special case. You can try to look at
Lovasz-Plummer: Matching Theory, it has some discussion on the SPP and
describes a few special cases.

--Laci
-- 
----------------------------------------------------------------------
| Laci Ladanyi           | God made one mistake when he created man: |
| ladanyi@cs.cornell.edu |     He wrote self-modifying code ...      |
----------------------------------------------------------------------