diff -Nru xapian1.3-core-1.3.4/debian/changelog xapian1.3-core-1.3.4/debian/changelog
--- xapian1.3-core-1.3.4/debian/changelog	2016-01-19 17:10:25.000000000 +0000
+++ xapian1.3-core-1.3.4/debian/changelog	2016-01-20 11:16:09.000000000 +0000
@@ -1,3 +1,9 @@
+xapian1.3-core (1.3.4-0ubuntu4) xenial; urgency=medium
+
+  * Add Breaks/Replaces. LP: #1536093.
+
+ -- Matthias Klose <doko@ubuntu.com>  Wed, 20 Jan 2016 12:15:10 +0100
+
 xapian1.3-core (1.3.4-0ubuntu3) xenial; urgency=medium
 
   * Build without optimization on s390x.
diff -Nru xapian1.3-core-1.3.4/debian/control xapian1.3-core-1.3.4/debian/control
--- xapian1.3-core-1.3.4/debian/control	2016-01-19 17:10:28.000000000 +0000
+++ xapian1.3-core-1.3.4/debian/control	2016-01-20 11:17:05.000000000 +0000
@@ -11,8 +11,8 @@
 Package: libxapian-1.3-5
 Architecture: any
 Section: libs
-Breaks: libxapian13-1, libxapian1.3-1
-Replaces: libxapian13-1, libxapian1.3-1
+Breaks: libxapian13-1, libxapian1.3-1, libxapian1.3-4
+Replaces: libxapian13-1, libxapian1.3-1, libxapian1.3-4
 Depends: ${shlibs:Depends}, ${misc:Depends}
 Suggests: xapian-tools
 Description: Search engine library
@@ -32,6 +32,8 @@
 Priority: extra
 Depends: libxapian-1.3-5 (= ${binary:Version}), ${shlibs:Depends}, ${misc:Depends}
 Suggests: libc6-dbg, libgcc1-dbg, zlib1g-dbg, libstdc++6-4.6-dbg
+Breaks: libxapian1.3-4-dbg
+Replaces: libxapian1.3-4-dbg
 Description: Debugging symbols for the Xapian Search engine library
  This package contains debugging symbols for the core Xapian library.
  .
diff -Nru xapian1.3-core-1.3.4/debian/control.in xapian1.3-core-1.3.4/debian/control.in
--- xapian1.3-core-1.3.4/debian/control.in	2015-10-16 15:59:06.000000000 +0000
+++ xapian1.3-core-1.3.4/debian/control.in	2016-01-20 11:17:00.000000000 +0000
@@ -11,8 +11,8 @@
 Package: libxapian@LIBXAPIAN_SOVERSION@
 Architecture: any
 Section: libs
-Breaks: libxapian13-1, libxapian1.3-1
-Replaces: libxapian13-1, libxapian1.3-1
+Breaks: libxapian13-1, libxapian1.3-1, libxapian1.3-4
+Replaces: libxapian13-1, libxapian1.3-1, libxapian1.3-4
 Depends: ${shlibs:Depends}, ${misc:Depends}
 Suggests: xapian-tools
 Description: Search engine library
@@ -32,6 +32,8 @@
 Priority: extra
 Depends: libxapian@LIBXAPIAN_SOVERSION@ (= ${binary:Version}), ${shlibs:Depends}, ${misc:Depends}
 Suggests: libc6-dbg, libgcc1-dbg, zlib1g-dbg, libstdc++6-4.6-dbg
+Breaks: libxapian1.3-4-dbg
+Replaces: libxapian1.3-4-dbg
 Description: Debugging symbols for the Xapian Search engine library
  This package contains debugging symbols for the core Xapian library.
  .