图的特殊点集和边集 学习笔记

· · 个人记录

支配集

一张无向图，如果一个点集使所有点要么在点集中，要么与点集中的一个点相邻，则称这个点集是图的一个支配集。最小支配集大小记作 \gamma(G)。求一般图的最小支配集是 NP-hard 的。

考虑如何求树的最小支配集，有贪心和 DP 两种方式。DP 设 f_{i,0/1/2} 表示 i 被儿子/自己/父亲支配，子树的答案。贪心时，按 DFS 序倒序处理，能保证当前节点的子树除了根都已经被支配。如果这个节点未被支配，则有将当前节点或父节点加入支配集两种方式，显然后者更优。

点覆盖

一张无向图，如果一个点集使所有边的至少一个端点在点集中，则称这个点集是图的一个点覆盖。求一般图的最小点覆盖是 NP-hard 的。

二分图的最小点覆盖有一重要性质 König 定理：最小点覆盖等于最大匹配。

树的点覆盖容易 DP，设 f_{i,0/1} 表示子树内 i 选/不选的答案，即 f_{u,0}=\sum_{v\in son_u}f_{v,1},f_{u,1}=\sum_{v\in son_u}\min(f_{v,0},f_{v,1})。

独立集

一张无向图，选出一些点互不相邻，称为独立集。最大独立集大小记作 \alpha(G)。求一般图的最大独立集是 NP-hard 的。

在任意图中，一个点集是点覆盖的充要条件是补集为独立集。点覆盖的定义为所有边至少一个端点在点集中，则边至多一个端点在点集的补集中。同理可以反推。因此最小点覆盖的补集为最大独立集。最大权独立集同理。

求最大独立集和最大团是可以互通的，下文会介绍最大团的 O(n2^\frac n2),O(2^\frac n2) 算法。最大独立集存在一个搜索算法：若当前最大度数 \leq2，则每个连通块是链或环，容易直接 DFS 求解。否则，讨论图中度数最大的点是否取在最大独立集中，分别递归到两个子问题，一个规模少 1，另一个规模至少少 4。复杂度为 T(n)=T(n-1)+T(n-4)+\operatorname{poly}(n)\approx O(1.3803^n\operatorname{poly}(n))。如下是 P12371代码。

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long e[55];
struct info{
  long long cnt,s;
  info(){
    cnt=1,s=0;
  }
  info(long long b,long long c){
    cnt=b,s=c;
  }
  info(long long t){
    cnt=1,s=t;
  }
};
info merge(info a,long long s){
  return a.s|=s,a;
}
info cmp(info a,info b){
  if(__builtin_popcountll(a.s)>__builtin_popcountll(b.s))return a;
  if(__builtin_popcountll(a.s)<__builtin_popcountll(b.s))return b;
  return info(a.cnt+b.cnt,a.s);
}
void dfs(int pos,long long s,long long e[],long long&vis,long long&s1,long long&s2,bool&type){
  vis^=1ll<<(pos-1),s1|=1ll<<(pos-1),type&=__builtin_popcountll(e[pos]&s)==2;
  while(vis&e[pos])dfs(__builtin_ctzll(vis&e[pos])+1,s,e,vis,s2,s1,type);
}
info solve(long long s,int n,long long e[]){
  if(!s)return info();
  int u,maxd=-1;
  for(int i=1;i<=n;i++)if(s>>(i-1)&1&&__builtin_popcountll(e[i]&s)>maxd)u=i,maxd=__builtin_popcountll(e[i]&s);
  if(maxd<=2){
    info ans(1,0);
    long long vis=s;
    while(vis){
      int a,b,cnt;
      bool type=1;
      long long s1=0,s2=0;
      dfs(__builtin_ctzll(vis)+1,s,e,vis,s1,s2,type),a=__builtin_popcountll(s1),b=__builtin_popcountll(s2),cnt=a+b;
      if(cnt&1)ans.cnt*=type?cnt:1,ans.s|=type?a<b?s1:s2:a>b?s1:s2;
      else ans.cnt*=type?2:cnt/2+1,ans.s|=s1;
    }
    return ans;
  }
  return cmp(solve(s^(1ll<<(u-1)),n,e),merge(solve(s&(~e[u]^(1ll<<(u-1))),n,e),1ll<<(u-1)));
}
int main(){
  cin>>n>>m;
  for(int i=1,u,v;i<=m;i++)cin>>u>>v,e[u]|=1ll<<(v-1),e[v]|=1ll<<(u-1);
  for(int i=1;i<=n;i++)e[i]^=((1ll<<n)-1)^(1ll<<(i-1));
  info ans=solve((1ll<<n)-1,n,e);
  cout<<__builtin_popcountll(ans.s)<<' '<<ans.cnt<<'\n';
  for(int i=1;i<=n;i++)if(ans.s>>(i-1)&1)cout<<i<<' ';
  putchar('\n');
  for(int i=1;i<=n;i++)e[i]^=((1ll<<n)-1)^(1ll<<(i-1));
  ans=solve((1ll<<n)-1,n,e),cout<<__builtin_popcountll(ans.s)<<' '<<ans.cnt<<'\n';
  for(int i=1;i<=n;i++)if(ans.s>>(i-1)&1)cout<<i<<' ';
  return putchar('\n'),0;
}

最大团

一张无向图，选出一些点两两都有边，称为最大团。最大团大小记作 \omega(G)。显然最大团等于补图最大独立集，补图中两个点有边当且仅当原图中两个点没边。

求最大团，容易想到 meet in the middle，枚举后半的团，设其邻域在前半部分的交为 S，我们需要求导出子图 G[S] 的团数，设为 f_S。容易想到的做法是做一遍高维前缀和 O(n2^{\frac n2})。

更好的方法是对于 S 中的一个点 u，讨论它是否在所选团内，有 f_S=\max(f_{S\setminus\{u\}},f_{S\cap N(u)}+1)。事实上此时我们可以不用 meet in the middie，直接对所有集合按上式转移，记忆化最大编号 \leq\frac n2 的 f_S。这里有一个自然根号，每次取编号最大的 u，按节点最大编号分层，\leq\frac n2 的 S 记忆化后 O(2^\frac n2)，>\frac n2 的因为只以全集为起点搜索，每次会分出两个最大编号少一的子问题，也是 O(2^\frac n2)。

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long e[55];
struct info{
  long long cnt,s;
  info(){
    cnt=1,s=0;
  }
  info(long long b,long long c){
    cnt=b,s=c;
  }
  info(long long t){
    cnt=1,s=t;
  }
}f[33554432];
info merge(info a,long long s){
  return a.s|=s,a;
}
info cmp(info a,info b){
  if(__builtin_popcountll(a.s)>__builtin_popcountll(b.s))return a;
  if(__builtin_popcountll(a.s)<__builtin_popcountll(b.s))return b;
  return info(a.cnt+b.cnt,a.s);
}
info dfs(long long s,int n,long long e[]){
  if(!s||(s<1<<n/2&&f[s].s))return f[s];
  int u=__lg(s)+1;
  info ans=cmp(dfs(s^(1ll<<(u-1)),n,e),merge(dfs(s&e[u],n,e),1ll<<(u-1)));
  if(s<1<<n/2)f[s]=ans;
  return ans;
}
int main(){
  cin>>n>>m;
  for(int i=1,u,v;i<=m;i++)cin>>u>>v,e[u]|=1ll<<(v-1),e[v]|=1ll<<(u-1);
  info ans=dfs((1ll<<n)-1,n,e);
  cout<<__builtin_popcountll(ans.s)<<' '<<ans.cnt<<'\n';
  for(int i=1;i<=n;i++)if(ans.s>>(i-1)&1)cout<<i<<' ';
  putchar('\n');
  for(int i=1;i<=n;i++)e[i]^=((1ll<<n)-1)^(1ll<<(i-1));
  for(int i=0;i<1<<n/2;i++)f[i]=info();
  ans=dfs((1ll<<n)-1,n,e),cout<<__builtin_popcountll(ans.s)<<' '<<ans.cnt<<'\n';
  for(int i=1;i<=n;i++)if(ans.s>>(i-1)&1)cout<<i<<' ';
  return putchar('\n'),0;
}