Re: small combination problem

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 03/27/04 

Date: Sat, 27 Mar 2004 04:08:49 -0700

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?
  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).

> 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.

> 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.
  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' .

J

Relevant Pages

  • Re: small combination problem
    ... Now 0 is only used twice, so remove the solutions containing 0. ... Leaving behind the clique that you found. ... The graph for this case is: ... into maximal stable sets, there exists some clique which hits every ...
    (comp.programming)
  • 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.programming)
  • 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: Time complexity of couting the number of cliques on k nodes
    ... of vertices of the host graph is part of the input. ... especially as the clique size k gets ... Remove all vertices of degree less than k-1 and their neighboring ... take the resulting subgraph and go to step ...
    (sci.math)
  • Re: I cant edit the graph .
    ... I did it twice and I still can't edit the graph ... First make sure no MS Office apps are running, ... I am having a problem with my microsoft graph. ...
    (microsoft.public.mac.office.powerpoint)