Re: small combination problem

From: Ian Woods (newspub2_at_wuggyNOCAPS.org)
Date: 03/29/04 

Date: Mon, 29 Mar 2004 01:25:40 +0000 (UTC)

Jim Nastos <nastos@cs.ualberta.ca> wrote in
news:Pine.LNX.4.44.0403270329410.1234-100000@tees.cs.ualberta.ca:

> On Fri, 26 Mar 2004, Ian Woods wrote:
>
>> Well, the numbers used only once can't be part of the solution: every
>> number will have to be used at least twice. So, eliminate the
>> solutions containing those numbers and let's look at this again:
>
> Why stop there?

I wanted to get a nice graph at the end, even though I missed and edge. ;)

> Since B = {3,5,6,7,9}, its corresponding A-set would have to have at
> least 4 elements (since a 3-set for A gives a B-set of size only 3).

Yep, and so each and every number in the solution must appear 4 times or
more, and a number can only appear once in each set of 'candidate'
solutions which generate each number.
 

>> B solutions
>> {3} { 0,3} { 1,2}
>> {5} { 0,5} { 1,4} {2,3}
>> {6} { 1,5} { 2,4}
>> {7} { 2,5} { 3,4}
>> {9} { 4,5}
>
> Now 0 is only used twice, so remove the solutions containing 0.
>
> {3} {1,2}
> {5} {1,4} {2,3}
> {6} {1,5} {2,4}
> {7} {2,5} {3,4}
> {9} {4,5}
>
> Now:
> 1 is used 3 times
> 2 is used 4 times
> 3 is used 2 times
> 4 is used 4 times
> 5 is used 3 times
>
> So 3 is now underused, and we remove solutions using 3:
>
> {3} {1,2}
> {5} {1,4}
> {6} {1,5} {2,4}
> {7} {2,5}
> {9} {4,5}
>
> Leaving behind the clique that you found.
> I think that if there is a unique A-solution, then the
> 'elimination reduction' would always leave behind the
> unique solution with no searching necessary... but I
> haven't thought about this long enough to be sure.

I believe it must do. This operation /must/ be equivalent to rejecting
vertices which cannot be in the minimum possible clique which is a
solution. Basically, any vertex with an insufficient in-degree
(insufficient usage) can be removed, and that can be done repeatedly.

If there is only one solution then there would only be one clique in the
graph, so all vertices not in the clique (all numbers not in the solution)
would have insufficient usage. The point you get to in this case is where
all the numbers in existing all have the same 'usage', all have the same
in-degree.

>> Let's draw a graph of how all these numbers relate to each other... I
>> happen to like graphs. If two numbers are in a solution, they're
>> connected by an edge. The graph for this case is:
>>
>> 0---------3
>> | |
>> | |
>> 5---------2
>> |\_ _/|
>> \ \-1-/ /
>> \ | /
>> \ | /
>> \|/
>> 4
>
> You missed edge {3,4}, but that's okay - it is not in the solution
> clique.
>
>> o the condidate A' graph must have at least one edge making each
>> number in B'.
>
>> The bad news is that graph algorithms involving complete subgraphs
>> have a nasty habit of being NP-complete. The added constraint that
>> the edges in the complete subgraph must produce all of the numbers in
>> B' might help, but I'm not sure exactly how at the moment.
>
> If every edge is 'coloured' with the number it represents (i.e. the
> sum
> of its vertices) then we are looking for a clique containing at least
> one edge from every colour. Note that all the edges coming out of any
> single vertex must all be different colours.

Yes. Handilly, these things are sets rather than lists.

> Consider taking the line graph of this graph; (i.e. map every edge
> of
> G to a vertex in a new graph L(G) and two vertices in L(G) are adj iff
> their corresponding edges in G share a vertex.)
> Since no two same-coloured edges in G share a vertex, then the
> colouring
> (i.e. the corresponding vertex labeling) is a valid vertex colouring
> of L(G). A clique in G (of size k) corresponds to a clique in L(G) (of
> size k-choose-2.) We are now looking for cliques in L(G) that hit
> every colour class in L(G). This still might be NP-hard in general,
> but there are many graph classes for which this problem is solvable.
> In fact, there is a class of graphs defined in this way: for any
> partition of a graph H into maximal stable sets, there exists some
> clique which hits every maximal stable set (I think this is the
> complement-definition of Strongly Perfect graphs.)
>
> Anyway... I think a unique solution will yield a graph which is a
> clique, and perhaps when elimination is carried out as far as I took
> it above, hopefully it would be the case that every maximal clique
> yields a solution set A' .

For single-solution cases, there will be only one clique which satisfies
the properties... but, that may not mean that it's the maximum clique. You
have, elsethread, posted a counterexample where there are (at least) two
A' which produce the same B'. Two things which sprang out at me: the
maximum clique might not fulfil the properties on edges, and a large clique
can hold smaller cliques which are A'-solutions in themselves.
 

Anyway...

Here's an attempt at finding at least one set A' for a set B' known to have
2 solutions eliminatling only candidate solutions. Also, it's a stab at
being able to make solutions for B's which have 'large' (computer-word-
sized) ranges.

R is 5 again, so the numbers in A' can range from -5 to +5. (The range for
this B to have 2 solutions could be smaller I suspect.)

B'={-3,-2,-1,3,4,5}

The solutions are:

A'1={-2,-1, 0, 5}
A'2={-4, 1, 2, 3}

So, for each element in B'

B solution range -54321012345
{-3} {-5 to -2, -1 to 2} -> 11111111000
{-2} {-5 to -2, 0 to 3} -> 11110111100
{-1} {-5 to -1, 0 to 2} -> 11111111000
{3} {-2 to 1, 2 to 5} -> 00011111111
{4} {-1 to 1, 3 to 5} -> 00001110111
{5} { 0 to 2, 3 to 5} -> 00000111111

Now, instead of counting the numbers, I'm going to use a magic operator

x MOP y

It performs the 'intersection' of the ranges. In terms of the elimination
algorithm, it discards any numbers which are not in both x and y. It's
important to note that although I've got seperate ranges for the 'first and
second' numbers in the solutions (which may or may not cross) the MOP
operator doesn't care which range a number appears in as long as it appears
in both x and y.

So, for example:

{-3,-2} -> {-5 to -2, -1 to 2} MOP {-5 to -2, 3 to 0}
        = {-5 to -2, 2 to 0 }

and

{-1, 3} -> {-5 to -1, 0 to 2} MOP {-2 to 1, 2 to 5}
        = {-2 to 1, 2 }

Now, suppose we wanted to find all the solutions for the B' {-3,-2} within
the range. We want to eliminate any numbers from the ranges of the B's for
{-3} and {-2}. This is precisely what MOP does. So, as in the example:

B{-3} MOP B{-2} -> {-5 to -2, 2 to 0}

If one number from A' was used to generate /both/ -3 and -2 it /must/ be in
the range of B{-3} MOP B{-2}.

In this case, B' has 6 elements so A' must have at least 4 elements. If we
guess that it must have 4 elements... A'={a,b,c,d} and the numbers in B'
are

a+b b+c c+d
a+c b+d
a+d

Or, in terms of usage, the numbers a,b,c and d are all used 3 times.

Armed with this knowledge, we want to eliminate any numbers which are used
less than three times out of all of the ranges. Also, we know that the
numbers in A' are used to generate three different numbers in B'. (*
Assumption: no two additions have generated the same value in B'. At the
moment, I'm still chucking the idea around...)

Well, let's get MOPping. We want to see what x MOP y MOP z gets to, since
we know that 3 numbers (x, y and z) are generated from a single number in
A'. The ranges we come out with in the end are numbers which could possibly
have been used to generated all three.

There are 3_C_6 (20) possible combinations:

                   -54321012345
-3 MOP -2 MOP -1 -> 11110111000
-3 MOP -2 MOP 3 -> 00010111000
-3 MOP -2 MOP 4 -> 00000110000
-3 MOP -2 MOP 5 -> 00000111000
-3 MOP -1 MOP 3 -> 00011111000
-3 MOP -1 MOP 4 -> 00001110000
-3 MOP -1 MOP 5 -> 00000111000
-3 MOP 3 MOP 4 -> 00001110000
-3 MOP 3 MOP 5 -> 00000111000
-3 MOP 4 MOP 5 -> 00000110000
-2 MOP -1 MOP 3 -> 00010111000
-2 MOP -1 MOP 4 -> 00000110000
-2 MOP -1 MOP 5 -> 00000111000
-2 MOP 3 MOP 4 -> 00000110100
-2 MOP 3 MOP 5 -> 00000111100
-2 MOP 4 MOP 5 -> 00000110100
-1 MOP 3 MOP 4 -> 00001110000
-1 MOP 3 MOP 5 -> 00000111000
-1 MOP 4 MOP 5 -> 00000110000
 3 MOP 4 MOP 5 -> 00000110111

Okay... where do we go from here?

Well, I don't know. But this is somewhat interesting: 0 and 1 can be used
to make all of the numbers. This effectively means that 0 and 1 both appear
in solutions (though not necessarilly the same solution!)

Also, I have the sneaky feeling that if there was only one solution then
this approach would have produced combinations where there are no numbers
(all zeros) or combinations with only one possible number (1 single 1).

Perhaps I've picked a bad example... but I don't have time to do it over
again. Hopefully this'll kick off some more ideas!

Ian Woods 

-- 
"I'm a paranoid schizophrenic sado-masochist.
My other half's out to get me and I can't wait."
Richard Heathfield

Relevant Pages

  • Re: small combination problem
    ... I wanted to get a nice graph at the end, even though I missed and edge. ... > Leaving behind the clique that you found. ... It performs the 'intersection' of the ranges. ... second' numbers in the solutions the MOP ...
    (comp.theory)
  • Re: small combination problem
    ... >> the graph, so all vertices not in the clique (all numbers not in the ... these things are sets rather than lists. ... >> It performs the 'intersection' of the ranges. ...
    (comp.programming)
  • Re: small combination problem
    ... >> the graph, so all vertices not in the clique (all numbers not in the ... these things are sets rather than lists. ... >> It performs the 'intersection' of the ranges. ...
    (comp.theory)
  • Re: small combination problem
    ... the maximum clique idea has to be scrapped. ... no maximum clique of the graph of B' is a solution to B'. ... operation efficiently for large ranges. ...
    (comp.programming)
  • Re: small combination problem
    ... the maximum clique idea has to be scrapped. ... no maximum clique of the graph of B' is a solution to B'. ... operation efficiently for large ranges. ...
    (comp.theory)