Problem of the unit dominating

The overall problem dominating is a Np-complete problem of the Graph theory.

Definition

An authority of the overall problem dominating is defined by

a graph G including/understanding a unit S of tops and a unit has arcs;
a whole K strictly positive and lower or equal to the number of tops in G .

It is then a question of determining if there exists a Ensemble dominating for G , of size lower or equal to K . In other words, we want to know if there exists a Sous-ensemble D of S having a size lower or equal to K and such as all the tops which are not in D are connected to at least a top of D by an arc of has .

Example

For the graph on the line, {4,5} is an example of Ensemble dominating of size 2.

Np-complétude

The overall problem dominating was proven Np-complete by using a reduction since the Problème of cover of tops.

Proof

The problems of cover of tops and overall dominating are similar; the difference being that the first relates to arcs whereas the second relates to the tops. Consequently, let us find a means to build a graph using tops to represent the arcs of the initial graph. Let us show how to build the graph allowing to make the reduction of the problem of cover of tops towards the overall problem dominating:

That is to say < G , K > an authority of the problem of cover of tops. Let us build new a graph G' by adding new tops to G . Precisely, for any arc < v , W > of G , let us add a top VW and the arcs < v , VW > and < W , VW >.

Now, the proof: G has a unit dominating D of size K if and only if G has a cover of tops C of size K .

( $\ Rightarrow$ ) D is a whole dominating of G of size K . Therefore, any arc of G relates to a top of D . D is thus a cover of the tops of G of size K .

( $\ Leftarrow$ ) C is a cover of tops of G of size K , therefore the new ones and the old tops are dominated by K tops.

Example

The graph on the line shows the construction of the graph G' to make the reduction.

Approximation

The version “optimization” of the problem, which consists in finding smallest

|D|

such as

|D|

is a Ensemble dominating, is approximable. To be more precise, it is approximable with a factor

1 + \ log |D|

, but, attention, it is not approximable at a distance

c \ log |D|

for a

c > 0

References

Michael R. Garey and David S. Johnson, Computers and Intractability: With Guide to the Theory off Np-Completeness , W.H. Freeman, 1979. ISBN 0-7167-1045-5}} A1.1: GT2, pg.190
Mitchell S., and S. Hedetniemi, " Edge domination in trees" , Proceedings off the 8th Southeastern Conference one Combinatorics, Graph Theory, and Computing , Utilitas Mathematica Publishing, Winnipeg, 489-509.
Yannakakis, Mr. and F. Gavril, " Edge dominating sets in graphs" , manuscript not published.
(in) a digest of problems of optimization in NP

Random links: