minimumVertexCover<V> function

Set<V> minimumVertexCover<V>({ required Iterable<V> vertices, required Iterable<V> neighboursOf(V vertex), bool approximate = false, StorageStrategy<V>? vertexStrategy, })

Computes a minimum vertex cover of an undirected graph.

If approximate is true, uses a 2-approximation algorithm running in O(|V| + |E|) time. Otherwise, uses an exact algorithm: König's theorem (O(|E| * sqrt(|V|))) if the graph is bipartite, or branch-and-bound search if non-bipartite.

Implementation

Set<V> minimumVertexCover<V>({
  required Iterable<V> vertices,
  required Iterable<V> Function(V vertex) neighboursOf,
  bool approximate = false,
  StorageStrategy<V>? vertexStrategy,
}) {
  vertexStrategy ??= StorageStrategy.defaultStrategy();
  if (approximate) {
    return approximateMinimumVertexCover<V>(
      vertices: vertices,
      neighboursOf: neighboursOf,
      vertexStrategy: vertexStrategy,
    );
  }

  final isBip = bipartite_check.isBipartite<V>(
    vertices: vertices,
    neighboursOf: neighboursOf,
    vertexStrategy: vertexStrategy,
  );
  if (isBip) {
    return bipartite_matching.bipartiteMinimumVertexCover<V>(
      vertices: vertices,
      neighboursOf: neighboursOf,
      vertexStrategy: vertexStrategy,
    );
  }

  final vertexList = vertices.toList(growable: false);
  final n = vertexList.length;
  if (n <= 1) {
    final cover = vertexStrategy.createSet();
    if (n == 1 && neighboursOf(vertexList.first).contains(vertexList.first)) {
      cover.add(vertexList.first);
    }
    return cover;
  }

  final vertexIndex = vertexStrategy.createMap<int>();
  for (var i = 0; i < n; i++) {
    vertexIndex[vertexList[i]] = i;
  }

  final edges = <(int, int)>[];
  final selfLoops = <int>{};
  for (var i = 0; i < n; i++) {
    for (final neighbor in neighboursOf(vertexList[i])) {
      final j = vertexIndex[neighbor];
      if (j != null) {
        if (i == j) {
          selfLoops.add(i);
        } else if (i < j) {
          edges.add((i, j));
        }
      }
    }
  }

  var bestCoverIndices = List<int>.generate(n, (i) => i);
  final currentCover = <int>{...selfLoops};

  void search(int edgeIdx) {
    if (currentCover.length >= bestCoverIndices.length) {
      return;
    }

    while (edgeIdx < edges.length) {
      final (u, v) = edges[edgeIdx];
      if (!currentCover.contains(u) && !currentCover.contains(v)) {
        break;
      }
      edgeIdx++;
    }

    if (edgeIdx == edges.length) {
      bestCoverIndices = currentCover.toList();
      return;
    }

    final (u, v) = edges[edgeIdx];

    currentCover.add(u);
    search(edgeIdx + 1);
    currentCover.remove(u);

    currentCover.add(v);
    search(edgeIdx + 1);
    currentCover.remove(v);
  }

  search(0);

  final result = vertexStrategy.createSet();
  for (final idx in bestCoverIndices) {
    result.add(vertexList[idx]);
  }
  return result;
}