AOJ1015 Dominating Set - nanikakaのAOJ航海日誌

概要

グラフG = (V, E)の支配集合Dとは、D ⊆ V で、V-Dの全ての頂点が、少なくとも1つのDと隣接しているようなもののことを言う。
与えられるグラフの支配集合のうち、最小の要素数を答えよ。

解法

この問題、おっそろしいことにグラフの大きさに関して制約が一切書いていません。
最小の支配集合を求める効率的なアルゴリズムはまだ見つかっていない(NP困難)ので頑張って、DFS+枝刈りで解きました。
普通に考えると支配集合Dに頂点を入れる入れないで、O(2^N)のアルゴリズムが思い付きますが、グラフのサイズが分からないので不安です。次のような工夫を施しました。
1. 孤立頂点kは必ずDに含める
2. 次数1の頂点が隣接しているような頂点kはDに含めれば絶対に損しない
この2つのどちらかを満たす頂点kについて、「Dに含めない」という分岐をしないようにしておきます。
更に、再帰中に支配集合を作成不可能になったら枝刈りなどの工夫を入れています。
ソースにコメントを残しておきました。

ソース

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//Dominating Set
public class AOJ1015 {

	int n, m, res, INF = 1<<29;
	List<Integer>[] adj;
	int[] cover;
	boolean[] special;
	
	void f(int k, int num){
		if(res <= num)return;
		if(k==n){
			boolean ok = true;
			for(int i=0;i<n&&ok;i++)ok&=cover[i]!=0;
			if(ok)res = Math.min(res, num);
			return;
		}
		//スペシャルマークがついている場所は振る舞いが決定している
		if(special[k]){
			f(k+1, num); return;
		}
		//[0, k)の頂点に、「カバーされていない && 隣接点が全てk未満」 なものがあった場合、もう支配集合は作れないので枝刈り
		for(int i=0;i<k;i++)if(cover[i]==0){
			boolean e = false;
			for(int x:adj[i])if(k<=x){
				e = true; break;
			}
			if(!e)return;
		}
		//kの頂点を採用する場合としない場合で枝分かれする
		//試す順番を分けている
		//kの頂点がカバーされていない OR 隣接点が多い(適当にn/5個以上とした)場合は取った方が得そうなので、kを採用する場合を先に試している
		if(cover[k]==0 || n/5 <= adj[k].size()){
			cover[k]++;
			for(int x:adj[k])cover[x]++;
			f(k+1, num+1);
			cover[k]--;
			for(int x:adj[k])cover[x]--;
			f(k+1, num);
		}
		else{
			f(k+1, num);
			cover[k]++;
			for(int x:adj[k])cover[x]++;
			f(k+1, num+1);
			cover[k]--;
			for(int x:adj[k])cover[x]--;
		}
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt(); m = sc.nextInt();
			if((n|m)==0)break;
			adj = new List[n];
			for(int i=0;i<n;i++)adj[i]=new ArrayList<Integer>();
			while(m--!=0){
				int s = sc.nextInt(), t = sc.nextInt();
				adj[s].add(t); adj[t].add(s);
			}
			cover = new int[n];
			special = new boolean[n];
			res = INF;
			int c = 0;
			for(int i=0;i<n;i++){
				if(adj[i].isEmpty()){
					c++;
					cover[i]++;
					special[i] = true;
					continue;
				}
				boolean f = false;
				for(int x:adj[i])if(adj[x].size()==1 && !special[x]){
					f = true; break;
				}
				if(f){
					c++;
					special[i] = true;
					cover[i]++;
					for(int x:adj[i])cover[x]++;
				}
			}
			f(0, c);
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1015().run();
	}
}