CODEWITHSUNDEEP
algorithmcomputer-sciencegraph-theorygraph-algorithm
Kiba005
Kiba005

Reputation: 21

Troubles with a graph task

I can't come up with an efficent solution to this problem:

Given a digraph G(V,E) (not necessarly connected) with at most one edge between each pair of nodes ( that means E ≤ V×(V-1)÷2 ), find a set of nodes S that satisfies these properties:

The only solution that I thougth is a bruteforce search of S, can anyone give me an hint? Thanks for the patience!

UPD: another important thing is that we can suppose that G is made in a way that S ≠ ∅

UPD2: rewrote condition 2 (sorry Diego Mazzaro).

Upvotes: 2

Views: 150

Answers (1)

Diego Mazzaro
Diego Mazzaro

Reputation: 2882

Since there are children I assume we are speaking about directed graphs.

Let me use this notation in order to shorten things: Ch(x) and Ch²(x) for Child(x) and Grandchild(x). Similarly P(x) for Parent(x).

Then the conditions can be put as:

  • ∀x∈S ⇒ Ch(x)∉S, Ch²(x)∉S;
  • ∀x∉S ⇒ ∃y∈S | x=Ch(y) ∨ x=Ch²(y)

Interpretation

Touch every vertex in the graph with these additional two rules:

  • whenever you touch a vertex (directly) also its children and grandchildren will be considered as touched (indirectly).
  • vertex that has been directly touched cannot be also touched indirectly.

At the end S will be the the set of all directly touched vertices.

This lets to show that not always there is a solution. For example if you consider a loop of four vertices there is not solution. Also a "loop of two vertex" cannot be solved. Note instead that A>B>C>D>E>B can be solved also if it has a loop of four thanks to the fact tha A (to be touched directly) is outside the loop.

Any loopless graph is solvable by the following:

  • touch (directly) all the vertices without parents
  • remove them and all the undirectly touched ones
  • repeat from top

If the graphs are not guaranteed to be loopless I would think to setup a backtracking algorithm considering the following:

- initial step:
    - touch (directly) all the vertices without parents (label them with 0)
    - ∀x directly touched
        - label with 1 every Ch(x)
        - label with 2 any Ch²(x) <0 or not already written 
        - label with 3 any Ch³(x) <0 or not already written
        - label with -1 every P(x)  < -1 or not already written
        - label with -2 every P²(x) < -2 or not already written
        - label with -3 every P³(x) not already written
- each move:
    - touch (directly) any vertex marked with 3 or -3
        -giving preference to the ones marked with -3
    - do the labeling work

This is not a complete description of the implementation, is only intended to give a direction other than brute force by sampling some vertex and check. Backtracking is itself brute force indeed but the succes or failure is related to the quality of the heuristic used. As Warnsdorf says: "always try first the vertex with lower degree". In this case always try first to touch vertices with less parents (so less possibilities to be touched indirectly).

In practice any information about the "loop-ity" and similar properties of the graph whould help in designing a better algorithm.

Another hint would be to separate connected components and then work on them indipendently as long as the time complexity of the main algorithm is more than linear. This helps becouse this will bring the time to be related to the size of the bigger component instead than to the size of the initial full (not connected) graph.

Upvotes: 1

Related Questions