Re: Complexity of graph problems

Michael Schnupp a écrit : 
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?


Using a reduction from minimum Set Cover...

(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 don't think that is the same paper since in the paper "Roman domination over some graph classes" we show that the Roman domination number of an interval graph or a cograph can be computed in linear time. Moreover, we show that there are polynomial time algorithms for computing the Roman domination numbers of AT-free graphs and graphs with a $d$-octopus.

Mathieu.

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

  • Re: Complexity of graph problems
    ... >> # (There are papers stating it is NP-complete, but I haven't found any proof ... >> # Any hint would be great. ... graphs, but I did'n't manage to find a working reduction. ...
    (comp.theory)
  • Re: Complexity of graph problems
    ... >> 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. ... > domination over some graph classes" we show that the Roman domination ... Your polynomial time algorithms are nice. ...
    (comp.theory)
  • Re: set, dict and other structures
    ... > implementation of graphs seems to satisfy all users. ... project and I'm sure there are a few more dimensions that didn't make it ...
    (comp.lang.python)
  • Re: graph problem
    ... just want a hint for similar problems or topics. ... ordinary algorithms like e.g. finding cycles in graphs are ... For homework I am too old... ...
    (sci.math)