Re: Complexity of graph problems

Mathieu Liedloff wrote:
>
>> # How to prove NP-completeness of Roman-Domination-Set on split graphs?
>> # (There are papers stating it is NP-complete, but I haven't found any proof
>> # so far.)
>> #
>> # Any hint would be great.
>
>
> Using a reduction from Vertex Cover:

Ah, thanks. Not so difficult - if you now how. :)

Today I tried to figure out, how to prove its completeness on bipartite
graphs, but I did'n't manage to find a working reduction.
Any hints here?

(Maybe even an idea about RDS on circle graphs?)

> Further results for some special graph classes can be found in
> Roman domination over some graph classes, M. Liedloff, T. Kloks, J. Liu,
> S.L. Peng, Proceedings of WG'2005.

That's the very paper stating NP-completeness for RDS on planar, split
and bipartite graphs by referencing to another paper which references
to "private communication"...

I managed the planar case¹, but had trouble with the others.

thanks again
michas

¹thinking about it, the split case is not much different. :)
.

Relevant Pages