「烧情侣」

0 烧情侣

Problem 0（烧情侣） 给你一张 $n$ 个点的无向图 $G$，初始时每个点上有无穷多对情侣。每一次操作你可以执行以下动作之一：

• 在任意顶点上放置一名团员，烧掉这个顶点上的所有情侣。
• 将一个团员从图中移除。
• 选择一个团员，将他移动到相邻的顶点上，并烧掉该顶点上的所有情侣。

每次操作后，情侣会以无限速度沿边占据所有可到达的顶点（情侣不可穿过团员）。问至少需要多少个团员，才能在有限次操作内烧掉所有情侣。

1 图搜索简介

Problem 1.1（Edge Searching）

这是最原始的图搜索游戏。

• 定义: 在 edge searching 模型中，一条边 $(u, v)$ 是通过一名团员从其一个端点 $u$ 滑动到另一个端点 $v$ 来完成清理的。为了在滑动过程中保护已清理的区域，起始点 $u$ 必须已被“守卫”——即 $u$ 上驻留有另一名团员，或者与 $u$ 相连的所有其他边均已清理。
• 基本操作:
  1. 在任意顶点上放置一名新团员。
  2. 从任意顶点上移除一名团员。
  3. 将一名已在顶点上的团员沿一条边滑动到另一端。
• Edge search number: 该模型下的最小团员数量记为 $es(G)$。

Problem 1.2（Node Searching）

Node searching 模型取消了“滑动”这一动态操作，规则更为静态。（注意：该模型中不存在“滑动”操作）

• 定义: 在 node searching 模型中，一条边 $(u, v)$ 被清理的唯一方式是，其两个端点 $u$ 和 $v$ 被团员同时占据。
• 基本操作:
  1. 在任意顶点上放置一名新团员。
  2. 从任意顶点上移除一名团员。 (注意：该模型中不存在“滑动”操作)
• Node search number: 该模型下的最小团员数量记为 $ns(G)$。

Problem 1.3（Mixed Searching）

Mixed searching 是上述两种模型的自然推广，它赋予了团员更大的策略自由度。

• 定义: 在 mixed searching 模型中，一条边 $(u, v)$ 的清理方式十分灵活，可以是以下任意一种:
  • 通过一名团员从 $u$ 滑动到 $v$ (同 edge search)。
  • 通过同时占据端点 $u$ 和 $v$ (同 node search)。
• 基本操作:
  1. 在任意顶点上放置一名新团员。
  2. 从任意顶点上移除一名团员。
  3. 将一名已在顶点上的团员沿一条边滑动到另一端。
• Mixed search number: 该模型下的最小团员数量记为 $ms(G)$。

2. “烧”顶点与“烧”边的联系

Proposition 2.1 $es(G) - 1 \le ms(G) \le es(G)\;\text{and}\;ns(G) - 1 \le ms(G) \le ns(G)$

Theorem 2.2 $es(G) = ms(G^e)$ 且 $ns(G) = ms(G^n)$

1. $G^e$ 上的 edge search 可以转化到 $G$ 上的 edge search。
   $G$ 上的边 $(u,v)$ 对应 $G^e$ 上的两条边 $(u,w)$ 和 $(w,v)$。我们将所有的 $(w,v)$ 收缩（contract），得到的新图 $H$ 与 $G$ 同构。$H$ 的每一个顶点 $v$ 都是通过将 $G^e$ 的一个顶点子集 $C_v$ 合并而得到的。给定一个 $G^e$ 的边搜索，我们通过以下规则将其转换为 $H$ 的边搜索：如果在第 $i$ 步，团员 $s$ 位于顶点 $u\in V(G^e)$，那么在新的搜索的第 $i$ 步，团员 $s$ 就位于顶点 $v\in V(H)$，其中 $u\in C_v$。这满足了我们的要求。
2. $G^e$ 上的 mixed search 可以转化到 $G^e$ 上的 edge search。
   我们只要证明对于 $G^e$ 上的一个 mixed search 方案，它所有通过同时占据两端点来清理的边，都可以在不增加新的团员的情况下，通过滑动操作来清理（回顾 mixed search 定义了两种清理方式）。
   具体来说，假设 mixed search 第 $i$ 步有一条边 $(u,v)$ 因为两个端点都被团员占据而被清理。由 $G^e$ 的定义，$u,v$ 中至少有一个是二度点，不妨设 $v$ 是二度点。那么我们在第 $i$ 步之后插入连续第两步：先将 $v$ 上的团员滑动到 $u$，再从 $u$ 滑动到 $v$。这样 $(u,v)$ 就以滑动的方式被清理了，并且不会有任何边发生重污染。

Remark 2.3 Theorem 2.2 意味着 edge search 和 node search 可以规约到 mixed search 上，但反过来可能并不容易。从定义上来看，mixed search 拥有更强的搜索能力。

Theorem 2.4 “烧情侣”（Problem 0）在简单图 $G$ 上的答案为 $ms(G)$。

Lemma 2.5 对于简单图 $G$ 上的一个搜索方案，在任何时刻，“烧情侣”被清理的点集为 $C$ 当且仅当 mixed search 被清理的边集为 $E_G(C) = \{(u,v)\in E(G)\mid u,v\in C\}$，即 $C$ 导出子图的边集。

1. 清理：
   • 如果 $v\in C_i$，那么 $C=C_i$ 和 $A=A_i$ 都不会变化。
   • 如果 $v\notin C_i$，考虑 $v$ 的邻居 $w\in C_i$，$w$ 在第 $i$ 步一定有团员驻留，否则 $w$ 在第 $i$ 步会被重污染。如果 $w=u$ 那么 $(v,w)$ 在 mixed search 中因滑动而清理；否则它因 $v$ 和 $w$ 同时被占据而清理。因此这一步后，$C = C_i \cup \{v\}$，$A = A_i \cup \{(v,w)\in E(G)\mid w\in C_i\} = E_G(C_i\cup \{v\})$。
2. 重污染：
   • 如果“烧情侣”没有顶点可以被重污染，跳至 3。
   • 否则，总可以选一个顶点 $x\in C$ 将要被重污染，且它有一个邻居 $y\in V(G)\setminus C$。这意味着 $(x,y)\notin A$，因此 mixed-search 中，$x$ 的所有邻边 $e$ 都会被 $(x,y)$ 重污染。$C' = C - \{x\}$，$A' = A - \{e\in E(G) \mid e\text{ is incident to } x\} = E_G(C'-\{x\})$。重复 2。
3. 此时“烧情侣”中已经没有顶点可以被重污染了。
   假设 mixed search 中还有边可以被重污染，那么总可以选一条边 $(u,v)\in A$ 将要被重污染，且 $v$ 上没有团员，有一条邻边 $(v,w)\in E(G)\setminus A$。这意味着 $v\in C, w\notin C$，因此 $v$ 会被 $w$ 重污染。这样导出了矛盾，所以此时 mixed search 中没有边可以被重污染。

Remark 2.6 注意 Theorem 2.4 在有重边的图上并不一定成立，比如 2 个点之间有 2 条边的图 $G$，烧情侣的答案为 1，而 $ms(G)=2$。回顾证明过程，你会注意到有重边时“清理”这一步不一定保持 Lemma 2.5 成立。

3. 单调性（Monotonicity）

Definition 3.1（图搜索问题的单调性） 称一个图搜索问题具有单调性，如果对于所有图 $G$，存在一个搜索方案使用的团员数 $\leq k$，则存在一个单调的搜索方案使用的团员数 $\leq k$。

Theorem 3.2（Bienstock D, Seymour P. 1991） Mixed searching 具有单调性。

Notation 3.3

• $G$ 的一个 mixed search 方案表示成序列 $(A_0,Z_0),(A_1,Z_1),\ldots,(A_n,Z_n)$，其中 $A_i$ 是第 $i$ 步时被清理的边集，$Z_i$ 是第 $i$ 步时有团员的点集。
  为了方便讨论，我们在这一节中认为每一步操作最多只会有一条新的边被清理（即使有多条边可以同时被清理，我们也将其分为多步），即 $|A_i-A_{i-1}| \le 1\text{ for } 1\le i \le n$。注意这里的 $A_i - A_{i-1}$ 是差集，即在 $A_i$ 中但不在 $A_{i-1}$ 中的边（不一定有 $A_i\supseteq A_{i-1}$），请务必不要和集合大小的差搞混。
• 设 $X\subseteq E(G)$ 是一个边集，定义 $\delta(X)$ 为既是 $X$ 中某条边的端点，又是 $E(G)\setminus X$ 中某条边的端点的点集。注意到 $\delta(X) = \delta(E(G)\setminus X)$。此外，$|\delta|$ 还满足 submodular inequality:
  $$|\delta(X\cup Y)| + |\delta(X\cap Y)| \leq |\delta(X)| + |\delta(Y)|, \quad \forall X,Y\subseteq E(G)$$
  这是因为不等式左边每个被数到的点，都在右边被数到了至少同样多次。
• 定义图 $G$ 一个 crusade 为 $E(G)$ 的一列子集 $(X_0,X_1,\ldots,X_n)$，满足 $X_0 = \emptyset$，$X_n = E(G)$，且对于 $1\leq i\leq n$，$|X_i-X_{i-1}| \leq 1$。我们称一个 cursade 使用少于 $k$ 个团员，如果对 $0\leq i\leq n$ 都有 $|\delta(X_i)| \le k$。

Proposition 3.4 如果 $ms(G) \leq k$，那么存在一个使用 $\le k$ 个团员的 crusade。

Remark 3.5 Proposition 3.4 的逆命题实际上是成立的，但证明并不显然。不过证明 crusade 的单调性是一件相对容易的事情。我们称一个 crusade $(X_0,X_1,\ldots,X_n)$ 是 progressive 的，如果 $X_0\subseteq X_1\subseteq \cdots \subseteq X_n$，且 $|X_i-X_{i-1}| = 1\text{ for } 1\leq i\leq n$。

Lemma 3.6 如果图 $G$ 有一个使用 $\le k$ 个团员的 crusade，那么也存在一个使用 $\le k$ 个团员的 progressive crusade。

Lemma 3.7 设 $G$ 是一张图，每个点的度数都 $\ge 2$。设 $(X_0,X_1,\dots,X_n)$ 是一个使用 $\le k$ 个团员的 progressive crusade，并且对于 $1\le i\le n$，$X_i - X_{i-1} = \{e_i\}$。那么存在一个单调的 mixed search，它使用 $\le k$ 个团员，并且确保 $G$ 的边按 $e_1,e_2,\dots,e_n$ 的顺序被清理。

• 如果 $|N \cup \delta(X_{j-1})| \le k$，我们可以将新的团员放置在 $e_j$ 的端点上，并宣告它被清理。
• 我们接下来假设 $|N \cup \delta(X_{j-1})| > k$。那么
  (1) $N \not\subseteq \delta(X_{j-1})$。
  如果 $N \subseteq \delta(X_{j-1})$，那么 $|N \cup \delta(X_{j-1})| \le |\delta(X_{j-1})| \le k$，这与假设矛盾。
  (2) $N - \delta(X_{j-1}) \subseteq \delta(X_j)$。
  这是因为对于任意 $x\in N-\delta(X_{j-1})$，$x$ 度数 $\geq 2$，它除了 $e_j$ 之外还与至少一条不在 $X_{j-1}$ 中的边 $e$ 关联，且 $e\notin X_j$。
  (3) $\delta(X_{j-1}) \not\subseteq \delta(X_j)$。
  如果 $\delta(X_{j-1})\subseteq \delta(X_j)$，那么由 (2) 有 $N\cup \delta(X_{j-1}) = (N-\delta(X_{j-1}))\cup \delta(X_{j-1}) \subseteq \delta(X_j)$，则 $|N\cup \delta(X_{j-1})| \le |\delta(X_j)| \le k$，这与假设矛盾。
  由 (3)，选择一个顶点 $u \in \delta(X_{j-1}) - \delta(X_j)$。那么 $u \in N$，并且 $e_j$ 有端点 $u,v$，且 $u$ 除了 $e_j$ 之外，不与任何在 $E(G) - X_{j-1}$ 中的边（即有情侣的边）相关联。因此，我们可以通过将位于 $u$ 的团员沿着 $e_j$ 滑动到 $v$ 来清理 $e_j$，而不会发生重污染。$\square$

Corollary 3.8 烧情侣问题具有单调性。

Remark 3.9 使用 Theorem 3.2 结合类似 Theorem 2.4 的证明方法，也可以得出 edge searching 和 node searching 具有单调性。这是 mixed search 灵活性的体现，其他问题的单调性都可以归约到它上面。

4. 一般图上的 $O(2^n \cdot poly(n))$ 算法和树上的 $O(n)$ 算法

Theorem 4.1 记用单调方案清理点集 $S\subseteq V(G)$ 需要的最小团员数为 $f(S)$，则

1. $|\partial(S)-\{v\}| \le f(S\setminus \{v\}) - 1$
   • 如果 $|\partial(S\setminus \{v\})| \le f(S\setminus \{v\}) - 1$，那么说明清理完 $S\setminus \{v\}$ 后，团员数比边界点数多，此时可以将空闲的团员移到 $v$ 上来清理。
   • 如果 $|\partial(S\setminus \{v\})| = f(S\setminus \{v\})$，那么 $N_S(v) \not\subseteq \partial(S)$。取 $u\in N_S(v) - \partial(S)$，将点 $u$ 上的团员滑动到 $v$ 上来清理。
   这样没有新增团员，因此用 $f(S\setminus \{v\})$ 来更新 $f(S)$。
2. $|\partial(S)-\{v\}| = f(S\setminus \{v\})$
   此时 $\partial(S)-\{v\} = \partial(S\setminus \{v\})$，且 $N_S(v) \subseteq \partial(S)$。这意味着清理完 $S\setminus \{v\}$ 后所有团员都在边界点上（没有空闲的团员），且没有与 $v$ 相邻的团员。因此只能用 $f(S\setminus \{v\})+1$ 来更新 $f(S)$。

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 20;

int N[MAXN]; // N[i] 表示 i 的邻居集合 mask
int f[1 << MAXN]; // f[S] 表示清理点集 S 需要的最小团员数

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        N[u] |= 1 << v;
        N[v] |= 1 << u;
    }

    f[0] = 0; // 初值

    for (int S = 1; S < (1 << n); S++) {
        f[S] = n;

        // 计算边界点集合 partial(S)
        int partial = 0;
        for (int v = 0; v < n; v++)
            if (S & (1 << v) && (S & N[v]) != N[v])
                partial |= 1 << v;

        // 状态转移
        for (int v = 0; v < n; v++)
            if (S & (1 << v))
                f[S] = min(f[S], max(f[S ^ (1 << v)], __builtin_popcount(partial & ~(1 << v)) + 1));
    }

    cout << f[(1 << n) - 1] << std::endl; // 输出答案
}

Lemma 4.3 设 $T$ 是一棵树， $k$ 是一个正整数。假设对于 $T$ 中的任意顶点 $v \in V(T)$，子图 $T \setminus \{v\}$ 最多只有两个 $ms=k$ 的连通分量，并且没有任何连通分量的 $ms\ge k+1$。那么，$ms(T) \le k$。

Theorem 4.4 对于任意树 $T$ 和正整数 $k$，$ms(T)\ge k+1$ 当且仅当 $T$ 中存在节点 $v$ 使得 $T\setminus \{v\}$ 至少有三个连通分量的 $ms\ge k$。

Corollary 4.5 对于任意树 $T$，$ms(T)\le \log_3(2|V(T)| + 1)$。

Theorem 4.6（Takahashi et al. 1995） 对于任意树 $T$，$ms(T)$ 可以在线性时间内求出。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 1000005;

struct PathVector {
    int p;
    int c;
    PathVector *n;
    PathVector *b;
    PathVector *n_star;
    PathVector *b_star;
    PathVector *btm;

    PathVector(): p(1), c(0), n(nullptr), b(nullptr), n_star(this), b_star(this), btm(this) {}

    void set(int p, int c, PathVector *n = nullptr, PathVector *s = nullptr) {
        this->p = p;
        this->c = c;
        this->n = n;
        if (!s) s = this;
        if (n) {
            n->b = this;
            if (this->p == n->p + 1) {
                this->b_star->n_star = n->n_star;
                n->n_star->b_star = this->b_star;
            } else {
                this->b_star->n_star = this;
            }
            s->btm = n->btm;
        } else {
            this->b_star->n_star = this;
            s->btm = this;
        }
    }
};

vector<int> G[MAXN]; // 邻接表
vector<PathVector*> pv_mem;

PathVector* merge(PathVector* P_s, PathVector* P_t) {
    if (P_s->p > P_t->p) {
        PathVector* P_sn = P_s->n_star;
        if (P_s->c <= 2) P_s->set(P_s->p, P_s->c);
        else if (P_sn->p < P_t->p) P_s->set(P_s->p + 1, 0);
        else if (P_sn->p == P_t->p) {
            if (P_sn->c >= 2 || P_t->c >= 2) P_s->set(P_s->p + 1, 0);
            else P_sn->set(P_sn->p, P_sn->c + 1, nullptr, P_s);
        } else if (P_sn->c <= 2) P_sn->set(P_sn->p, P_sn->c, nullptr, P_s);
        else if (P_sn->c == 3) {
            P_sn->set(P_sn->p, P_sn->c, merge(P_sn->n, P_t), P_s);
            if (P_sn->n->p == P_sn->p) P_s->set(P_s->p + 1, 0);
        }
        return P_s;
    } else if (P_s->p == P_t->p) {
        if (P_s->c >= 2 || P_t->c >= 2) P_s->set(P_s->p + 1, 0);
        else P_s->set(P_s->p, P_s->c + 1);
        return P_s;
    } else { // if P_s->p < P_t->p
        PathVector* P_tn = P_t->n_star;
        if (P_t->c <= 1) P_t->set(P_t->p, 1);
        else if (P_t->c == 2) P_t->set(P_t->p, 3, P_s);
        else if (P_s->p > P_tn->p) P_t->set(P_t->p + 1, 0);
        else if (P_s->p == P_tn->p) {
            if (P_s->c >= 2 || P_tn->c >= 2) P_t->set(P_t->p + 1, 0);   
            else P_tn->set(P_tn->p, P_s->c + 1, nullptr, P_t);
        } else if (P_tn->c <= 1) P_tn->set(P_tn->p, 1, nullptr, P_t);
        else if (P_tn->c == 2) P_tn->set(P_tn->p, 3, P_s, P_t);
        else if (P_tn->c == 3) {
            P_tn->set(P_tn->p, P_tn->c, merge(P_s, P_tn->n), P_t);
            if (P_tn->n->p == P_tn->p) P_t->set(P_t->p + 1, 0);
        }
        return P_t;
    }
}

PathVector* lmerge(PathVector* P_s, PathVector* P_t) {
    if (P_s->p > P_t->p && P_s->c == 3) {
        PathVector* P_prime = P_s->btm->b_star;
        while (P_prime->p < P_t->p) P_prime = P_prime->b->b_star;
        if (P_prime == P_s) P_s = merge(P_s, P_t);
        else P_prime->b->set(P_prime->b->p, P_prime->b->c, merge(P_prime, P_t), P_s);
        return P_s;
    }
    if (P_s->p < P_t->p && P_t->c == 3) {
        PathVector* P_prime = P_t->btm->b_star;
        while (P_prime->p < P_s->p) P_prime = P_prime->b->b_star;
        if (P_prime == P_t) P_t = merge(P_s, P_t);
        else P_prime->b->set(P_prime->b->p, P_prime->b->c, merge(P_s, P_prime), P_t);
        return P_t;
    }
    return merge(P_s, P_t);
}

PathVector* DFS(int u, int f) {
    PathVector* P_u = new PathVector();
    pv_mem.push_back(P_u);
    
    for (int v: G[u]) if (v != f) {
        PathVector* P_v = DFS(v, u);
        P_u = lmerge(P_u, P_v);
    }
    std::cout << "DFS(" << u << ") = " << P_u->p << std::endl;
    return P_u;
}

int main() {
    std::ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    cout << DFS(1, 0)->p << endl;
    for (auto ptr: pv_mem) delete ptr;
    pv_mem.clear();
    return 0;
}

5. NP-Completeness

Theorem 5.1（Megiddo et al. 1988） Edge Searching 是 NP-Complete 的。

Problem 5.2（等规模子集最小割）

• 问题: MIN-CUT INTO EQUAL-SIZED SUBSETS
• 实例: 一个图 $G=(V,E)$，其中 $|V|$ 是偶数，以及一个正整数 $K$。
• 提问: 是否存在一个将 $V$ 划分为两个子集 $V_1$ 和 $V_2$ 的方案，使得 $|V_1|=|V_2|=\frac{1}{2}|V|$，并且连接 $V_1$ 和 $V_2$ 的边的数量（即 $|\{\{u,v\} \in E : u \in V_1, v \in V_2 \}|$）不超过 $K$？

Lemma 5.3 假设在搜索 $K_M$ ($M \ge 4$) 的过程中，在某个步骤 $t$，第一个顶点关联的所有边被完全清理。那么在该步骤中，必然有至少 $M-1$ 个团员位于 $K_M$ 上。