Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:NP-completeness results for partitioning a graph into total dominating sets
Speaker:Juho Lauri
coming from:Bell Labs, Ireland
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 13 July 2017
Duration:30 Minutes
Building:E1 4

A *total domatic $k$-partition* of a graph is a partition of its vertex set into $k$ subsets such that each intersects the open neighborhood of every vertex.
The maximum $k$ for which a total domatic $k$-partition exists is known as the *total domatic number* of a graph $G$, denoted by $d_t(G)$.
We extend considerably the known hardness results by showing it is NP-complete to decide whether $d_t(G) \geq 3$ where $G$ is a bipartite planar graph of bounded maximum degree.
Similarly, for every $k \geq 3$, it is NP-complete to decide whether $d_t(G) \geq k$, where $G$ is a split graph or $k$-regular.
In particular, these results complement very recent combinatorial results regarding $d_t(G)$ on some of these graph classes by showing that the known results are, in a sense, best possible.
Moreover, for general $n$-vertex graphs, we show the problem is solvable in $3^n n^{O(1)}$ time and polynomial space, and derive even faster algorithms for special graph classes via simple reductions.
Finally, we briefly discuss the possibility of breaking the $3^n$ time barrier in polyspace.
In particular, this bound has been bypassed for the related problem of *domatic number*, but it appears plausible different ideas are needed for total domatic number.

Name(s):Davis Issac
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Davis Issac, 07/05/2017 01:48 PM -- Created document.