# Disrupting Diffusion: Token-Level Attention Erasure Attack against
Diffusion-based Customization

Yisu Liu, Jinyang An, Wanqian Zhang, Dayan Wu, Jingzi Gu, Zheng Lin, Weiping
Wang  Institute of Information Engineering, Chinese Academy of
SciencesBeijingChina

###### Abstract.

With the development of diffusion-based customization methods like DreamBooth,
individuals now have access to train the models that can generate their
personalized images. Despite the convenience, malicious users have misused
these techniques to create fake images, thereby triggering a privacy security
crisis. In light of this, proactive adversarial attacks are proposed to
protect users against customization. The adversarial examples are trained to
distort the customization model’s outputs and thus block the misuse. In this
paper, we propose DisDiff (Disrupting Diffusion), a novel adversarial attack
method to disrupt the diffusion model outputs. We first delve into the
intrinsic image-text relationships, well-known as cross-attention, and
empirically find that the subject-identifier token plays an important role in
guiding image generation. Thus, we propose the Cross-Attention Erasure module
to explicitly ”erase” the indicated attention maps and disrupt the text
guidance. Besides, we analyze the influence of the sampling process of the
diffusion model on Projected Gradient Descent (PGD) attack and introduce a
novel Merit Sampling Scheduler to adaptively modulate the perturbation
updating amplitude in a step-aware manner. Our DisDiff outperforms the state-
of-the-art methods by 12.75% of FDFR scores and 7.25% of ISM scores across two
facial benchmarks and two commonly used prompts on average.

Diffusion models, adversarial attack, anti-customization

††ccs: Computing methodologies Computer vision

##  1\. Introduction

In the era of pre-trained generative AI, individuals wield the power of
creating multi-media contents that appears genuinely authentic with just a
single click. Despite the success of GAN- and VAE-based image synthesis
methods(Karras et al., 2020; Patashnik et al., 2021; Xu et al., 2018; Tao et
al., 2022; Razavi et al., 2019), more impressive and controllable results are
achieved by recently proposed diffusion models, such as DALL-E(Ramesh et al.,
2022), Imagen(Saharia et al., 2022) and Stable Diffusion(StabilityAI, 2024).
These diffusion model based text-to-image generation methods can generate
almost any style of image by a simple corresponding text instruction, and show
the unprecedented capacity for producing high-quality images across various
applications.

Figure 1.  Comparison of DreamBooth, Anti-DreamBooth with DisDiff. The first
row shows the unprotected DreamBooth, which learns from the subjects and
generates them into different scenes. The second row shows the protected
results. Protected by Anti-DreamBooth, the face is still identified. Our
DisDiff achieves unidentified or even unrecognized outputs, boosting the
protection performances.

With the users’ desire for image synthesis of their subjects, e.g., daily
supplies, pets or family members, customized image generation steps onto the
stage, with representatives like Textual Inversion(Gal et al., 2022) and
DreamBooth(Ruiz et al., 2023). Leveraging the pre-trained text-to-image
diffusion models, Textual Inversion learns a pseudo-word in the well-editable
word embedding space of text encoder, i.e., $S*$, to represent the newly
provided concept. DreamBooth fine-tunes the diffusion models with a small set
of subject images and a subject-identifier token (e.g., sks) included prompt,
such as ”a photo of sks dog”. Iteratively training large amounts of model
parameters, DreamBooth achieves superior performance compared to Textual
Inversion. More recently, Custom Diffusion(Kumari et al., 2023) fine-tunes the
selected parameters in the attention layers to reduce the memory overhead,
achieving efficient customization.

Despite the convenient editing of users’ specified subjects, these methods
present a dual-edged dilemma. Malicious users exploit this customization to
fabricate synthetic images or videos and spread them on the internet. The
generated fake products(Chen et al., 2020; Yang et al., 2023; Kim et al.,
2022) engender potential security and privacy vulnerabilities for individuals.
In response to defend against this, both passive and proactive protections
have been proposed for safeguarding privacy. Passive protections, commonly
known as DeepFake detection(Zhao et al., 2021; Zhang et al., 2022; Ge et al.,
2022; Iqbal et al., 2023; Wang et al., 2023a; Liao et al., 2023), are employed
to determine the authenticity of images. The detecting models are trained to
discriminate whether the images are real or fake. However, fake images have
been spread before detected and these methods often struggle with novel
synthetic techniques(Wang et al., 2021). Regarding this matter, proactive
protections are proposed with adversarial attacks to disrupt the fake image
synthesis(Yang et al., 2021; Wu et al., 2023a). These applications distort the
fake image generation with noticeable artifacts, thereby providing cues for
detection. As diffusion-based customization methods emerge recently, the
urgency of protecting users’ privacy against these techniques becomes
paramount. As one of the pioneering works, Anti-DreamBooth(Van Le et al.,
2023) aims to disrupt the generation of images produced by DreamBooth.
Specifically, Anti-DreamBooth tries to alternatively learn a surrogate
diffusion model (or utilize a fine-tuned fixed one) and the adversarial
perturbations to improve the attack performances.

Despite the destruction of the visual quality of generated images by Anti-
DreamBooth, the face still exists. This is obvious not only for human
observers (visually) but also for detection algorithms (quantitatively). As
illustrated in Figure 1, the generated images of both DreamBooth and Anti-
DreamBooth are recognized, i.e., there exists an evident face in the image.
Besides, the generated face can even be correctly identified, i.e., being
classified as the same identity by a face recognition algorithm. These
undesired issues of privacy information leakage become the motivation of our
work.

In this paper, we propose DisDiff, a novel adversarial attack method against
diffusion-based customization. We first delve into the training process of
DreamBooth through the lens of the attention mechanism. As training proceeds,
the diffusion model gradually establishes the association between ”sks person”
and the target individual. This association can be reflected by the cross-
attention maps in the UNet(Ronneberger et al., 2015), which serves as the core
guidance of text-image generation. In light of this, we propose a novel Cross-
Attention Erasure module (CAE), to explicitly diminish the cross-attention’s
guiding effects. CAE effectively ”erases” the indicated attention maps and
therefore disrupts the text guidance on image generation. On the other hand,
we explore the impact of the sampling procedure of diffusion models on
adversarial attacks inspired by (Wang et al., 2023c). We compute Hybrid
Quality Scores (HQS) for different timesteps to measure the importance of
these steps on adversarial learning. Then, we introduce the Merit Sampling
Scheduler (MSS) to adaptively modulate the PGD step sizes during attack, i.e.,
at the steps where HQS is large, PGD step size is magnified by MSS and vice
versa. Both CAE and MSS modules are empirically proven to boost the
adversarial attack performances on diffusion-based customizations.

In brief, our contributions are summarised as follows:

1) We propose DisDiff, a proactive adversarial attack method against
diffusion-based customization, to protect users’ privacy.

2) We delve into the image-text relationship and justify its importance on
generation guidance. On this basis, we propose a novel Cross-Attention Erasure
module to ”erase” the subject-identifier token-related attention map.

3) Observing the diffusion sampling process and PGD, we introduce a Merit
Sampling Scheduler, which restricts the perturbation updating step length in a
step-aware manner.

4) Experiments show that DisDiff outperforms the SOTA method by 12.75% of FDFR
scores and 7.25% of ISM scores across two facial benchmarks and commonly used
prompts on average.

##  2\. RELATED WORK

###  2.1. Text-to-image Diffusion

As latent-variable generative models, diffusion models establish a Markov
chain of continuous timesteps to gradually introduce Gaussian noise into the
training data. Afterward, the models learn to reverse the diffusion process
and reconstruct data samples from the induced noises. In response to the
growing demand for multimedia generation, considerable research efforts have
been devoted to exploring text-to-image diffusion models. Stable Diffusion
(SD)(StabilityAI, 2024), rooted in the Latent Diffusion Models(Rombach et al.,
2022), significantly amplifies the scope of text-to-image synthesis
applications. With the input of Gaussian noises and user-elaborated prompts,
SD generates diversified images through the denoising process. It has been
demonstrated that the text prompts serve as an essential controller for image
generation, with even minor modifications leading to significantly different
outcomes. A body of works focuses on the role of image-text relationships in
the generation, which is known as attention maps. For precise SD text-to-image
generation, Prompt-to-Prompt(Hertz et al., 2022) explores cross-attention
layers during the diffusion backward inference process. Attend-and-
Excite(Chefer et al., 2023) modifies the latent codes by maximizing the
dominant attention values for each subject token. Chen et al.(Chen et al.,
2024) explore the roles of attention maps on the forward and backward guidance
and introduce a training-free localized spatial control over newly generated
images.

###  2.2. Diffusion based Customization

Despite the diversity of generated images by diffusion models, users often
seek to synthesize specific concepts for their personal subjects. This task is
named user customization(Brooks et al., 2023; Raj et al., 2023; Li et al.,
2024; Wei et al., 2023) and has been widely studied. LoRA(Hu et al., 2021)
enables the diffusion models for specific styles or tasks by fine-tuning the
extra parameters. This technique allows the model to associate image
representations with the prompts describing them effectively. Textual
Inversion(Gal et al., 2022) harnesses the diffusion models to reflect a novel
concept to a pseudo-word, denoted as $S*$, within the malleable word embedding
space of the text encoder. It allows for the seamless integration of unique
concepts into the generative process, enhancing the model’s ability to produce
tailored and specific imagery. DreamBooth(Ruiz et al., 2023) fine-tunes the
diffusion model with a subject-identifier token consisting prompt (e.g., ”a
photo of sks person”) and several images of the indicated subject. Through
this process, the model becomes ”familiar” with recognizing features
associated with ”sks person,” enabling it to generate various representations
in response to different prompts. Recently, Custom Diffusion(Kumari et al.,
2023) offers further insights into customization techniques. It reveals that
optimizing selected parameters within the text-to-image conditioning mechanism
is not only effective in representing new concepts but also facilitates rapid
adjustments. Despite the convenience of diffusion-based customization, there
exist some potential risks. Malicious users may misuse these tools to invade
privacy, for instance, generating illicit pornographic images or harmful
content. Such misuse highlights the importance of ethical considerations and
robust safeguards in the development of text-to-image synthesis technologies.

###  2.3. Adversarial Attacks on Image Generation

Recognizing the urgency for privacy protection, researchers have introduced
adversarial attacks to defend against malicious image manipulations. Inspired
by adversarial attacks against classification tasks(Madry et al., 2017; Dong
et al., 2018; Zhong and Deng, 2022), Yeh et al.(Yeh et al., 2021) and Ruiz et
al.(Ruiz et al., 2020) aim at distorting or neutralizing image editing
DeepFake techniques. He et al.(He et al., 2022) harness the StyleGAN inversion
technique, encoding the protected images into latent space and adding
perturbations. CMUA-Watermark(Huang et al., 2022) and TAFIM(Aneja et al.,
2022) further train universal watermarks against various image manipulations.
As to the black-box Deepfake scenarios, Huang et al.(Huang et al., 2021)
alternately train the surrogate models and perturbation generators, while
Anti-Forgery(Wang et al., 2022) trains the perturbations in Lab color space.
UnGANable(Li et al., 2023) examines multiple adversarial scenarios and
proposes corresponding methodologies to disrupt StyleGAN inversion-based image
manipulation.

Within the realm of diffusion-based customization for privacy protection,
GLAZE(Shan et al., 2023) and AdvDM(Liang et al., 2023) employ invisible
perturbations on personal images, protecting users from style theft and
painting imitation. Differently, Anti-DreamBooth devises to generate
adversarial noises and distort the outputs of customized diffusion methods,
especially DreamBooth. To overcome the prompt robustness problem, (Wu et al.,
2023b) proposes an Adversarial Decoupling Augmentation Framework to adapt
diverse DreamBooth prompts. SimAC(Wang et al., 2023b) takes a sense of the
perception in the frequency domain of images and leverages a greedy algorithm
to select timesteps. Different from them, our DisDiff sets out from the image-
text relationship and disrupts the internal textual guidance. Besides, we take
into consideration the integration of diffusion sampling and adversarial
learning and introduce the Merit Sampling Scheduler to adaptively restrict the
perturbation updating amplitude.

##  3\. Method

###  3.1. Preliminaries

Stable Diffusion consists of an autoencoder and a conditional UNet(Ronneberger
et al., 2015) denoiser. Firstly, the encoder $\mathcal{E}(\cdot)$ is devised
to map a given image $x\in X$ into a spatial latent code $z=\mathcal{E}(x)$.
The decoder $\mathcal{D}$ is then trained to map the latent code back to the
input image such that $\mathcal{D}(\mathcal{E}(x))\approx x$. Secondly, the
conditional denoiser $\epsilon_{\theta}(\cdot)$ is performed to predict the
added noises guided by the text prompt $y$. At this time, a pre-trained
CLIP(Radford et al., 2021) text encoder $c(\cdot)$ is used to generate text
embeddings. Representing the prompt $y$ as a conditioning vector denoted by
$c(y)$, the diffusion model $\epsilon_{\theta}$ is trained to minimize the
loss function:

(1) $L_{DM}=\mathbb{E}_{z\sim
E(x),y,\epsilon\sim\mathcal{N}(0,\textbf{I}),t}\left\|\epsilon-\epsilon_{\theta}(z_{t},t,c(y))\right\|_{2}^{2}.$

During inference, latent $z_{T}$ is sampled from $\mathcal{N}(0,\textbf{I})$
and progressively denoised to yield the latent $z_{0}$. Subsequently, $z_{0}$
is fed into the decoder to generate the image $x^{\prime}=\mathcal{D}(z_{0})$.

Figure 2.  The overview framework of Disrupting Diffusion. The prompt ”a photo
of sks person” is used for training. At every denoising process, we acquire
the attention maps of the subject to calculate $L_{DB}$ and $L_{CAE}$. Then,
the gradients are aggregated and fed into the Merit Sampling Scheduler, which
is used for PGD attack to update $x_{adv}$.

DreamBooth fine-tunes the diffusion model parameters for user customization.
The training dataset consists of a subject-specific set $X_{s}$ and a class-
specific set $X_{c}$, accompanied by corresponding prompts $y_{s}$ and
$y_{c}$, e.g., ”a photo of sks [class noun]” and ”a photo of [class noun]”,
respectively. $X_{s}$ comprises various personal images, while $X_{c}$ serves
to mitigate model overfitting. Therefore, DreamBooth utilizes a two-part loss
to train the diffusion models:

(2) $\begin{split}L_{DB}=\mathbb{E}_{z\sim E(x_{s}),\epsilon\sim
N(0,\textbf{I}),t}\left\|\epsilon-\epsilon_{\theta}(z_{t},t,c(y_{s}))\right\|_{2}^{2}\\\
\hskip 11.38109pt+\lambda_{DB}\mathbb{E}_{z\sim E(x_{c}),\epsilon\sim
N(0,\textbf{I}),t}\left\|\epsilon-\epsilon_{\theta}(z_{t},t,c(y_{c}))\right\|_{2}^{2},\end{split}$

where $\lambda_{DB}$ represents a balanced hyper-parameter. In the inference
process, users modify the subject-specific prompt to their desire, e.g., ”a
photo of sks [class noun] on the mountain”. The model then generates this
specific subject on the mountain as described.

Adversarial attacks manipulate model $f$ by introducing imperceptible
perturbations to the input data. As to the image generation, the attacker aims
to distort or nullify the generation model’s outputs by an optimal
perturbation $\delta$. The perturbations are bounded within an $\eta$-ball
according to distance metric $\ell_{p}$, where $\eta$ represents the maximum
allowed perturbation magnitude. The goal of adversarial attacks is to maximize
the loss function, ensuring the outputs are different from the ground truth
$y_{true}$. $\delta_{adv}$ is optimized by:

(3) $\delta_{\text{adv}}=\arg\max
L(f(x+\delta),y_{\text{true}}),s.t.\|\delta\|_{p}\leq\eta.$

Projected Gradient Descent (PGD)(Madry et al., 2017) is a widely used method
for adversarial attacks. The perturbations are computed by disrupting the
input along the direction of Eq.3 iteratively. Every iteration process of PGD
updates the adversarial example $x^{\prime}$ as follows:

(4) $x^{\prime}_{0}=x,$ (5)
$x^{\prime}_{k}=\Pi_{x,\eta}(x^{\prime}_{k-1}+\gamma\cdot\text{sgn}(\nabla_{x}L(f(x^{\prime}_{k-1}),y_{\text{true}}))),$

where $\Pi_{x,\eta}(z)$ confines the pixel values of $z$ within the
$\eta$-ball, $\gamma$ represents the step size, and $k$ denotes the number of
iterations.

###  3.2. Cross-Attention Erasure

Motivation. As in the literature(Hertz et al., 2022; Chefer et al., 2023),
cross-attention maps represent the influence of tokens on image pixels, which
control the text-guided image generation in the diffusion model. Thus, we
first delve into the training process of DreamBooth through the lens of
attention maps. Specifically, given a textual guidance composed of sequence
$W=\\{w_{1},w_{2},...,w_{n}\\}$, we derive the corresponding attention maps
$M=\\{m_{1},m_{2},$ $...,m_{n}\\}$, where n is the word number. At timestep
$t$, $m_{t}$ is computed through the diffusion forward process with latent
code $z_{t}$:

(6) $m_{t}=\text{Softmax}\left(\frac{QK^{\top}}{\sqrt{d}}\right),$

where query $Q$ is equal to $W_{Q}\cdot c(y)$, key $K$ is equal to $W_{K}\cdot
c(y)$. $W_{Q}$ and $W_{K}$ are weight parameters of the query and key
projection layers and $d$ is the channel dimension of key and query features.

Figure 3.  Visualizations of cross-attention maps from unprotected DreamBooth
and DisDiff. For the unprotected ones, the diffusion model captures the
subject-identifier token ”sks” (highlighted red areas on the face) and
generates customized images. However, DisDiff erases the model’s attention on
that token and dramatically distorts the model’s outputs.

Notably, we aggregate these attention maps by averaging across all $16\times
16$ attention layers and heads, as they are proved to convey the most semantic
information(Hertz et al., 2022). Besides, it is observed that the original
attention maps may not fully reflect whether an object is generated in the
image(Chefer et al., 2023). In other words, a single patch with high attention
value might originate from partial information passed from the token. To
mitigate this, we further apply a Gaussian filter over $m_{t}$, which ensures
that the attention value of the maximally-activated patch depends on its
neighboring patches, facilitating a smoother attention distribution across the
image.

Figure 3 shows the visualizations of attention maps. As the customization
prompt is characterized by a subject-identifier token $w_{s}$(”sks”) and a
class-identifier token $w_{c}$(”person”), we maintain our focus on their
related attention maps. The red highlighted areas reveal high relativity
between the token and the generated image. Clearly, for unprotected subjects,
the fine-tuned diffusion model successfully associates the subject-identifier
token ”sks” with faces. However, the class-identifier token ”person” becomes
less prominent. That is, ”sks” actually stands on the subject. We compute the
relative energy of the subject-identifier token by:

(7) $E(m_{s})=\frac{\sum_{A\in m_{s}}A^{2}}{\sum_{m_{i}\in M}\sum_{A\in
m_{i}}A^{2}},$

where $m_{s}$ is the attention map of $w_{s}$ and $A$ stands on the pixel
value in the maps. $E(m_{s})$ reflects the energy weight percentage of the
subject-identifier token. To protect personal privacy from customization, we
thereby try to ”erase” the energy associated with the values in $m_{s}$.
Concretely, the proposed Cross-Attention Erasure loss is as follows:

(8) $L_{CAE}=(1-E(m_{s}))^{2}.$

Our adversarial attack focuses on maximizing $L_{cae}$, and the optimal
perturbation $\delta$ can be learned by training procedure in Section 3.4.

The intuition of our CAE module is that after erasing the cross-attention map
of the subject-identifier token (with eliminated highlighted areas), the model
would lose the direction of text guidance. As a result, the generated images
would exclude the identity information or even the subjects themselves. The
protecting results are shown in the last two rows in Figure 3. Compared with
highlighted red areas of unprotected DreamBooth(the first two rows), the
impact of the subject-identifier token on image generation dramatically
decreases. In light of this, the learned perturbations distort image-text
correlations of the diffusion model, affecting unidentified or unrecognized
inference outputs.

###  3.3. Merit Sampling Scheduler

Note that in the adversarial learning procedure of DisDiff, the timestep
sampling process of diffusion models is included. Thus, to evaluate the
importance of steps for adversarial learning, we adopt the Hybrid Quality
Score (HQS) metric inspired by (Wang et al., 2023c). Assuming that $G_{t}$ is
the computed gradients on images, we first calculate the L1 norm of the
gradients by:

(9) $N_{t}=\sum\limits_{i}|G_{t}^{i}|.$

$G_{t}$ is then converted by a softmax function to the confident map $p_{t}$.
The entropy is computed by:

(10) $H_{t}=-\sum\limits_{i}p_{t}^{i}\text{log}p_{t}^{i}.$

Afterward, the sequences $N=\\{N_{1},N_{2},...,N_{T}\\}$ and
$H=\\{H_{1},H_{2},\allowbreak{}...,H_{T}\\}$ are normalized to [0,1] and the
HQS metric is computed as:

(11) $\text{HQS}(t)=\text{norm}(N_{t})-\text{norm}(H_{t}).$

Figure 4 shows the HQS evaluation of various timesteps. High HQS stands on
high values of gradient norm and low entropy, indicating that the model pays
more attention at this timestep and mainly focuses on identity-related areas
(such as faces). During early iterations when HQS is high, larger PGD steps
may be beneficial for adversarial attacks. Conversely, as the HQS decreases,
smaller PGD steps can help fine-tune the generated adversarial samples, as
well as avoid excessive deviation from the original input distribution.

Figure 4.  Analysis of varying timesteps. As the timestep becomes larger, not
only does the HQS metric significantly decrease but also the model pays more
attention to identity-irrelevant information, illustrating that the steps in
the former are more important for perturbation training.

Besides, we also visualize the cross-attention map of the subject-identifier
token for different timesteps. As can be seen, when the timesteps are large,
the model pays more attention to the irrelevant information of the identity.
As the timestep gets smaller, the attention gradually moves to the identity’s
faces. Observations on HQS and attention maps both empirically justify that
the timesteps sampling is essential to adversarial attacks.

Therefore, we resort to adopting a time-dependent function as the Merit
Sampling Scheduler (MSS) to adjust the perturbation updating steps in PGD
adaptively. We empirically design the time-aware decreasing function as:

(12) $h(t)=\frac{1}{2}(cos(\frac{\pi t}{T})+1),$

where $T$ is the max timestep to sample so that the amplitude of $h(t)$ is
limited in [0,1]. In this regard, our proposed MSS dynamically adjusts the
step size of the perturbation updating. The scheduler is then used to be an
enhancement for PGD attacks. Given the overall loss $L$, PGD process in Eq.5
is modified as:

(13) $x^{\prime}_{k}=\Pi_{x,\eta}(x^{\prime}_{k-1}+\gamma\cdot
h(t)\cdot\text{sgn}(\nabla_{x}L(f(x^{\prime}_{k-1}),y_{\text{true}}))).$

By incorporating MSS, we associate adversarial learning with the diffusion
model sampling process. The modified PGD updates the perturbations precisely,
contributing to better attack performances.

###  3.4. Training Procedure

To sum up, the proposed DisDiff combines the DreamBooth loss with the Cross-
Attention Erasure loss as the overall loss:

(14) $L_{DisDiff}=L_{DB}+\lambda L_{CAE},$

where $\lambda$ is a trade-off hyper-parameter. To conduct the adversarial
attack, we utilize modified PGD (Eq.13) and maximize the loss function to
train the perturbations:

(15) $\delta=\underset{\delta}{\text{argmax}}\,L_{DisDiff}.$

We conduct an alternative training strategy similar to (Van Le et al., 2023):
at each epoch, we first adopt a clean image set $X_{c}$ to train the surrogate
model for $t_{1}$ steps. The adversarial example $x^{\prime}$ is then updated
by PGD attack for $t_{2}$ steps and the model is once again trained by the
adversarial examples.

The training process is illustrated in Algorithm 1. For convenience, we omit
the class-specific datasets and prompts of the DreamBooth procedure.

Algorithm 1 Disrupting Diffusion Step

1:Input: Stable Diffusion model $SD$, protected image $X_{adv}$, clean images
batch $X_{cl}$, prompt $W=\\{w_{1},w_{2},...,w_{n}\\}$, scheduler $h(t)$,
surogate model steps $t_{1}$, PGD steps $t_{2}$

2:procedure DBSTEP(SD, X,W)

3: Random sample timestep $t$

4: $X^{\prime},\\_\leftarrow SD(X,W,t)$

5: $L_{DB}\leftarrow MSE(X_{s}^{\prime},X_{s})$

6: $SD\leftarrow SD-\alpha_{DB}\nabla L_{DB}$

7: return $SD$

8:end procedure

9:For $t$ in {1, 2, …, $t_{1}$} :

10: $SD\leftarrow DBSTEP(SD,X_{cl},W)$

11:For $t$ in {1, 2, …, $t_{2}$} :

12: $X_{adv}^{\prime},M_{t}\leftarrow SD(X_{adv},t,W)$

13: $M_{t}\leftarrow\text{Softmax}(M_{t})$

14: $L_{DisDiff}\leftarrow MSE(X^{\prime}_{adv},X_{adv})+\lambda\cdot
L_{CAE}(M_{t})$

15: $X_{adv}\leftarrow X_{adv}+\gamma\cdot
h(t)\cdot\text{sgn}(\nabla_{X_{adv}}L_{DisDiff})$

16:For $t$ in {1, 2, …, $t_{1}$} :

17: $SD\leftarrow DBSTEP(SD,X_{adv},W)$

##  4\. EXPERIMENTS

###  4.1. Experimental Setup

Table 1. The comparison of attack performances on VGGFace2 and CelebA-HQ datasets. Dataset | Method | Reference | “a photo of sks person” | “a dslr portrait of sks person”
---|---|---|---|---
FDFR↑ | ISM↓ | FID↑ | BRISQUE↑ | FDFR↑ | ISM↓ | FID↑ | BRISQUE↑
VGGFace2 | w/o Protect | CVPR’23 | 0.06 | 0.56 | 236.37 | 20.37 | 0.21 | 0.44 | 279.05 | 7.61
AdvDM | ICML’23 | 0.10 | 0.38 | 359.65 | 17.39 | 0.11 | 0.29 | 397.64 | 27.97
Anti-DB | ICCV’23 | 0.62 | 0.32 | 462.12 | 37.10 | 0.72 | 0.27 | 448.98 | 38.89
DisDiff | —— | 0.77 | 0.27 | 476.28 | 42.46 | 0.95 | 0.06 | 473.38 | 41.26
CelebA-HQ | w/o Protect | CVPR’23 | 0.07 | 0.63 | 154.63 | 13.15 | 0.30 | 0.46 | 221.89 | 8.75
AdvDM | ICML’23 | 0.06 | 0.59 | 197.59 | 24.55 | 0.30 | 0.42 | 235.47 | 16.88
Anti-DB | ICCV’23 | 0.56 | 0.44 | 386.06 | 41.58 | 0.48 | 0.33 | 384.80 | 35.86
DisDiff | —— | 0.62 | 0.40 | 412.19 | 44.98 | 0.55 | 0.34 | 400.38 | 38.35

Evaluation Benchmarks. We quantitatively evaluate our approach on two
benchmarks: CelebA-HQ(Liu et al., 2015) and VGGFace2(Cao et al., 2018).
CelebA-HQ comprises 30,000 images at a resolution of 1024 × 1024. VGGFace2
contains approximately 3.31 million images of 9,131 persons. For each dataset,
we choose 50 identities as the protecting subjects. 8 different images are
prepared for each subject and divided equally into two subsets: the clean
image set and the target protection set. All images undergo center-cropping
and resizing procedures, resulting in a uniform resolution of 512 × 512.

DreamBooth and Adversarial Attack Procedures. We address three versions of
pre-trained SD from HuggingFace(Face, 2024): v1.4, v1.5 and v2.1. For
DreamBooth, the text-encoder and UNet model are trained with a batch size of 2
and the learning rate of $5\times 10^{-7}$ for 1,000 training steps. The
prompt is ”a photo of sks person” for the subject images and ”a photo of
person” for class-specific datasets. The PGD attack is configured with
$\gamma$ = 0.005 and a default noise budget $\eta$ = 0.05 for VGGFace2 and
0.07 for CelebA-HQ respectively. We train the perturbations by 50 iterations,
each containing 3 steps of surrogate model training and 6 steps of
perturbation training. The hyper-parameter $\lambda$ in $L_{DisDiff}$ is set
to 0.1 for both datasets.

Figure 5. Comparison under other inference prompts. Four rows show different
image edit prompts: distance, expression, action, and location, respectively.

Evaluation Metrics. We fine-tune the diffusion model by DreamBooth with our
protected images and generate 16 images for each identity and testing prompt.
These images are then evaluated by a set of metrics. We utilize two widely
used image quality metrics, FID(Heusel et al., 2017) and BRISQUE(Mittal et
al., 2012), to test the disrupting results. On the other hand, images
generated from successfully disrupted DreamBooth models may lack detectable
faces, which we quantify as the Face Detection Failure Rate (FDFR), measured
using the RetinaFace detector(Deng et al., 2020). We also extract face
recognition embeddings using the ArcFace recognizer(Deng et al., 2019) and
compute the cosine distance to the average face embedding of the entire user’s
clean image set, referred to as Identity Score Matching (ISM).

###  4.2. Comparison with SOTAs

We conduct comparisons with two SOTA anti-customization baselines: mist-v3
version of AdvDM(Liang et al., 2023) and Anti-DreamBooth(Van Le et al., 2023).
For a fair comparison, we reproduce their source codes and train adversarial
examples with equivalent noise budgets. These protected examples are then used
to fine-tune the diffusion models (DreamBooth), with the prompt ”a photo of
sks person.” Then, the trained diffusion models are tested by prompts ”a photo
of sks person” and ”a dslr portrait of sks person”. As can be seen in Table 1,
our method demonstrates notable performances across four metrics and two
prompts.

Figure 6.  Ablation study of (a) the proposed module CAE and MSS, (b)
different schedulers.  Figure 7. Visualizations of identity images, attention
maps, and generated images before and after protecting.

Specifically, higher FDFR rates signify a decreasing number of detected faces,
while lower ISM rates indicate less similarity with the original subject. As
to the image quality, increased FID and BRISQUE rates emphasize the lower
image quality, resulting in significant distortions of DreamBooth outputs.

To further verify the efficacy of our DisDiff, we also test our method under
various prompts with distance, expression, action, and location descriptions,
respectively. As shown in Figure 5, DreamBooth edits the images as the prompts
describe. AdvDM pushes the outputs to the target image so that the resulting
outputs show a similar texture to that image. Although Anti-DreamBooth
successfully distorts the output images, the identity is still recognizable.
Our proposed DisDiff leads to more unrecognized faces and unidentified
subjects by directly disrupting the cross-attention module, which greatly
boosts the protecting performances.

###  4.3. Ablation Study

Impact of Cross-Attention Erasure. To testify to the impacts of our proposed
Cross-Attention Erasure, we visualize the attention maps and the corresponding
generated images. As shown in the first row of Figure 7, highlighted red areas
occur on the identity face for the token ”sks”, which indicates that the
diffusion model pays much more attention to the learned identity with ”sks”.
This is intuitive since DreamBooth progressively makes the token ”sks” and the
special person connected closely. This situation still exists when the
identity is protected by AdvDM and Anti-DreamBooth, which is undesired for
privacy protection. Compared with them, DisDiff successfully erases the impact
of ”sks”. That is, the diffusion model ignores the token ”sks” and its
guidance on generation, thus has no idea about whom to generate. The images
protected with our method thus exhibit greater blurriness and
indistinctiveness.

Table 2. Attack performances with different noise budget $\eta$ and * indicates the default setting. $\eta$ | LPIPS | FDFR↑ | ISM↓ | FID↑ | BRISQUE↑
---|---|---|---|---|---
0 | - | 0.06 | 0.56 | 236.37 | 20.37
0.01 |  $\approx$ 0 | 0.08 | 0.53 | 271.92 | 33.93
0.03 | 0.01 | 0.59 | 0.37 | 426.68 | 40.20
0.05$*$ | 0.03 | 0.77 | 0.27 | 476.28 | 42.46
0.07 | 0.07 | 0.82 | 0.26 | 485.02 | 43.63
0.09 | 0.11 | 0.85 | 0.16 | 494.51 | 40.83

Module and Scheduler Selection. We conduct the ablation study of the proposed
Cross-Attention Erasure (CAE) and Merit Sampling Scheduler (MSS) modules. As
shown in Figure 6(a), we set the metrics of baseline method Anti-DreamBooth as
1 and calculate the relative magnitude of DisDiff. Clearly, when utilizing CAE
or MSS, the lower ISM and higher FDFR illustrate that the customization
outputs become unidentified and unrecognized, indicating DisDiff’s
effectiveness. Also, we apply two widely used decreasing functions to serve as
the scheduler in MSS: the logarithm decreasing function111The logarithm
decreasing function is $1-\frac{log(t+1)}{log(T+1)}$, where T is the max
sampling step. and diffusion models sampling sequence $\bar{\alpha_{t}}$. We
set the scheduler in Eq.12 as the baseline and compare the attack performances
in Figure 6(b). Finally, we select the cosine function in Eq.12 as the
default, which achieves the lowest ISM rate.

Table 3. Attack performances on other diffusion customization methods on VGGFace2.  | Method | FDFR↑ | ISM↓ | FID↑ | BRISQUE↑
---|---|---|---|---|---
LoRA | w/o Protect | 0.11 | 0.43 | 248.05 | 17.31
Anti-DB | 0.68 | 0.36 | 403.38 | 44.38
DisDiff | 0.73 | 0.21 | 418.70 | 44.70
TI | w/o Protect | 0.04 | 0.42 | 222.70 | 7.59
Anti-DB | 0.09 | 0.27 | 289.66 | 39.37
DisDiff | 0.14 | 0.24 | 308.77 | 41.23
Table 4. Attack performances on different generator versions on VGGFace2. ”Self” means the perturbation training and DreamBooth process share the same surrogate model, while ”SD v2.1” means the perturbation training with SD v2.1 and DreamBooth with other versions. Surrogate | Method | SD v1.4 | SD v1.5
---|---|---|---
FDFR↑ | ISM↓ | FID↑ | BRISQUE↑ | FDFR↑ | ISM↓ | FID↑ | BRISQUE↑
w/o Protect | 0.09 | 0.56 | 231.13 | 19.79 | 0.09 | 0.55 | 217.22 | 18.33
self | Anti-DB | 0.88 | 0.07 | 511.59 | 42.77 | 0.93 | 0.07 | 517.03 | 46.09
DisDiff | 0.96 | 0.04 | 522.57 | 46.26 | 0.99 | 0.05 | 512.70 | 55.90
v2.1 | Anti-DB | 0.89 | 0.10 | 495.50 | 38.25 | 0.90 | 0.12 | 506.64 | 44.02
DisDiff | 0.99 | 0.02 | 505.66 | 44.60 | 0.96 | 0.08 | 510.93 | 50.83
Table 5. Attack performances on VGGFace2 when the DreamBooth training prompt and subject-identifier token are different from the perturbation training stage. $S*$ is ”t@t” for the first row and ”sks” for the second row. DreamBooth prompt | Method | ”a photo of $S_{*}$ person” | ”a dslr portrait of $S_{*}$ person”
---|---|---|---
FDFR↑ | ISM↓ | FID↑ | BRISQUE↑ | FDFR↑ | ISM↓ | FID↑ | BRISQUE↑
”a dslr portrait of sks person” | Anti-DB | 0.01 | 0.16 | 279.37 | 19.74 | 0.57 | 0.30 | 459.65 | 39.25
DisDiff | 0.05 | 0.20 | 270.47 | 21.95 | 0.85 | 0.21 | 476.27 | 40.14
”sks” → ”t@t” | Anti-DB | 0.60 | 0.34 | 454.53 | 40.61 | 0.41 | 0.31 | 396.92 | 34.50
DisDiff | 0.73 | 0.28 | 464.09 | 42.24 | 0.71 | 0.25 | 414.26 | 38.87

Noise Budget. The noise budget $\eta$ represents the permissible magnitude of
perturbations, and a large noise budget is easily perceptible by humans. LPIPS
is used to measure the image quality before and after attack. As shown in
Table 2, DisDiff shows high FID and BRISQUE scores when the budget is as small
as 0.03. Besides, LPIPS is still low when we set $\eta=0.05$ as the default,
meaning that the perturbation is still invisible. Moreover, the attack
performances become stronger as the budget increases, which is also reasonable
since the larger the perturbation is, the greater the attack performances can
be achieved.

###  4.4. Robust Analysis

Attacks on different customization methods. To verify our protection
generality across various generation methods, we reproduce wildly used
customization methods: Low-rank Adaptation (LoRA)(Hu et al., 2021), Textual
Inversion (TI)(Gal et al., 2022) and Custom Diffusion(Kumari et al., 2023).
However, Custom Diffusion exhibits suboptimal performance when trained by
limited subject faces. We train customization with LoRA and TI and conduct
adversarial attacks with Anti-DreamBooth and DisDiff. As can be seen in Table
3, compared to unprotected DreamBooth, both Anti-DreamBooth and DisDiff
successfully attack these two customization methods. DisDiff shows better
evaluation scores, indicating the robustness of protection ability across
different customization methods.

Attacks on different generators. Considering the potential malicious uses of
DreamBooth across different diffusion model generators, we conduct experiments
to assess the impact. As shown in Table 4, we first test under the self-
surrogate setting (indicated ”self”), where the perturbation training and
DreamBooth models are the same version. Experiments show that DisDiff achieves
better performances than Anti-DreamBooth and generalizes well on SD v1.4 and
v1.5. Then, we test the generated perturbations robustness under different
generators (indicated ”v2.1”). We employ the adversarial examples generated
with SD v2.1 to train DreamBooth under v1.4 and v1.5. The FDFR approaches 1.0
and ISM approaches 0, indicating minimal faces generated. These results
illustrate that the adversarial examples perform well against different
generators.

Attacks while prompt or subject-identifier mismatching. Assuming that the
adversarial learning prompts differ from the ones used to train DreamBooth, we
conduct experiments to test the robustness, as illustrated in Table 5. In the
first row, we employ ”a photo of sks person” for adversarial learning and ”a
photo of a dslr portrait of sks person” for DreamBooth, conducting inference
for both. DisDiff and Anti-DreamBooth perform poorly when confronted with the
prompt ”a photo of sks person” due to prompt mismatching. However, when
presented with the prompt ”a dslr portrait of sks person”, DisDiff
demonstrates superior performances. This is partially due to that the training
prompt becomes more complicated and the models are overfitting.

We also evaluate the results by changing the DreamBooth subject-identifier
token to ”t@t”, as in the second row. Our DisDiff remains well-generalized to
”t@t”. The reason is that we apply the softmax function in CAE. The summary of
all the softmax attention maps for every pixel is 1. After erasing the
attention map of ”sks”, the values of other tokens become larger. As a result,
the attention map of substitute token ”t@t” is erased even though it is not
involved in perturbation training. To sum up, DisDiff is robust to different
DreamBooth prompts and subject-identifier tokens.

Attacks after image pre-processings. Before being released to the Internet,
images are often pre-processed by image compression to save the storage
overhead. JPEG Compression is a technique commonly used for digital images
which reduces redundant information in the image and Gaussian Blur is also
widely used to reduce image noise and details. We find that the attack
performances indeed decrease facing these methods in Table 6. This is
acceptable due to their ability of adversarial purification. However, DisDiff
can still achieve high BRISQUE scores, thus maintaining certain robustness
against image pre-processing.

Table 6. Attack performances after Gaussian Blur and JPEG compression on VGGFace2. Method | FDFR↑ | ISM↓ | FID↑ | BRISQUE↑
---|---|---|---|---
Disrupting Diffusion | 0.77 | 0.27 | 476.28 | 42.46
Gaussian Blur $K=3$ | 0.41 | 0.45 | 401.88 | 43.02
Gaussian Blur $K=5$ | 0.35 | 0.44 | 380.02 | 41.94
Gaussian Blur $K=7$ | 0.45 | 0.40 | 419.42 | 42.60
JPEG Comp. $Q=30$ | 0.05 | 0.53 | 247.59 | 34.17
JPEG Comp. $Q=50$ | 0.13 | 0.48 | 296.86 | 37.52
JPEG Comp. $Q=70$ | 0.33 | 0.44 | 352.31 | 40.48
No attack, no preproc. | 0.06 | 0.56 | 236.37 | 20.37

##  5\. Conclusion and Future work

To protect privacy from malicious diffusion-based customization methods, we
propose a novel adversarial attack method, Disrupting Diffusion (DisDiff). We
track the attention maps during generation and propose a Cross-Attention
Erasure module to disrupt these maps. We also introduce a time-aware Merit
Sampling Scheduler to adaptively adjust the PGD steps. DisDiff successfully
disrupts customization’s output as unrecognizable and unidentifiable,
achieving better performance than state-of-the-art adversarial attacks.

With the extensive research of diffusion models, there has been a rapid
evolution in the models and customization techniques. In light of this, our
research will focus on the latest emerging diffusion models(Podell et al.,
2023; Pernias et al., 2023; Peebles and Xie, 2023) and customization
methods(Huang et al., 2024) to extend our DisDiff. At the same time, the
perturbation robustness across various prompts and image pre-processings
remains to be explored.

## References

  * (1)
  * Aneja et al. (2022) Shivangi Aneja, Lev Markhasin, and Matthias Nießner. 2022.  TAFIM: targeted adversarial attacks against facial image manipulations. In _European Conference on Computer Vision_. Springer, 58–75.
  * Brooks et al. (2023) Tim Brooks, Aleksander Holynski, and Alexei A Efros. 2023.  Instructpix2pix: Learning to follow image editing instructions. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 18392–18402.
  * Cao et al. (2018) Qiong Cao, Li Shen, Weidi Xie, Omkar M Parkhi, and Andrew Zisserman. 2018.  Vggface2: A dataset for recognising faces across pose and age. In _2018 13th IEEE international conference on automatic face & gesture recognition (FG 2018)_. IEEE, 67–74.
  * Chefer et al. (2023) Hila Chefer, Yuval Alaluf, Yael Vinker, Lior Wolf, and Daniel Cohen-Or. 2023.  Attend-and-excite: Attention-based semantic guidance for text-to-image diffusion models.  _ACM Transactions on Graphics (TOG)_ 42, 4 (2023), 1–10.
  * Chen et al. (2024) Minghao Chen, Iro Laina, and Andrea Vedaldi. 2024.  Training-free layout control with cross-attention guidance. In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_. 5343–5353.
  * Chen et al. (2020) Renwang Chen, Xuanhong Chen, Bingbing Ni, and Yanhao Ge. 2020.  Simswap: An efficient framework for high fidelity face swapping. In _Proceedings of the 28th ACM International Conference on Multimedia_. 2003–2011.
  * Deng et al. (2020) Jiankang Deng, Jia Guo, Evangelos Ververas, Irene Kotsia, and Stefanos Zafeiriou. 2020.  Retinaface: Single-shot multi-level face localisation in the wild. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 5203–5212.
  * Deng et al. (2019) Jiankang Deng, Jia Guo, Niannan Xue, and Stefanos Zafeiriou. 2019.  Arcface: Additive angular margin loss for deep face recognition. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 4690–4699.
  * Dong et al. (2018) Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. 2018.  Boosting adversarial attacks with momentum. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 9185–9193.
  * Face (2024) Hugging Face. 2024.  .  https://huggingface.co/
  * Gal et al. (2022) Rinon Gal, Yuval Alaluf, Yuval Atzmon, Or Patashnik, Amit H Bermano, Gal Chechik, and Daniel Cohen-Or. 2022.  An image is worth one word: Personalizing text-to-image generation using textual inversion.  _arXiv preprint arXiv:2208.01618_ (2022).
  * Ge et al. (2022) Shiming Ge, Fanzhao Lin, Chenyu Li, Daichi Zhang, Weiping Wang, and Dan Zeng. 2022.  Deepfake video detection via predictive representation learning.  _ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM)_ 18, 2s (2022), 1–21.
  * He et al. (2022) Ziwen He, Wei Wang, Weinan Guan, Jing Dong, and Tieniu Tan. 2022.  Defeating deepfakes via adversarial visual reconstruction. In _Proceedings of the 30th ACM International Conference on Multimedia_. 2464–2472.
  * Hertz et al. (2022) Amir Hertz, Ron Mokady, Jay Tenenbaum, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or. 2022.  Prompt-to-prompt image editing with cross attention control.  _arXiv preprint arXiv:2208.01626_ (2022).
  * Heusel et al. (2017) Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. 2017.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  _Advances in Neural Information Processing Systems_ 30 (2017).
  * Hu et al. (2021) Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2021.  Lora: Low-rank adaptation of large language models.  _arXiv preprint arXiv:2106.09685_ (2021).
  * Huang et al. (2022) Hao Huang, Yongtao Wang, Zhaoyu Chen, Yuze Zhang, Yuheng Li, Zhi Tang, Wei Chu, Jingdong Chen, Weisi Lin, and Kai-Kuang Ma. 2022.  Cmua-watermark: A cross-model universal adversarial watermark for combating deepfakes. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36. 989–997.
  * Huang et al. (2024) Mengqi Huang, Zhendong Mao, Mingcong Liu, Qian He, and Yongdong Zhang. 2024.  RealCustom: Narrowing Real Text Word for Real-Time Open-Domain Text-to-Image Customization.  _arXiv preprint arXiv:2403.00483_ (2024).
  * Huang et al. (2021) Qidong Huang, Jie Zhang, Wenbo Zhou, Weiming Zhang, and Nenghai Yu. 2021.  Initiative defense against facial manipulation. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 1619–1627.
  * Iqbal et al. (2023) Farkhund Iqbal, Ahmed Abbasi, Abdul Rehman Javed, Ahmad Almadhor, Zunera Jalil, Sajid Anwar, and Imad Rida. 2023.  Data augmentation-based novel deep learning method for deepfaked images detection.  _ACM Transactions on Multimedia Computing, Communications and Applications_ (2023).
  * Karras et al. (2020) Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. 2020.  Analyzing and improving the image quality of stylegan. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 8110–8119.
  * Kim et al. (2022) Jiseob Kim, Jihoon Lee, and Byoung-Tak Zhang. 2022.  Smooth-swap: A simple enhancement for face-swapping with smoothness. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 10779–10788.
  * Kumari et al. (2023) Nupur Kumari, Bingliang Zhang, Richard Zhang, Eli Shechtman, and Jun-Yan Zhu. 2023.  Multi-concept customization of text-to-image diffusion. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 1931–1941.
  * Li et al. (2024) Dongxu Li, Junnan Li, and Steven Hoi. 2024.  Blip-diffusion: Pre-trained subject representation for controllable text-to-image generation and editing.  _Advances in Neural Information Processing Systems_ 36 (2024).
  * Li et al. (2023) Zheng Li, Ning Yu, Ahmed Salem, Michael Backes, Mario Fritz, and Yang Zhang. 2023.  $\\{$UnGANable$\\}$: Defending Against $\\{$GAN-based$\\}$ Face Manipulation. In _32nd USENIX Security Symposium (USENIX Security 23)_. 7213–7230.
  * Liang et al. (2023) Chumeng Liang, Xiaoyu Wu, Yang Hua, Jiaru Zhang, Yiming Xue, Tao Song, Zhengui Xue, Ruhui Ma, and Haibing Guan. 2023.  Adversarial example does good: Preventing painting imitation from diffusion models via adversarial examples.  _arXiv preprint arXiv:2302.04578_ (2023).
  * Liao et al. (2023) Xin Liao, Yumei Wang, Tianyi Wang, Juan Hu, and Xiaoshuai Wu. 2023.  FAMM: Facial muscle motions for detecting compressed deepfake videos over social networks.  _IEEE Transactions on Circuits and Systems for Video Technology_ (2023).
  * Liu et al. (2015) Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. 2015.  Deep learning face attributes in the wild. In _Proceedings of the IEEE International Conference on Computer Vision_. 3730–3738.
  * Madry et al. (2017) Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. 2017.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ (2017).
  * Mittal et al. (2012) Anish Mittal, Anush Krishna Moorthy, and Alan Conrad Bovik. 2012.  No-reference image quality assessment in the spatial domain.  _IEEE Transactions on Image Processing_ 21, 12 (2012), 4695–4708.
  * Patashnik et al. (2021) Or Patashnik, Zongze Wu, Eli Shechtman, Daniel Cohen-Or, and Dani Lischinski. 2021.  Styleclip: Text-driven manipulation of stylegan imagery. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 2085–2094.
  * Peebles and Xie (2023) William Peebles and Saining Xie. 2023.  Scalable diffusion models with transformers. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 4195–4205.
  * Pernias et al. (2023) Pablo Pernias, Dominic Rampas, Mats Leon Richter, Christopher Pal, and Marc Aubreville. 2023.  Würstchen: An Efficient Architecture for Large-Scale Text-to-Image Diffusion Models. In _The Twelfth International Conference on Learning Representations_.
  * Podell et al. (2023) Dustin Podell, Zion English, Kyle Lacey, Andreas Blattmann, Tim Dockhorn, Jonas Müller, Joe Penna, and Robin Rombach. 2023.  Sdxl: Improving latent diffusion models for high-resolution image synthesis.  _arXiv preprint arXiv:2307.01952_ (2023).
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021\.  Learning transferable visual models from natural language supervision. In _International Conference on Machine Learning_. PMLR, 8748–8763.
  * Raj et al. (2023) Amit Raj, Srinivas Kaza, Ben Poole, Michael Niemeyer, Nataniel Ruiz, Ben Mildenhall, Shiran Zada, Kfir Aberman, Michael Rubinstein, Jonathan Barron, et al. 2023\.  Dreambooth3d: Subject-driven text-to-3d generation. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 2349–2359.
  * Ramesh et al. (2022) Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. 2022.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ 1, 2 (2022), 3.
  * Razavi et al. (2019) Ali Razavi, Aaron Van den Oord, and Oriol Vinyals. 2019.  Generating diverse high-fidelity images with vq-vae-2.  _Advances in Neural Information Processing Systems_ 32 (2019).
  * Rombach et al. (2022) Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. 2022.  High-resolution image synthesis with latent diffusion models. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 10684–10695.
  * Ronneberger et al. (2015) Olaf Ronneberger, Philipp Fischer, and Thomas Brox. 2015.  U-net: Convolutional networks for biomedical image segmentation. In _Medical image computing and computer-assisted intervention–MICCAI 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18_. Springer, 234–241.
  * Ruiz et al. (2020) Nataniel Ruiz, Sarah Adel Bargal, and Stan Sclaroff. 2020.  Disrupting deepfakes: Adversarial attacks against conditional image translation networks and facial manipulation systems. In _Computer Vision–ECCV 2020 Workshops: Glasgow, UK, August 23–28, 2020, Proceedings, Part IV 16_. Springer, 236–251.
  * Ruiz et al. (2023) Nataniel Ruiz, Yuanzhen Li, Varun Jampani, Yael Pritch, Michael Rubinstein, and Kfir Aberman. 2023.  Dreambooth: Fine tuning text-to-image diffusion models for subject-driven generation. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 22500–22510.
  * Saharia et al. (2022) Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. 2022\.  Photorealistic text-to-image diffusion models with deep language understanding.  _Advances in Neural Information Processing Systems_ 35 (2022), 36479–36494.
  * Shan et al. (2023) Shawn Shan, Jenna Cryan, Emily Wenger, Haitao Zheng, Rana Hanocka, and Ben Y Zhao. 2023.  Glaze: Protecting Artists from Style Mimicry by $\\{$Text-to-Image$\\}$ Models. In _32nd USENIX Security Symposium (USENIX Security 23)_. 2187–2204.
  * StabilityAI (2024) StabilityAI. 2024.  Stable Diffusion.  Hugging Face Model Hub.  https://huggingface.co/stabilityai
  * Tao et al. (2022) Ming Tao, Hao Tang, Fei Wu, Xiao-Yuan Jing, Bing-Kun Bao, and Changsheng Xu. 2022.  Df-gan: A simple and effective baseline for text-to-image synthesis. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 16515–16525.
  * Van Le et al. (2023) Thanh Van Le, Hao Phung, Thuan Hoang Nguyen, Quan Dao, Ngoc N Tran, and Anh Tran. 2023.  Anti-DreamBooth: Protecting users from personalized text-to-image synthesis. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 2116–2127.
  * Wang et al. (2023b) Feifei Wang, Zhentao Tan, Tianyi Wei, Yue Wu, and Qidong Huang. 2023b.  SimAC: A Simple Anti-Customization Method against Text-to-Image Synthesis of Diffusion Models.  _arXiv preprint arXiv:2312.07865_ (2023).
  * Wang et al. (2023c) Luozhou Wang, Shuai Yang, Shu Liu, and Ying-cong Chen. 2023c.  Not All Steps are Created Equal: Selective Diffusion Distillation for Image Manipulation. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 7472–7481.
  * Wang et al. (2022) Run Wang, Ziheng Huang, Zhikai Chen, Li Liu, Jing Chen, and Lina Wang. 2022.  Anti-forgery: Towards a stealthy and robust deepfake disruption attack via adversarial perceptual-aware perturbations.  _arXiv preprint arXiv:2206.00477_ (2022).
  * Wang et al. (2021) Run Wang, Felix Juefei-Xu, Meng Luo, Yang Liu, and Lina Wang. 2021.  Faketagger: Robust safeguards against deepfake dissemination via provenance tracking. In _Proceedings of the 29th ACM International Conference on Multimedia_. 3546–3555.
  * Wang et al. (2023a) Tianyi Wang, Harry Cheng, Kam Pui Chow, and Liqiang Nie. 2023a.  Deep convolutional pooling transformer for deepfake detection.  _ACM Transactions on Multimedia Computing, Communications and Applications_ 19, 6 (2023), 1–20.
  * Wei et al. (2023) Yuxiang Wei, Yabo Zhang, Zhilong Ji, Jinfeng Bai, Lei Zhang, and Wangmeng Zuo. 2023.  Elite: Encoding visual concepts into textual embeddings for customized text-to-image generation. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 15943–15953.
  * Wu et al. (2023b) Ruijia Wu, Yuhang Wang, Huafeng Shi, Zhipeng Yu, Yichao Wu, and Ding Liang. 2023b.  Towards prompt-robust face privacy protection via adversarial decoupling augmentation framework.  _arXiv preprint arXiv:2305.03980_ (2023).
  * Wu et al. (2023a) Xiaoshuai Wu, Xin Liao, and Bo Ou. 2023a.  Sepmark: Deep separable watermarking for unified source tracing and deepfake detection. In _Proceedings of the 31st ACM International Conference on Multimedia_. 1190–1201.
  * Xu et al. (2018) Tao Xu, Pengchuan Zhang, Qiuyuan Huang, Han Zhang, Zhe Gan, Xiaolei Huang, and Xiaodong He. 2018.  Attngan: Fine-grained text to image generation with attentional generative adversarial networks. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 1316–1324.
  * Yang et al. (2021) Chaofei Yang, Leah Ding, Yiran Chen, and Hai Li. 2021.  Defending against gan-based deepfake attacks via transformation-aware adversarial faces. In _2021 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 1–8.
  * Yang et al. (2023) Jiachen Yang, Chen Cheng, Shuai Xiao, Guipeng Lan, and Jiabao Wen. 2023.  High Fidelity Face-Swapping With Style ConvTransformer and Latent Space Selection.  _IEEE Transactions on Multimedia_ (2023).
  * Yeh et al. (2021) Chin-Yuan Yeh, Hsi-Wen Chen, Hong-Han Shuai, De-Nian Yang, and Ming-Syan Chen. 2021.  Attack as the best defense: Nullifying image-to-image translation gans via limit-aware adversarial attack. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 16188–16197.
  * Zhang et al. (2022) Daichi Zhang, Fanzhao Lin, Yingying Hua, Pengju Wang, Dan Zeng, and Shiming Ge. 2022.  Deepfake video detection with spatiotemporal dropout transformer. In _Proceedings of the 30th ACM International Conference on Multimedia_. 5833–5841.
  * Zhao et al. (2021) Hanqing Zhao, Wenbo Zhou, Dongdong Chen, Tianyi Wei, Weiming Zhang, and Nenghai Yu. 2021.  Multi-attentional deepfake detection. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 2185–2194.
  * Zhong and Deng (2022) Yaoyao Zhong and Weihong Deng. 2022.  Opom: Customized invisible cloak towards face privacy protection.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 45, 3 (2022), 3590–3603.


The Open University of<EMAIL_ADDRESS>https://orcid.org/0000-0002-6629-3243 Zeev Nutov [100]Theory of computation
Design and analysis of algorithms

###### Acknowledgements.

# Extending the primal-dual 2-approximation algorithm beyond uncrossable set
families

Zeev Nutov

###### Abstract

A set family ${\cal F}$ is uncrossable if $A\cap B,A\cup B\in{\cal F}$ or
$A\setminus B,B\setminus A\in{\cal F}$ for any $A,B\in{\cal F}$. A classic
result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993:708-717] states
that the problem of covering an uncrossable set family by a min-cost edge set
admits approximation ratio $2$, by a primal-dual algorithm. They asked whether
this result extends to a larger class of set families and combinatorial
optimization problems. We define a new class of semi-uncrossable set families,
when for any $A,B\in{\cal F}$ we have that $A\cap B\in{\cal F}$ and one of
$A\cup B,A\setminus B,B\setminus A$ is in ${\cal F}$, or $A\setminus
B,B\setminus A\in{\cal F}$. We will show that the Williamson et al. algorithm
extends to this new class of families and identify several “non-uncrossable”
algorithmic problems that belong to this class. In particular, we will show
that the union of an uncrossable family and a monotone family, or of an
uncrossable family that has the disjointness property and a proper family, is
a semi-uncrossable family, that in general is not uncrossable. For example,
our result implies approximation ratio $2$ for the problem of finding a min-
cost subgraph $H$ such that $H$ contains a Steiner forest and every connected
component of $H$ contains at least $k$ nodes from a given set $T$ of
terminals.

###### keywords:

primal dual algorithm, uncrossable set family, approximation algorithm

##  1 Introduction

Let $G=(V,E)$ be graph. For $J\subseteq E$ and $S\subseteq V$ let
$\delta_{J}(S)$ denote the set of edges in $J$ with one end in $S$ and the
other in $V\setminus S$, and let $d_{J}(S)=|\delta_{J}(S)|$ be their number.
An edge set $J$ covers $S$ if $d_{J}(S)\geq 1$. Consider the following
problem:

Set Family Edge Cover
Input: A graph $G=(V,E)$ with edge costs $\\{c_{e}:e\in E\\}$ and a set family
${\cal F}$ on $V$.
Output: A min-cost edge set $J\subseteq E$ such that $d_{J}(S)\geq 1$ for all
$S\in{\cal F}$.

In this problem the set family ${\cal F}$ may not given explicitly, but we
will require that some queries related to ${\cal F}$ can be answered in time
polynomial in $n=|V|$. Specifically, following [8], we will require that for
any edge set $I$, the inclusion minimal members of the residual family ${\cal
F}^{I}=\\{S\in{\cal F}:d_{I}(S)=0\\}$ of ${\cal F}$ can be computed in time
polynomial in $n=|V|$. We will also assume that $V,\emptyset\notin{\cal F}$,
as otherwise the problem has no feasible solution.

Various types of set families were considered in the literature, classified
according to the conditions they satisfy. In this paper we will focus on the
following four conditions:

Monotonicity $\emptyset\neq S^{\prime}\subseteq S$ |  $\in{\cal F}$ |  $\Longrightarrow$ |  $S^{\prime}\in{\cal F}$
---|---|---|---
Symmetry $S$ |  $\in{\cal F}$ |  $\Longrightarrow$ |  $\bar{S}\in{\cal F}$, where $\bar{S}=V\setminus S$.
Disjointness $\emptyset\neq S^{\prime}\subseteq S$ |  $\in{\cal F}$ |  $\Longrightarrow$ |  $S^{\prime}\in{\cal F}$ or $S\setminus S^{\prime}\in{\cal F}$
Uncrossability $A,B$ |  $\in{\cal F}$ |  $\Longrightarrow$ |  $A\cap B,A\cup B\in{\cal F}$ or $A\setminus B,B\setminus A\in{\cal F}$

We note that in the paper of Goemans and Williamson [5], the disjointness
property was defined as follows: if $A,B$ are disjoint and $A\cup B\in{\cal
F}$ then $A\in{\cal F}$ or $B\in{\cal F}$. For $A=S^{\prime}$ and
$B=S\setminus S^{\prime}$ this is equivalent to the definition given here. Let
us say that a set-family ${\cal F}$ is:

  * •

Symmetric if the Symmetry Condition holds for all $S\in{\cal F}$.

  * •

Monotone if the Monotonicity Condition holds for all $\emptyset\neq
S^{\prime}\subseteq S\in{\cal F}$.

  * •

Disjointness compliable if the Disjointness Condition holds for all
$\emptyset\neq S^{\prime}\subseteq S\in{\cal F}$.

  * •

Uncrossable if the Uncrossability Condition holds for all $A,B\in{\cal F}$.

A set family is proper if it is both symmetric and disjointness compliable. It
is not hard to see the following:

  * •

If ${\cal F}$ is monotone then ${\cal F}$ is disjointness compliable and
uncrossable.

  * •

If ${\cal F}$ is proper then ${\cal F}$ is uncrossabile.

Agrawal, Klein and Ravi [1] designed and analyzed a primal-dual approximation
algorithm for the Steiner Forest problem, and showed that it achieves
approximation ratio $2$. A classic result of Goemans and Williamson [5] from
the early 90’s shows by an elegant proof that the same algorithm applies for
Set Family Edge Cover with an arbitrary proper family ${\cal F}$. In fact, one
of the main achievements of the Goemans and Williamson paper was defining a
generic class of set families that models a rich collection of combinatorial
optimization problems, for which the primal dual algorithm achieves
approximation ratio $2$. Slightly later, Williamson, Goemans, Mihail, and
Vazirani [8] further extended this result to the more general class of
uncrossable families by adding to the algorithm a novel reverse-delete phase.
They posed an open question of extending this algorithm to a larger class of
set families and combinatorial optimization problems. However, for 30 years,
the class of uncrossable set families remained the most general generic class
of set families for which the primal dual algorithm achieves approximation
ratio $2$. We present a strict generalization of this result, illustrated by
several examples.

######  Definition 1.1.

We say that a set family ${\cal F}$ is semi-uncrossable if for any
$A,B\in{\cal F}$ the following semi-uncrossability condition holds

$A\cap B\in{\cal F}\mbox{ and one of }A\cup B,A\setminus B,B\setminus A\mbox{
is in }{\cal F}\ \ \mbox{ or }\ \ A\setminus B,B\setminus A\in{\cal F}\ .$

One can see that if ${\cal F}$ is symmetric and if $A\cap B\in{\cal F}$ or
$A\setminus B,B\setminus A\in{\cal F}$ whenever $A,B\in{\cal F}$, then ${\cal
F}$ is uncrossable. Indeed, if $A,B\in{\cal F}$ then $\bar{A},\bar{B}\in{\cal
F}$ (since ${\cal F}$ is symmetric), and thus $\bar{A}\cap\bar{B}\in{\cal F}$
or $\bar{A}\setminus\bar{B},\bar{B}\setminus\bar{A}\in{\cal F}$; by symmetry
we get that $A\cup B\in{\cal F}$ or $B\setminus A,A\setminus B\in{\cal F}$. In
particular, we get that:

If ${\cal F}$ is symmetric and semi-uncrossable then ${\cal F}$ is
uncrossable.

Namely, for symmetric ${\cal F}$ the definitions of “uncrossable” and “semi-
uncrossable” coincide. However, for non-symmetric families, these definitions
are distinct. For illustration, consider the following example, see Fig. 1.

Figure 1: An example of a semi-uncrossable family ${\cal
F}=\\{A,B,\\{s\\},\\{t\\}\\}$ that is not uncrossable.

Example 1. Let $V=X\cup Y\cup\\{s,t\\}$ where $X,Y\neq\emptyset$, let
$A=\\{s,t\\}$ and $B=X\cup\\{s\\}$. Let

${\cal F}=\\{A,B,A\cap B,A\setminus B\\}=\\{A,B,\\{s\\},\\{t\\}\\}\ .$

This ${\cal F}$ is semi-uncrossable but not uncrossable. Note that an attempt
to “symmetrize” ${\cal F}$ by adding to ${\cal F}$ the complements of the sets
in ${\cal F}$ results in a family that is not semi-uncrossable (and hence not
uncrossable), where the semi-uncrossability condition fails for
$\bar{A},\bar{B}$. Thus semi-uncrossable families strictly generalize
uncrossable set families. We prove the following.

######  Theorem 1.2.

Set Family Edge Cover with semi-uncrossable ${\cal F}$ admits approximation
ratio $2$.

The Theorem 1.2 algorithm is identical to the algorithm of Williamson,
Goemans, Mihail, and Vazirani [8] for uncrossable families, and the proof of
the approximation ratio is also similar. Hence the contribution of our paper
is not technical but rather conceptual, as follows.

  * •

We define a new class of set families that strictly contains the class of
uncrossable families, and show that the [8] algorithm achieves for this new
class the same approximation ratio $2$.

  * •

We identify many combinatorial algorithmic problems that can be modeled by
this class.

Recently, Bansal, Cheriyan, Grout, and Ibrahimpur [2] defined a new class of
set families which they called pliable set families with property $(\gamma)$;
a set family ${\cal F}$ is pliable if for any $A,B\in{\cal F}$ at least two of
the sets $A\cap B,A\cup B,A\setminus B,B\setminus A$ belongs to ${\cal F}$,
while property ($\gamma$) imposes some restrictions on triples of sets from
${\cal F}$. They showed that the primal-dual algorithm of [5, 8] achieves
approximation ratio $16$ for this class. Property $(\gamma)$ holds for semi-
uncrossable families, and the class of pliable set families with property
$(\gamma)$ strictly includes the class of semi-uncrossable families. But
handling this more general class of families comes with the price of a worse
approximation ratio – $16$ instead of $2$. The class of semi-uncrossable set
families is sandwiched between the uncrossable families and the pliable
families with property $(\gamma)$, and our approximation ratio is $2$ – the
same as for uncrossable set families. Our paper is partly motivated by the
result of [2]. Another motivation comes from the Unbalanced Point-To-Point
Connection problem, where the relevant set family ${\cal F}$ has the property
that $A\cap B\in{\cal F}$ or $A\setminus B,B\setminus A\in{\cal F}$; see [6].
This problem admits approximation ratio $O(\log n)$, but has no known super-
constant approximation threshold.

We illustrate application of Theorem 1.2 on combinations of several
fundamental problems, among them Steiner Forest, $T$-Join, Point-to-Point
Connection, $(T,k)$-Constrained Forest, $k$-Constrained Forest, and Steiner
Network Augmentation; see formal definitions in the next section. We can
combine any two of these problems by requiring that the solution will satisfy
the requirements of both problems. This means that the Set Family Edge Cover
formulation of both problems has the same graph with the same edge costs, and
we need to cover the union of the set families of the problems.111This
definition of “combination of problems” depends on the specific set family
that models the problem. For example, the set family of the Steiner Tree
problem is symmetric, but the set family of the equivalent rooted version is
not. For all problems considered, we will specify the set family we choose,
trying to maximize the number of “good” properties, like uncrossability and
symmetry. Namely, if in one problem we need to cover a set family ${\cal A}$
and in the other a set family ${\cal B}$, then in the combination of the
problems we need to cover the set family ${\cal F}={\cal A}\cup{\cal B}$. In
fact, in this way we can also combine a problem with itself. We will assume
that each of ${\cal A},{\cal B}$ is semi-uncrossable, as otherwise we should
not expect that ${\cal A}\cup{\cal B}$ will be semi-uncrossable. We will prove
the following.

######  Theorem 1.3.

Let ${\cal A},{\cal B}$ be semi-uncrossable set families over a groundset $V$.
Then ${\cal A}\cup{\cal B}$ is semi-uncrossable in the following cases:

  1. (i)

${\cal A}$ is monotone.

  2. (ii)

${\cal A}$ is proper and ${\cal B}$ is disjointness compliable.

As was mentioned, for a symmetric family the definitions of “uncrossable” and
“semi-uncrossable” coincide, hence the new applications of Theorems 1.2 and
1.3 are for non-symmetric families. Consider for example the $k$-Constrained
Forest problem: Given a graph $G=(V,E)$ with edge costs, find a min-cost
subgraph $H$ such that every connected component of $H$ has at least $k$
nodes. The set family we need to cover here is $\\{S:1\leq|S|<k\\}$. This
family is not symmetric, but it is monotone. Monotone set families were
introduced by Goemans and Williamson [4], where they also showed several
additional graph problems that can be modeled by such families. Note that any
monotone family is uncrossable, hence the problem of covering a monotone set
family admits approximation ratio $2$. Couëtoux, Davis, and Williamson [3]
improved the approximation ratio to $1.5$ by a dual fitting algorithm.

Clearly, we can achieve ratio $\alpha+\beta$ for the problem of covering the
union ${\cal F}={\cal A}\cup{\cal B}$ of an uncrossable family ${\cal A}$ and
a monotone family ${\cal B}$, where $\alpha$ and $\beta$ are the best known
approximation ratios for covering ${\cal A}$ and ${\cal B}$, respectively.
Currently, $\alpha=2$ [8] and $\beta=1.5$ [3], so the overall approximation
ratio will be $3.5$. Theorems 1.2 and 1.3 give a better approximation ratio of
$2$. Let us now illustrate Theorem 1.3 and its limitations on few examples.

Example 2. ${\cal A}$ is monotone and ${\cal B}$ is proper, ${\cal A}\cup{\cal
B}$ is semi-uncrossable but not uncrossable.
Consider the set family ${\cal A}=\\{S:1\leq|S|\leq 2\\}$ of the
$3$-Constrained Forest problem that is monotone, and the family ${\cal
B}=\\{S:|S\cap\\{s,t\\}|=1\\}$ of the Shortest $st$-Path problem that is
proper. Now consider the sets $A=\\{s,t\\}$ and $B=X\cup\\{s\\}$ in Example 1,
where $|X|,|Y|\geq 3$. Then $A\in{\cal A}$, $B\in{\cal B}$, but among the sets
$A\cap B,A\cup B,A\setminus B,B\setminus A$, only $A\cap B,A\setminus B$
belong to ${\cal A}\cup{\cal B}$, hence ${\cal A}\cup{\cal B}$ is not
uncrossable. However, ${\cal A}\cup{\cal B}$ is semi-uncrossable by Theorem
1.3.

Example 3. ${\cal A},{\cal B}$ are both disjointness compliable, ${\cal
A}\cup{\cal B}$ is not semi-uncrossable.
Let $V=\\{s,t,x,y\\}$, $A=\\{s,t\\}$, $B=\\{s,x\\}$, and let ${\cal
A}=\\{A,A\cap B\\}=\\{\\{s,t\\},\\{s\\}\\}$ and ${\cal B}=\\{B,A\cap
B\\}=\\{\\{s,x\\},\\{s\\}\\}$. Then ${\cal A},{\cal B}$ are both uncrossable
and disjointness compliable, $A\in{\cal A}$, $B\in{\cal B}$, but among the
sets $A\cap B,A\cup B,A\setminus B,B\setminus A$ only $A\cap B$ belongs to
${\cal A}\cup{\cal B}$.

Example 4. ${\cal A}$ is proper and ${\cal B}$ is uncrossable, ${\cal
A}\cup{\cal B}$ is not semi-uncrossable.
Let $V=\\{x,y,s,t\\}$, $A=\\{x,s\\}$, $B=\\{x,y\\}$, ${\cal
B}=\\{B,\bar{B}\\}$ and let ${\cal A}=\\{S:|S\cap\\{s,t\\}|\\}=1$ (this is the
family of the Shortest $st$-Path problem). One can verify that ${\cal A}$ is
proper, ${\cal B}$ is symmetric and uncrossable, $A\in{\cal A}$, $B\in{\cal
B}$, but among the sets $A\cap B,A\cup B,A\setminus B,B\setminus A$ only
$A\setminus B,A\cup B$ belong to ${\cal A}\cup{\cal B}$, so ${\cal A}\cup{\cal
B}$ is not semi-uncrossable.

The proof of Theorem 1.3 is by a standard case analysis and uncrossing. Yet,
Theorem 1.3 is sharp in the following sense.

  * •

In the combinations considered in the theorem, the combined set family ${\cal
F}={\cal A}\cup{\cal B}$ may not be uncrossable even if ${\cal A},{\cal B}$
are both uncrossable, as is shown in Example 2.

  * •

For any combination not mentioned in Theorem 1.3, either the semi-
uncrossability of ${\cal A}\cup{\cal B}$ can be deduced from the theorem, or
there exists an example such that ${\cal A}\cup{\cal B}$ is not semi-
uncrossable (namely, we cannot weaken the conditions in Theorem 1.3). To see
this, note that in the following cases ${\cal F}={\cal A}\cup{\cal B}$ may not
be semi-uncrossable.

    * –

${\cal A},{\cal B}$ are both disjointness compliable; see Example 3.

    * –

If ${\cal A}$ is proper and ${\cal B}$ is symmetric; see Example 4.

We summarize this in Table 1. Note that there is only entry in the table that
guarantees an uncrossable family – when both ${\cal A},{\cal B}$ are proper,
while there are 5 entries where we get a semi-uncrossable family that may not
be uncrossable.

| d | s | m | d,s
---|---|---|---|---
d | $-$ | $-$ | $+$ | $+$
s |  | $-$ | $+$ | $-$
m |  |  | $+$ | $+$
d,s |  |  |  |  $+^{*}$
Table 1: Combinations that lead to semi-uncrossable families. Here, “d”,“s”,
and “m” stand for disjointness compliable, symmetric, and monotone,
respectively. Also, “$+$” means that the union is semi-uncrossable but is not
uncrossable in general, “$+^{*}$” means that the union is always uncrossable,
while “$-$” means that the union is not semi-uncrossable in general (and there
is an exampe for that).

In the next Section 2 we prove Theorem 1.3 and discuss some applications of
Theorems 1.2 and 1.3 for specific problems, while Theorem 1.2 is proved in
Section 3.

##  2 Applications

Recall that in Theorem 1.3 we need to prove that if ${\cal A},{\cal B}$ are
semi-uncrossable set families then ${\cal A}\cup{\cal B}$ is semi-uncrossable
in the following cases:

  1. (i)

${\cal A}$ is monotone.

  2. (ii)

${\cal A}$ is proper and ${\cal B}$ is disjointness compliable.

Since each of ${\cal A},{\cal B}$ is semi-uncrossable, we need to verify the
semi-uncrossability condition only for pairs of sets $A,B$ such that
$A\in{\cal A}$ and $B\in{\cal B}$. Let $A\in A$ and $B\in B$. Assume that all
sets $A\cap B,A\setminus B,B\setminus A$ are non-empty, as otherwise $\\{A\cap
B,A\cup B\\}=\\{A,B\\}$ or $\\{A\setminus B,B\setminus A\\}=\\{A,B\\}$.

Part (i) is trivial – since ${\cal A}$ is monotone, $A\cap B,A\setminus
B\in{\cal A}$, so the semi-uncrossability condition holds for $A,B$.

We prove (ii). Since ${\cal A}$ is symmetric, $\bar{A}\in{\cal A}$. Since
${\cal A},{\cal B}$ are both disjointness compliable, the following holds:

  1. (a)

$A\cap B\in{\cal A}$ or $A\setminus B\in{\cal A}$.

  2. (b)

$\bar{A}\cap B\in{\cal A}$ or $\bar{A}\setminus B\in{\cal A}$; note that
$\bar{A}\cap B=B\setminus A$ and that $\bar{A}\setminus B=V\setminus(A\cup
B)$, thus this is equivalent to $B\setminus A\in{\cal A}$ or $A\cup B\in{\cal
A}$ (by the symmetry of ${\cal A}$).

  3. (c)

$A\cap B\in{\cal B}$ or $B\setminus A\in{\cal B}$.

Let us consider the two cases in (c).

  * •

If $A\cap B\in{\cal B}$, then the semi-uncrossability condition holds by (b).

  * •

If $B\setminus A\in{\cal B}$ then the semi-uncrossability condition holds by
(a).

In both cases the semi-uncrossability condition holds, concluding the proof of
(ii) and also of Theorem 1.3.

We illustrate application of Theorems 1.2 and 1.3 on combinations of several
fundamental problems. In all these problems we are given an (undirected) graph
$G=(V,E)$ with edge costs $\\{c_{e}:e\in E\\}$, and seek a subgraph of $G$ or
an edge subset of $E$ that satisfies obeys a orescribed requirement. Below we
indicate for each problem the additional parts of the input, the prescribed
requirement, the set family we need to cover, and the (strongest) relevant
properties of this family.

Steiner Forest (SF)
Given a subpartition ${\cal P}$ of $V$, find a min-cost subgraph $H$ of $G$
such that every part $P\in{\cal P}$ is contained in the same connected
component of $H$.
Set family: $\\{S:\emptyset\neq S\cap P\neq P\mbox{ for some }P\in{\cal
P}\\}$; this family is proper and thus uncrossable.

$T$-Join
Given a set $T\subseteq V$ of terminals with $|T|$ even, find a min-cost
subgraph $H$ of $G$ such that every connected component of $H$ contains an
even number of terminals.
Set family: $\\{S:|S\cap T|\mbox{ is odd}\\}$; this family is proper and thus
uncrossable.

$(T,k)$-Constrained Forest ($(T,k)$-CF)
Given a set $T\subseteq V$ of terminals and an integer $k$, find a min-cost
spanning subgraph $H$ of $G$ such that every connected component of $H$ has
$0$ or at least $k$ terminals.
Set family: $\\{S:1\leq|S\cap T|<k\\}$; this family is disjointness compliable
and uncrossable.

$k$-Constrained Forest ($k$-CF)
This is a particular case of $(T,k)$-CF when $T=V$.
Set family: $\\{S:1\leq|S|<k\\}$; this family is monotone and thus
uncrossable.

Generalized Point-To-Point Connection (G-P2P)
Given integer charges $\\{b(v):v\in V\\}$ with $b(V)=0$, find a min-cost
spanning subgraph $H$ of $G$ such that every connected component of $H$ has
zero charge.
Set family: $\\{S:b(S)\neq 0\\}$; this family is proper and thus uncrossable.

Steiner Network Augmentation (SNA)
Given a graph $G_{0}=(V,E_{0})$ with $E_{0}\cap E=\emptyset$ and a set $D$ of
demand node pairs, find a min-cost subgraph $H$ of $G$ such that
$\lambda_{G_{0}\cup H}(uv)\geq\lambda_{G_{0}}(u,v)+1$ for all $(u,v)\in D$,
where $\lambda_{J}(u,v)$ denotes the maximum number of edge disjoint
$uv$-paths in a graph $J$.
Set family: $\\{S:|S\cap\\{u,v\\}|=1,d_{G_{0}}(S)=\lambda_{G_{0}}(u,v)\mbox{
for some }\\{u,v\\}\in D\\}$; this family is symmetric and uncrossable.

Combinations of problem pairs from the list above that give a semi-uncrossable
family are summarized in Table 2; we added one additional row for the Shortest
$st$-Path problem, that will help us to verify that the table was indeed
filled correctly. Excluding the last row, we have overall 21 combinations, and
15 of them give a semi-uncrossable set family by Theorem 1.3. Among these, 8
combinations give a set family that is not uncrossable in general. We now will
justify whether each entry should be marked by “$+$” (semi-uncrossable that
may not be uncrossable), or by “$+^{*}$” (always uncrossable), or by “$-$”
(may not be semi-uncrossable). Interestingly, Theorem 1.3 “correctly filled”
the table – the plus entries are exactly the ones that could be deduced from
the theorem.

|  SF d,s |  $T$-Join d,s |  G-P2P d,s |  $k$-CF m |  $(T,k)$-CF d |  SNA s
---|---|---|---|---|---|---
SF d,s | $+^{*}$ | $+^{*}$ | $+^{*}$ | $+$ | $+$ | $-$
$T$-Join d,s |  | $+^{*}$ | $+^{*}$ | $+$ | $+$ | $-$
G-P2P d,s |  |  | $+^{*}$ | $+$ | $+$ | $-$
$k$-CF m |  |  |  |  $+^{*}$ | $+$ | $+$
$(T,k)$-CF d |  |  |  |  | $-$ | $-$
SNA s |  |  |  |  |  | $-$
SP d,s | $+^{*}$ | $+^{*}$ | $+^{*}$ | $+$ | $+$ | $-$
Table 2: Combinations that lead to semi-uncrossable families. Here, “d”,“s”,
and “m” stand for disjointness compliable, symmetric, and monotone,
respectively (uncrossability is not mentioned since all problems are
uncrossable). Also, “$+$” means that the union is semi-uncrossable, “$+^{*}$”
means that the union is uncrossable, while “$-$” means that the union is not
semi-uncrossable in general.

We need the following observations to show that the table was indeed filled
correctly.

  1. (A)

If ${\cal F}$ is semi-uncrossable and symmetric then ${\cal F}$ is
uncrossable.

  2. (B)

If ${\cal A},{\cal B}$ are both monotone then ${\cal A}\cup{\cal B}$ is also
monotone and thus uncrossable.

  3. (C)

Except $k$-CF, the Shortest $st$-Path problem is a particular case of each of
the problems considered here.

  4. (D)

There is an example that the combination of Shortest $st$-Path with $3$-CF
(and thus also with $(T,3)$-CF) gives a semi-uncrossable family that is not
uncrossable.

  5. (E)

There is an example that the combination of Shortest $st$-Path with SNA gives
a set family that is not semi-uncrossable.

Observation (A) was already proved in the introduction while Observation (B)
is trivial. For Observation (C), one can verify that Shortest $st$-Path is a
particular case of:

  * •

SF when ${\cal P}=\\{\\{s,t\\}\\}$.

  * •

$T$-Join when $T=\\{s,t\\}$.

  * •

G-P2P when $b(s)=1,b(t)=-1$, and $b(v)=0$ otherwise.

  * •

$(T,k)$-CF when $T=\\{s,t\\}$ and $k=2$.

  * •

SNA when $E_{0}=\emptyset$ and $D=\\{\\{s,t\\}\\}$.

Observation (D) was proved in the Introduction, see Example 2.

We now consider Observation (E). Note that in the combined problem of Shortest
$st$-Path with SNA we cannot just add the pair $\\{s,t\\}$ to the set $D$ of
demand pairs, because we require that the augmenting graph $H$ will contain an
$st$-path, and not the weaker condition that $G_{0}\cup H$ will contain an
$st$-path. Consider now the families ${\cal A},{\cal B}$ in Example 4 in the
Introduction. Let $E_{0}=\\{xy,st\\}$. Then (independently of the edge set $E$
and costs), ${\cal B}$ is the family of the SNA instance and ${\cal A}$ is the
family of the Shortest $st$-Path instance. But in Example 4 the family ${\cal
A}\cup{\cal B}$ is not semi-uncrossable.

We use these observations to justify the last row of the table – of the
Shortest $st$-Path problem. The first 3 entries in the row are by Theorem
1.3(ii). The next two entries are by Theorem 1.3(i) and Observation (D). The
last entry in the row is by Observation (E).

In a similar way we can fill the other entries. Note that observation (D) is
used only for the plus entries, to decide whether the entry should be “$+$” or
“$+^{*}$”.

The first 3 columns: Here all combinations give a semi-uncrossable family by
Theorem 1.3(ii). The family is also uncrossable, since the combined set family
is symmetric.

The $k$-CF column. The first 3 entries in the column follow from Theorem
1.3(i) and Observations (C) and (D). The fourth entry is by Observation (B).

The $(T,k)$-CF column. All positive entries in the column of $(T,k)$-CF are by
Theorem 1.3 and Observations (C) and (D); in the first 3 entries of the
column, instead of Observation (C) and (D) we can use the fact that $k$-CF is
a particular case of $(T,k)$-CF.

The SNA column. All the minus entries in this column follow from Observations
(C) and (E). The unique plus entry in this column is by Theorem 1.3(i) and
Observation (D).

##  3 Proof of Theorem 1.2

In this section we prove Theorem 1.2. During the proof we indicate the parts
that extend or fail to pliable set families; recall that a set family ${\cal
F}$ is pliable if for any $A,B\in{\cal F}$ at least $2$ sets from $A\cap
B,A\cup B,A\setminus B,B\setminus A$ belong to ${\cal F}$. Also recall that
the residual family of ${\cal F}$ w.r.t. an edge set $I$ is ${\cal
F}^{I}=\\{S\in{\cal F}:d_{I}(S)=0\\}$.

One can see that if an edge $e$ covers one of the sets $A\cap B,A\cup
B,A\setminus B,B\setminus A$ then it also covers one of $A,B$. This implies
the following.

######  Corollary 3.1.

If ${\cal F}$ is semi-uncrossable or if ${\cal F}$ is pliable then so is
${\cal F}^{I}$, for any edge set $I$.

An ${\cal F}$-core is an inclusion minimal member of ${\cal F}$; let ${\cal
C}({\cal F})$ denote the family of ${\cal F}$-cores. Similarly to uncrossable
families, we have the following.

######  Lemma 3.2.

If ${\cal F}$ is semi-uncrossable then for any $C\in{\cal C}({\cal F})$ and
$S\in{\cal F}$, either $C\subseteq S$ or $C\cap S=\emptyset$; in particular,
the ${\cal F}$-cores are pairwise disjoint.

Note that if ${\cal F}$ is pliable then the cores are also pairwise disjoint.
However, the first property in Lemma 3.2 may not hold for pliable families.

We now describe the algorithm. Consider the following LP-relaxation (P) for
Set Family Edge Cover and its dual program (D):

$\displaystyle\begin{array}[]{lllllll}&\hphantom{\bf(P)}&\min&\
\displaystyle\sum_{e\in E}c_{e}x_{e}&\hphantom{\bf(P)}&\max&\
\displaystyle\sum_{S\in{\cal F}}y_{S}\\\ &\mbox{\bf(P)}&\
\mbox{s.t.}&\displaystyle\sum_{e\in\delta(S)}x_{e}\geq 1\ \ \ \ \ \forall
S\in{\cal F}&\mbox{\bf(D)}&\ \mbox{s.t.}&\displaystyle\sum_{\delta(S)\ni
e}y_{S}\leq c_{e}\ \ \ \ \ \forall e\in E\\\ &\hphantom{\bf(P)}&&\ \ x_{e}\geq
0\ \ \ \ \ \ \ \ \ \ \ \forall e\in E&\hphantom{\bf(P)}&&\ \ y_{S}\geq 0\ \ \
\ \ \ \ \ \ \ \ \ \forall S\in{\cal F}.\end{array}$

Given a solution $y$ to (D), an edge $e\in E$ is tight if the inequality of
$e$ in (D) holds with equality. The algorithm has two phases.

Phase 1 starts with $I=\emptyset$ an applies a sequence of iterations. At the
beginning of an iteration, we compute the family ${\cal C}({\cal F}^{I})$.
Then we raise the dual variables corresponding to the members of ${\cal
C}({\cal F}^{I})$ uniformly (possibly by zero), until some edge $e\in
E\setminus I$ becomes tight, and add $e$ to $I$. Phase I terminates when
${\cal C}({\cal F}^{I})=\emptyset$, namely when $I$ covers ${\cal F}$.

Phase 2 applies on $I$ “reverse delete”, which means the following. Let
$I=\\{e_{1},\ldots,e_{j}\\}$, where $e_{i+1}$ was added after $e_{i}$. For
$i=j$ downto $1$, we delete $e_{i}$ from $I$ if $I\setminus\\{e_{i}\\}$ still
covers ${\cal F}$. At the end of the algorithm, $I$ is output.

It is easy to see that the produced dual solution is feasible, hence
$\sum_{S\in{\cal F}}y_{S}\leq{\sf opt}$, by the Weak Duality Theorem. We prove
that at the end of the algorithm

$\sum_{e\in I}c(e)\leq 2\sum_{S\in{\cal F}}y_{S}\ .$

As any edge in $I$ is tight, the last inequality is equivalent to

$\sum_{e\in I}\sum_{\delta_{l}(S)\ni e}y_{S}\leq 2\sum_{S\in{\cal F}}y_{S}\ .$

By changing the order of summation we get:

$\sum_{S\in{\cal F}}d_{I}(S)y_{S}\leq 2\sum_{S\in{\cal F}}y_{S}\ .$

It is sufficient to prove that at any iteration the increase at the left hand
side is at most the increase in the right hand side. Let us fix some
iteration, and let ${\cal C}$ be the family of cores among the members of
${\cal F}$ not yet covered. The increase in the left hand side is
$\varepsilon\cdot\sum_{C\in{\cal C}}d_{I}(C)$, where $\varepsilon$ is the
amount by which the dual variables were raised in the iteration, while the
increase in the right hand side is $\varepsilon\cdot 2|{\cal C}|$.
Consequently, it is sufficient to prove that $\sum_{C\in{\cal C}}d_{I}(C)\leq
2|{\cal C}|$. As the edges were deleted in reverse order, the set $I^{\prime}$
of edges in $I$ that were added after the iteration (and “survived” the
reverse delete phase), form an inclusion minimal edge-cover of the family
${\cal F}^{\prime}$ of members in ${\cal F}$ that are uncovered at the
beginning of the iteration. Note also that $\bigcup_{C\in{\cal
C}}\delta_{I}(C)\subseteq I^{\prime}$. Hence to prove ratio $2$, it is
sufficient to prove the following purely combinatorial statement, in which due
to Corollary 3.1 we can revise our notation to ${\cal F}\leftarrow{\cal
F}^{\prime}$ and $I\leftarrow I^{\prime}$.

######  Lemma 3.3.

Let $I$ be an inclusion minimal cover of a set family ${\cal F}$ and let
${\cal C}={\cal C}({\cal F})$ be the family of ${\cal F}$-cores. If ${\cal F}$
is semi-uncrossable then

$\sum_{C\in{\cal C}}d_{I}(C)\leq 2|{\cal C}|-1\ .$ (1)

In the rest of this section we prove Lemma 3.3. Let us say that two sets $A,B$
are laminar if they are disjoint or one of them contains the other; namely, if
at least one of the sets $A\cap B,A\setminus B,B\setminus A$ is empty. A set
family ${\cal L}$ is a laminar set family if its members are pairwise laminar.
Let $I$ be an inclusion minimal edge cover of a set family ${\cal F}$. We say
that $S_{e}\in{\cal F}$ is a witness set for $e$ if $e$ is the unique edge in
$I$ that covers $S_{e}$, namely, if $\delta_{I}(S_{e})=\\{e\\}$. We say that
${\cal L}\subseteq{\cal F}$ is a witness family for $I$ if $|{\cal L}|=|I|$
and for every $e\in I$ there is a witness set $S_{e}\in{\cal L}$. By the
minimality of $I$, there exists a witness family ${\cal L}\subseteq{\cal F}$.
We will show the following.

######  Lemma 3.4.

Let $I$ be an inclusion minimal cover of a set family ${\cal F}$. If ${\cal
F}$ is semi-uncrossable then there exists a witness family ${\cal
L}\subseteq{\cal F}$ for $I$ that is laminar.

######  Proof 3.5.

Let $A,B\in{\cal F}$ be witness sets of edges $e,f\in I$, respectively. Note
that no edge in $I\setminus\\{e,f\\}$ covers a set from $A\cap B,A\cup
B,A\setminus B,B\setminus A$, as such an edge covers one of $A,B$,
contradicting that $A,B$ are witness sets. Thus all possible locations of such
$e,f$ are as depicted in Fig. 2. We claim that one of the sets $A\cap
B,A\setminus B,B\setminus A$ is a witness set for one of $e,f$. This follows
from the following observations.

  * •

$A\setminus B\notin{\cal F}$ in (a) and $B\setminus A\notin{\cal F}$ in (b);
in both cases, $A\cap B\in{\cal F}$ is a witness set for one of $e,f$.

  * •

$A\cup B\notin{\cal F}$ in (c), and $A\cap B\notin{\cal F}$ in (d); in both
cases, $A\setminus B,B\setminus A\in{\cal F}$ and each of $A\setminus
B,B\setminus A$ is a witness set for one of $e,f$.

By the minimality of $I$ there exists a witness family for $I$. Let ${\cal L}$
be a witness family for $I$ with $\sum_{S\in{\cal L}}|S|$ minimal. We claim
that ${\cal L}$ is laminar. Suppose to the contrary that there are
$A,B\in{\cal L}$ that are not laminar. Then there is $A^{\prime}\in\\{A\cap
B,A\setminus B,B\setminus A\\}$ and $B^{\prime}\in\\{A,B\\}$ such that ${\cal
L}^{\prime}=({\cal L}\setminus\\{A,B\\})\cup\\{A^{\prime},B^{\prime}\\}$ is
also a witness family for $I$. However, $\sum_{S\in{\cal
L}^{\prime}}|S|<\sum_{S\in{\cal L}}|S|$, contradicting the choice of ${\cal
L}$.

Figure 2: Illustration to the proof of Lemma 3.4.

We note that Lemma 3.4 extends to pliable families by a slightly more
complicated proof, see [2, Lemma 10].

Let $J=\bigcup_{C\in{\cal C}}\delta_{I}(C)$. Note that
$\delta_{I}(C)=\delta_{J}(C)$ for any $C\in{\cal C}$. As any subfamily of a
laminar family is also laminar, we conclude from Lemma 3.4 that if ${\cal F}$
is semi-uncrossable then there exists a laminar witness family ${\cal
L}\subseteq{\cal F}$ for $J$. Note that for every $S\in{\cal L}$ there is
$C\in{\cal C}$ such that $C\subseteq S$. Moreover, if ${\cal F}$ is semi-
uncrossable then by Lemma 3.2 ${\cal L}\cup{\cal C}$ is laminar (this is not
true if ${\cal F}$ is only pliable). Thus to finish the proof of Lemma 3.3, it
is sufficient to prove the following lemma, that was essentially proved in [5,
8].

######  Lemma 3.6.

Let ${\cal L},{\cal C}$ be set families such that ${\cal L}\cup{\cal C}$ is
laminar, the members of ${\cal C}$ are pairwise disjoint, and ${\cal C}$ is
the family of inclusion minimal members of ${\cal L}\cup{\cal C}$. Let $J$ be
an edge set such that every edge in $J$ covers some $C\in{\cal C}$. If ${\cal
L}$ is a witness family for $J$ then

$\sum_{C\in{\cal C}}d_{J}(C)\leq 2|{\cal C}|-1\ .$ (2)

######  Proof 3.7.

Let $S=S_{e}$ be an inclusion minimal set in ${\cal L}$, let $C\in{\cal C}$
such that $C\subseteq S_{e}$ (possibly $C=S_{e}$), and let ${\cal L}_{C}$ be
the family of sets in ${\cal L}$ that contain $C$ and contain no other set in
${\cal C}$. We claim that then:

  1. (i)

$\delta_{J}(C)=\\{e\\}$.

  2. (ii)

$S_{e}\in{\cal L}_{C}$ and $|{\cal L}_{C}|\leq 2$.

We prove (i). Suppose to the contrary that there is
$f\in\delta_{J}(C)\setminus\\{e\\}$. Since ${\cal L}$ is laminar and $S_{e}$
is inclusion minimal in ${\cal L}$, we must have $S_{e}\subset S_{f}$ or
$S_{e}\cap S_{f}=\emptyset$. In both cases $f$ covers $S_{e}$, contradicting
that $S_{e}$ is a witness set for $e$.

We prove (ii). It is easy to see that $S_{e}\in{\cal L}_{C}$. Suppose to the
contrary that there are distinct $S_{f},S_{g}\in{\cal
L}_{C}\setminus\\{S_{e}\\}$. Then $S_{e}\subset S_{f}\subset S_{g}$. Since
every edge in $J$ covers some $C\in{\cal C}$, there is $C_{f}\in{\cal C}$ that
is covered by $f$. Since $S_{g}\in{\cal L}_{C}$, we must have $C_{f}\cap
S_{g}=\emptyset$. But then $f$ must cover $S_{g}$, contradicting that $S_{g}$
is a witness set for $g$.

The rest of the proof is by induction on $|{\cal C}|$. The base case $|{\cal
C}|=1$ is easy to verify. We prove the lemma for $|{\cal C}|\geq 2$, assuming
that it holds for $|{\cal C}|-1$.

Let $C$ be as in (i) and let ${\cal C}^{\prime}={\cal C}\setminus\\{C\\}$.
Define $J^{\prime}$ and ${\cal L}^{\prime}$ as follows.

  * •

If ${\cal L}_{C}=\\{S_{e}\\}$ and if there is $C^{\prime}\in{\cal C}^{\prime}$
such that $\delta_{J}(C^{\prime})=\\{e\\}$, then $J^{\prime}=J$ and ${\cal
L}^{\prime}=(L\setminus\\{S_{e}\\})\cup\\{C^{\prime}\\}$.

  * •

Else, $J^{\prime}=J\setminus\\{e\\}$ and ${\cal L}^{\prime}={\cal
L}\setminus\\{S_{e}\\}$.

One can verify that the triple ${\cal L}^{\prime},{\cal
C}^{\prime},J^{\prime}$ satisfies the assumptions of the lemma and that
$\sum_{C\in{\cal C}}d_{J}(C)-\sum_{C\in{\cal C}^{\prime}}d_{J^{\prime}}(C)\leq
2$. From this, using the induction hypothesis we get

$\sum_{C\in{\cal C}}d_{J}(C)\leq\sum_{C\in{\cal
C}^{\prime}}d_{J^{\prime}}(C)+2\leq(2|{\cal C}^{\prime}|-1)-1+2=2|{\cal C}|-1\
,$

concluding the proof.

This concludes the proof of Theorem 1.2.

##  4 Concluding remarks

In this paper we presented a new class of semi-uncrossable set families that
extends the class of uncrossable families. The algorithm of [8] for
uncrossable families extends to the more general class of semi-uncrossable
families with the same approximation ratio of $2$. Our work shows that often a
combination of two problems such that at least one of them is non-symmetric
gives a problem with a semi-uncrossable family that is not uncrossable in
general.

Jain [7] introduced the iterative rounding method, and used it to obtain
approximation ratio $2$ for the problem of covering a skew-supermodular
(a.k.a. weakly supermodular) set function; the class of skew-supermodular set
functions generalizes the class of uncrossable set families. It is an
interesting question whether Jain’s result can be extended to a larger class
of set functions.

## References

  * [1] A. Agrawal, P. Klein, and R. Ravi.  When trees collide: An approximation algorithm for the generalized Steiner problem on networks.  SIAM J. on Computing, 24(3):440–456, 1995.
  * [2] I. Bansal, J. Cheriyan, L. Grout, and S. Ibrahimpur.  Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions.  CoRR, abs/2209.11209, 2022.  URL: https://arxiv.org/abs/2209.11209.
  * [3] B. Couëtoux, J. M. Davis, and D. P. Williamson.  A 3/2-approximation algorithm for some minimum-cost graph problems.  Mathematical Programming, 150:19–34, 2015.
  * [4] M. X. Goemans and D. P. Williamson.  Approximating minimum-cost graph problems with spanning tree edges.  Operations Research Letters, 16:183–189, 1994.
  * [5] M. X. Goemans and D. P. Williamson.  A general approximation technique for constrained forest problems.  SIAM J. Comput., 24(2):296–317, 1995.
  * [6] MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, and Zeev Nutov.  On fixed cost k-flow problems.  Theory Comput. Syst., 58(1):4–18, 2016.
  * [7] K. Jain.  A factor 2 approximation algorithm for the generalized steiner network problem.  Combinatorica, 21(1):39–60, 2001.
  * [8] D. P. Williamson, M. X. Goemans, M. Mihail, and V. V. Vazirani.  A primal-dual approximation algorithm for generalized steiner network problems.  Combinatorica, 15(3):435–454, 1995.