Maximum Clique, Independent Set, and Vertex Cover
(graph/maximum_clique.hpp)

• View this file on GitHub
• Last update: 2026-08-13 01:41:40+09:00
• Include: #include "graph/maximum_clique.hpp"

Overview

This header solves three exact NP-hard problems on general undirected graphs:

• maximum clique;
• maximum independent set;
• minimum vertex cover.

A clique is a vertex set where every pair of vertices has an edge. An independent set is a vertex set where no pair of vertices has an edge. A vertex cover is a vertex set that touches every edge.

These problems are still exponential in the worst case. The implementation is not a naive 2^N subset scan: it uses a branching maximum independent set solver. Maximum clique is computed as maximum independent set in the complement graph.

Graph Orientation

Direction is ignored. Every active edge of Graph<T> is treated as an undirected edge between its endpoints. Self-loops are ignored because they do not help a clique or an independent set.

How It Works

The core solver is for maximum independent set.

If every remaining vertex has degree at most 2, each connected component is a path, a cycle, or an isolated vertex. Those components are solved directly by dynamic programming.

Otherwise, let v be a maximum-degree vertex. Since the maximum degree is at least 3, the solver branches into these two cases:

• do not use v, so only v is removed;
• use v, so v and all its neighbors are removed.

The second branch removes at least 4 vertices.

For maximum clique, the solver builds the complement graph: two vertices are connected in the complement exactly when they are not connected in the original graph. An independent set in the complement is a clique in the original graph.

For minimum vertex cover, the solver uses the fact that a set C is a vertex cover exactly when its complement V - C is an independent set. Therefore, the minimum vertex cover is the complement of a maximum independent set.

Complexity Note

Let N be the number of vertices. This implementation is exact and has exponential worst-case complexity. The branching step gives the recurrence

T(N) <= T(N - 1) + T(N - 4)

The positive root of x^4 = x^3 + 1 is about 1.381, so the search tree is bounded by $O(1.381^N)$. With the polynomial work in each node, the usual bound for this branching algorithm is written as $O(1.381^N \cdot N)$ when adjacency bookkeeping is implemented linearly.

The implementation follows that branching algorithm. It stores adjacency lists and copies the active-vertex set during recursion, so the simple header implementation may have a slightly larger polynomial constant than a hand-tuned contest implementation with incremental degree bookkeeping, but the exponential part is the 1.381^N branching bound.

Result Types

MaximumCliqueResult contains these members:

Member / Method	Type / Signature	Meaning
vertices	std::vector<int>	Vertices in one maximum clique.
size	int size() const	Returns vertices.size().
empty	bool empty() const	Returns whether vertices is empty.

MaximumIndependentSetResult contains these members:

Member / Method	Type / Signature	Meaning
vertices	std::vector<int>	Vertices in one maximum independent set.
size	int size() const	Returns vertices.size().
empty	bool empty() const	Returns whether vertices is empty.

MinimumVertexCoverResult contains these members:

Member / Method	Type / Signature	Meaning
vertices	std::vector<int>	Vertices in one minimum vertex cover.
size	int size() const	Returns vertices.size().
empty	bool empty() const	Returns whether vertices is empty.

Returned vertices are sorted in increasing order.

Functions

Function	Signature	Description	Complexity
maximum_clique	template <class T> MaximumCliqueResult maximum_clique(const Graph<T>& g)	Returns one maximum clique.	$O(1.381^N \cdot N)$ branching bound
maximum_clique_size	template <class T> int maximum_clique_size(const Graph<T>& g)	Returns the size of a maximum clique.	$O(1.381^N \cdot N)$ branching bound
maximum_independent_set	template <class T> MaximumIndependentSetResult maximum_independent_set(const Graph<T>& g)	Returns one maximum independent set.	$O(1.381^N \cdot N)$ branching bound
maximum_independent_set_size	template <class T> int maximum_independent_set_size(const Graph<T>& g)	Returns the size of a maximum independent set.	$O(1.381^N \cdot N)$ branching bound
minimum_vertex_cover	template <class T> MinimumVertexCoverResult minimum_vertex_cover(const Graph<T>& g)	Returns one minimum vertex cover.	$O(1.381^N \cdot N)$ branching bound
minimum_vertex_cover_size	template <class T> int minimum_vertex_cover_size(const Graph<T>& g)	Returns the size of a minimum vertex cover.	$O(1.381^N \cdot N)$ branching bound
is_clique	template <class T> bool is_clique(const Graph<T>& g, const std::vector<int>& vertices)	Checks whether vertices is a clique.	$O(N + M + K^2)$
is_independent_set	template <class T> bool is_independent_set(const Graph<T>& g, const std::vector<int>& vertices)	Checks whether vertices is an independent set.	$O(N + M + K^2)$
is_vertex_cover	template <class T> bool is_vertex_cover(const Graph<T>& g, const std::vector<int>& vertices)	Checks whether vertices is a vertex cover.	$O(N + M + K)$

Here, K = vertices.size().

Example

#include "graph/graph.hpp"
#include "graph/maximum_clique.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<> g(5);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 2);
    g.add_edge(3, 4);

    auto clique = m1une::graph::maximum_clique(g);
    auto independent = m1une::graph::maximum_independent_set(g);
    auto cover = m1une::graph::minimum_vertex_cover(g);

    std::cout << clique.size() << "\n";       // 3
    std::cout << independent.size() << "\n";  // 2
    std::cout << cover.size() << "\n";        // 2
}

Depends on

• Graph (graph/graph.hpp)

Required by

• Graph All (graph/all.hpp)
• Undirected Graph Algorithms (graph/undirected.hpp)

Verified with

• verify/graph/cow_game.test.cpp
• verify/graph/graph_algorithms.test.cpp
• verify/graph/library_checker_maximum_independent_set.test.cpp
• verify/graph/range_edge_graph.test.cpp

Code

#ifndef M1UNE_GRAPH_MAXIMUM_CLIQUE_HPP
#define M1UNE_GRAPH_MAXIMUM_CLIQUE_HPP 1

#include <algorithm>
#include <cassert>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

struct MaximumCliqueResult {
    std::vector<int> vertices;

    int size() const {
        return int(vertices.size());
    }

    bool empty() const {
        return vertices.empty();
    }
};

struct MaximumIndependentSetResult {
    std::vector<int> vertices;

    int size() const {
        return int(vertices.size());
    }

    bool empty() const {
        return vertices.empty();
    }
};

struct MinimumVertexCoverResult {
    std::vector<int> vertices;

    int size() const {
        return int(vertices.size());
    }

    bool empty() const {
        return vertices.empty();
    }
};

namespace detail {

struct MaximumIndependentSetBranching {
    int n;
    std::vector<std::vector<char>> adjacent;
    std::vector<std::vector<int>> graph;

    explicit MaximumIndependentSetBranching(const std::vector<std::vector<char>>& adjacent_)
        : n(int(adjacent_.size())), adjacent(adjacent_), graph(n) {
        for (int v = 0; v < n; v++) {
            for (int to = 0; to < n; to++) {
                if (adjacent[v][to]) graph[v].push_back(to);
            }
        }
    }

    std::vector<int> solve_path(const std::vector<int>& order) const {
        int m = int(order.size());
        if (m == 0) return {};

        std::vector<int> dp0(m, 0), dp1(m, 0);
        dp1[0] = 1;
        for (int i = 1; i < m; i++) {
            dp0[i] = std::max(dp0[i - 1], dp1[i - 1]);
            dp1[i] = dp0[i - 1] + 1;
        }

        std::vector<int> result;
        int state = (dp1[m - 1] > dp0[m - 1] ? 1 : 0);
        for (int i = m - 1; i >= 0; i--) {
            if (state == 1) {
                result.push_back(order[i]);
                state = 0;
            } else if (i > 0) {
                state = (dp1[i - 1] > dp0[i - 1] ? 1 : 0);
            }
        }
        return result;
    }

    std::vector<int> solve_cycle(const std::vector<int>& order) const {
        int m = int(order.size());
        if (m == 0) return {};
        if (m == 1) return {order[0]};

        std::vector<int> without_first(order.begin() + 1, order.end());
        auto result_without = solve_path(without_first);

        std::vector<int> result_with = {order[0]};
        if (m >= 4) {
            std::vector<int> middle(order.begin() + 2, order.end() - 1);
            auto middle_result = solve_path(middle);
            result_with.insert(result_with.end(), middle_result.begin(), middle_result.end());
        }

        return (result_with.size() > result_without.size() ? result_with : result_without);
    }

    std::vector<int> solve_degree_at_most_two(const std::vector<char>& active,
                                              const std::vector<int>& degree) const {
        std::vector<int> result;
        std::vector<char> visited(n, false);

        for (int s = 0; s < n; s++) {
            if (!active[s] || visited[s]) continue;

            std::vector<int> component;
            std::vector<int> stack = {s};
            visited[s] = true;
            for (int it = 0; it < int(stack.size()); it++) {
                int v = stack[it];
                component.push_back(v);
                for (int to : graph[v]) {
                    if (!active[to] || visited[to]) continue;
                    visited[to] = true;
                    stack.push_back(to);
                }
            }

            if (component.size() == 1) {
                result.push_back(component[0]);
                continue;
            }

            int endpoint = -1;
            for (int v : component) {
                if (degree[v] <= 1) {
                    endpoint = v;
                    break;
                }
            }

            std::vector<int> order;
            if (endpoint != -1) {
                int prev = -1, cur = endpoint;
                while (cur != -1) {
                    order.push_back(cur);
                    int next = -1;
                    for (int to : graph[cur]) {
                        if (active[to] && to != prev) {
                            next = to;
                            break;
                        }
                    }
                    prev = cur;
                    cur = next;
                }
                auto part = solve_path(order);
                result.insert(result.end(), part.begin(), part.end());
            } else {
                int start = component[0];
                int first = -1;
                for (int to : graph[start]) {
                    if (active[to]) {
                        first = to;
                        break;
                    }
                }
                assert(first != -1);

                order.push_back(start);
                int prev = start, cur = first;
                while (cur != start) {
                    order.push_back(cur);
                    int next = -1;
                    for (int to : graph[cur]) {
                        if (active[to] && to != prev) {
                            next = to;
                            break;
                        }
                    }
                    assert(next != -1);
                    prev = cur;
                    cur = next;
                }
                auto part = solve_cycle(order);
                result.insert(result.end(), part.begin(), part.end());
            }
        }

        return result;
    }

    std::vector<int> solve(std::vector<char> active) const {
        int active_count = 0;
        int max_degree = -1;
        int branch_vertex = -1;
        std::vector<int> degree(n, 0);

        for (int v = 0; v < n; v++) {
            if (!active[v]) continue;
            active_count++;
            for (int to : graph[v]) {
                if (active[to]) degree[v]++;
            }
            if (degree[v] > max_degree) {
                max_degree = degree[v];
                branch_vertex = v;
            }
        }

        if (active_count == 0) return {};
        if (max_degree <= 2) {
            auto result = solve_degree_at_most_two(active, degree);
            std::sort(result.begin(), result.end());
            return result;
        }

        auto without = active;
        without[branch_vertex] = false;
        auto result_without = solve(without);

        auto with = active;
        with[branch_vertex] = false;
        for (int to : graph[branch_vertex]) with[to] = false;
        auto result_with = solve(with);
        result_with.push_back(branch_vertex);

        auto result = (result_with.size() > result_without.size() ? result_with : result_without);
        std::sort(result.begin(), result.end());
        return result;
    }

    std::vector<int> solve() const {
        std::vector<char> active(n, true);
        return solve(active);
    }
};

template <class T>
std::vector<std::vector<char>> undirected_adjacency_matrix(const Graph<T>& g) {
    int n = g.size();
    std::vector<std::vector<char>> adjacent(n, std::vector<char>(n, false));
    for (const auto& e : g.edges()) {
        if (e.from == e.to) continue;
        adjacent[e.from][e.to] = true;
        adjacent[e.to][e.from] = true;
    }
    return adjacent;
}

std::vector<std::vector<char>> complement_adjacency_matrix(const std::vector<std::vector<char>>& adjacent) {
    int n = int(adjacent.size());
    std::vector<std::vector<char>> complement(n, std::vector<char>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (adjacent[i][j]) continue;
            complement[i][j] = true;
            complement[j][i] = true;
        }
    }
    return complement;
}

}  // namespace detail

template <class T>
bool is_clique(const Graph<T>& g, const std::vector<int>& vertices) {
    auto adjacent = detail::undirected_adjacency_matrix(g);
    for (int v : vertices) {
        assert(0 <= v && v < g.size());
    }
    for (int i = 0; i < int(vertices.size()); i++) {
        for (int j = i + 1; j < int(vertices.size()); j++) {
            if (!adjacent[vertices[i]][vertices[j]]) return false;
        }
    }
    return true;
}

template <class T>
bool is_independent_set(const Graph<T>& g, const std::vector<int>& vertices) {
    auto adjacent = detail::undirected_adjacency_matrix(g);
    for (int v : vertices) {
        assert(0 <= v && v < g.size());
    }
    for (int i = 0; i < int(vertices.size()); i++) {
        for (int j = i + 1; j < int(vertices.size()); j++) {
            if (adjacent[vertices[i]][vertices[j]]) return false;
        }
    }
    return true;
}

template <class T>
bool is_vertex_cover(const Graph<T>& g, const std::vector<int>& vertices) {
    std::vector<char> selected(g.size(), false);
    for (int v : vertices) {
        assert(0 <= v && v < g.size());
        selected[v] = true;
    }
    for (const auto& e : g.edges()) {
        if (e.from == e.to) continue;
        if (!selected[e.from] && !selected[e.to]) return false;
    }
    return true;
}

template <class T>
MaximumCliqueResult maximum_clique(const Graph<T>& g) {
    auto adjacent = detail::undirected_adjacency_matrix(g);
    auto complement = detail::complement_adjacency_matrix(adjacent);
    detail::MaximumIndependentSetBranching solver(complement);
    return MaximumCliqueResult{solver.solve()};
}

template <class T>
int maximum_clique_size(const Graph<T>& g) {
    return maximum_clique(g).size();
}

template <class T>
MaximumIndependentSetResult maximum_independent_set(const Graph<T>& g) {
    auto adjacent = detail::undirected_adjacency_matrix(g);
    detail::MaximumIndependentSetBranching solver(adjacent);
    return MaximumIndependentSetResult{solver.solve()};
}

template <class T>
int maximum_independent_set_size(const Graph<T>& g) {
    return maximum_independent_set(g).size();
}

template <class T>
MinimumVertexCoverResult minimum_vertex_cover(const Graph<T>& g) {
    auto independent = maximum_independent_set(g);
    std::vector<char> in_independent(g.size(), false);
    for (int v : independent.vertices) in_independent[v] = true;

    MinimumVertexCoverResult result;
    for (int v = 0; v < g.size(); v++) {
        if (!in_independent[v]) result.vertices.push_back(v);
    }
    return result;
}

template <class T>
int minimum_vertex_cover_size(const Graph<T>& g) {
    return minimum_vertex_cover(g).size();
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_MAXIMUM_CLIQUE_HPP

#line 1 "graph/maximum_clique.hpp"



#include <algorithm>
#include <cassert>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 6 "graph/graph.hpp"
#include <utility>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 9 "graph/maximum_clique.hpp"

namespace m1une {
namespace graph {

struct MaximumCliqueResult {
    std::vector<int> vertices;

    int size() const {
        return int(vertices.size());
    }

    bool empty() const {
        return vertices.empty();
    }
};

struct MaximumIndependentSetResult {
    std::vector<int> vertices;

    int size() const {
        return int(vertices.size());
    }

    bool empty() const {
        return vertices.empty();
    }
};

struct MinimumVertexCoverResult {
    std::vector<int> vertices;

    int size() const {
        return int(vertices.size());
    }

    bool empty() const {
        return vertices.empty();
    }
};

namespace detail {

struct MaximumIndependentSetBranching {
    int n;
    std::vector<std::vector<char>> adjacent;
    std::vector<std::vector<int>> graph;

    explicit MaximumIndependentSetBranching(const std::vector<std::vector<char>>& adjacent_)
        : n(int(adjacent_.size())), adjacent(adjacent_), graph(n) {
        for (int v = 0; v < n; v++) {
            for (int to = 0; to < n; to++) {
                if (adjacent[v][to]) graph[v].push_back(to);
            }
        }
    }

    std::vector<int> solve_path(const std::vector<int>& order) const {
        int m = int(order.size());
        if (m == 0) return {};

        std::vector<int> dp0(m, 0), dp1(m, 0);
        dp1[0] = 1;
        for (int i = 1; i < m; i++) {
            dp0[i] = std::max(dp0[i - 1], dp1[i - 1]);
            dp1[i] = dp0[i - 1] + 1;
        }

        std::vector<int> result;
        int state = (dp1[m - 1] > dp0[m - 1] ? 1 : 0);
        for (int i = m - 1; i >= 0; i--) {
            if (state == 1) {
                result.push_back(order[i]);
                state = 0;
            } else if (i > 0) {
                state = (dp1[i - 1] > dp0[i - 1] ? 1 : 0);
            }
        }
        return result;
    }

    std::vector<int> solve_cycle(const std::vector<int>& order) const {
        int m = int(order.size());
        if (m == 0) return {};
        if (m == 1) return {order[0]};

        std::vector<int> without_first(order.begin() + 1, order.end());
        auto result_without = solve_path(without_first);

        std::vector<int> result_with = {order[0]};
        if (m >= 4) {
            std::vector<int> middle(order.begin() + 2, order.end() - 1);
            auto middle_result = solve_path(middle);
            result_with.insert(result_with.end(), middle_result.begin(), middle_result.end());
        }

        return (result_with.size() > result_without.size() ? result_with : result_without);
    }

    std::vector<int> solve_degree_at_most_two(const std::vector<char>& active,
                                              const std::vector<int>& degree) const {
        std::vector<int> result;
        std::vector<char> visited(n, false);

        for (int s = 0; s < n; s++) {
            if (!active[s] || visited[s]) continue;

            std::vector<int> component;
            std::vector<int> stack = {s};
            visited[s] = true;
            for (int it = 0; it < int(stack.size()); it++) {
                int v = stack[it];
                component.push_back(v);
                for (int to : graph[v]) {
                    if (!active[to] || visited[to]) continue;
                    visited[to] = true;
                    stack.push_back(to);
                }
            }

            if (component.size() == 1) {
                result.push_back(component[0]);
                continue;
            }

            int endpoint = -1;
            for (int v : component) {
                if (degree[v] <= 1) {
                    endpoint = v;
                    break;
                }
            }

            std::vector<int> order;
            if (endpoint != -1) {
                int prev = -1, cur = endpoint;
                while (cur != -1) {
                    order.push_back(cur);
                    int next = -1;
                    for (int to : graph[cur]) {
                        if (active[to] && to != prev) {
                            next = to;
                            break;
                        }
                    }
                    prev = cur;
                    cur = next;
                }
                auto part = solve_path(order);
                result.insert(result.end(), part.begin(), part.end());
            } else {
                int start = component[0];
                int first = -1;
                for (int to : graph[start]) {
                    if (active[to]) {
                        first = to;
                        break;
                    }
                }
                assert(first != -1);

                order.push_back(start);
                int prev = start, cur = first;
                while (cur != start) {
                    order.push_back(cur);
                    int next = -1;
                    for (int to : graph[cur]) {
                        if (active[to] && to != prev) {
                            next = to;
                            break;
                        }
                    }
                    assert(next != -1);
                    prev = cur;
                    cur = next;
                }
                auto part = solve_cycle(order);
                result.insert(result.end(), part.begin(), part.end());
            }
        }

        return result;
    }

    std::vector<int> solve(std::vector<char> active) const {
        int active_count = 0;
        int max_degree = -1;
        int branch_vertex = -1;
        std::vector<int> degree(n, 0);

        for (int v = 0; v < n; v++) {
            if (!active[v]) continue;
            active_count++;
            for (int to : graph[v]) {
                if (active[to]) degree[v]++;
            }
            if (degree[v] > max_degree) {
                max_degree = degree[v];
                branch_vertex = v;
            }
        }

        if (active_count == 0) return {};
        if (max_degree <= 2) {
            auto result = solve_degree_at_most_two(active, degree);
            std::sort(result.begin(), result.end());
            return result;
        }

        auto without = active;
        without[branch_vertex] = false;
        auto result_without = solve(without);

        auto with = active;
        with[branch_vertex] = false;
        for (int to : graph[branch_vertex]) with[to] = false;
        auto result_with = solve(with);
        result_with.push_back(branch_vertex);

        auto result = (result_with.size() > result_without.size() ? result_with : result_without);
        std::sort(result.begin(), result.end());
        return result;
    }

    std::vector<int> solve() const {
        std::vector<char> active(n, true);
        return solve(active);
    }
};

template <class T>
std::vector<std::vector<char>> undirected_adjacency_matrix(const Graph<T>& g) {
    int n = g.size();
    std::vector<std::vector<char>> adjacent(n, std::vector<char>(n, false));
    for (const auto& e : g.edges()) {
        if (e.from == e.to) continue;
        adjacent[e.from][e.to] = true;
        adjacent[e.to][e.from] = true;
    }
    return adjacent;
}

std::vector<std::vector<char>> complement_adjacency_matrix(const std::vector<std::vector<char>>& adjacent) {
    int n = int(adjacent.size());
    std::vector<std::vector<char>> complement(n, std::vector<char>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (adjacent[i][j]) continue;
            complement[i][j] = true;
            complement[j][i] = true;
        }
    }
    return complement;
}

}  // namespace detail

template <class T>
bool is_clique(const Graph<T>& g, const std::vector<int>& vertices) {
    auto adjacent = detail::undirected_adjacency_matrix(g);
    for (int v : vertices) {
        assert(0 <= v && v < g.size());
    }
    for (int i = 0; i < int(vertices.size()); i++) {
        for (int j = i + 1; j < int(vertices.size()); j++) {
            if (!adjacent[vertices[i]][vertices[j]]) return false;
        }
    }
    return true;
}

template <class T>
bool is_independent_set(const Graph<T>& g, const std::vector<int>& vertices) {
    auto adjacent = detail::undirected_adjacency_matrix(g);
    for (int v : vertices) {
        assert(0 <= v && v < g.size());
    }
    for (int i = 0; i < int(vertices.size()); i++) {
        for (int j = i + 1; j < int(vertices.size()); j++) {
            if (adjacent[vertices[i]][vertices[j]]) return false;
        }
    }
    return true;
}

template <class T>
bool is_vertex_cover(const Graph<T>& g, const std::vector<int>& vertices) {
    std::vector<char> selected(g.size(), false);
    for (int v : vertices) {
        assert(0 <= v && v < g.size());
        selected[v] = true;
    }
    for (const auto& e : g.edges()) {
        if (e.from == e.to) continue;
        if (!selected[e.from] && !selected[e.to]) return false;
    }
    return true;
}

template <class T>
MaximumCliqueResult maximum_clique(const Graph<T>& g) {
    auto adjacent = detail::undirected_adjacency_matrix(g);
    auto complement = detail::complement_adjacency_matrix(adjacent);
    detail::MaximumIndependentSetBranching solver(complement);
    return MaximumCliqueResult{solver.solve()};
}

template <class T>
int maximum_clique_size(const Graph<T>& g) {
    return maximum_clique(g).size();
}

template <class T>
MaximumIndependentSetResult maximum_independent_set(const Graph<T>& g) {
    auto adjacent = detail::undirected_adjacency_matrix(g);
    detail::MaximumIndependentSetBranching solver(adjacent);
    return MaximumIndependentSetResult{solver.solve()};
}

template <class T>
int maximum_independent_set_size(const Graph<T>& g) {
    return maximum_independent_set(g).size();
}

template <class T>
MinimumVertexCoverResult minimum_vertex_cover(const Graph<T>& g) {
    auto independent = maximum_independent_set(g);
    std::vector<char> in_independent(g.size(), false);
    for (int v : independent.vertices) in_independent[v] = true;

    MinimumVertexCoverResult result;
    for (int v = 0; v < g.size(); v++) {
        if (!in_independent[v]) result.vertices.push_back(v);
    }
    return result;
}

template <class T>
int minimum_vertex_cover_size(const Graph<T>& g) {
    return minimum_vertex_cover(g).size();
}

}  // namespace graph
}  // namespace m1une

Back to top page