description: Recognize treewidth at most two and construct a decomposition. Repeatedly remove a live vertex of degree at most two; when it has two neighbors, add the missing edge between them. This reduction is exact: suppressing a degree-two vertex produces a minor, while a decomposition of the filled graph extends by attaching the bag {vertex, first, second}. Reversing the eliminations and attaching each new bag to a later bag that contains its surviving neighbor set yields bags of size at most three.¶
tree_decomposition_width_two.hpp¶
Recognize treewidth at most two and construct a decomposition. Repeatedly remove a live vertex of degree at most two; when it has two neighbors, add the missing edge between them. This reduction is exact: suppressing a degree-two vertex produces a minor, while a decomposition of the filled graph extends by attaching the bag {vertex, first, second}. Reversing the eliminations and attaching each new bag to a later bag that contains its surviving neighbor set yields bags of size at most three.
Verified by tree_decomposition_width_2.
识别并构造宽度不超过 2 的树分解；适合系列并行图或小树宽 DP。
Implementation¶
#ifndef NOYA_TREE_DECOMPOSITION_WIDTH_TWO_HPP
#define NOYA_TREE_DECOMPOSITION_WIDTH_TWO_HPP 1
/// @complexity Time: Expected O(V + E).
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
namespace noya {
struct width_two_tree_decomposition {
int width = 0;
std::vector<std::vector<int>> bags;
std::vector<std::pair<int, int>> tree_edges;
};
/// @brief Recognize treewidth at most two and construct a decomposition.
/// Repeatedly remove a live vertex of degree at most two; when it has two
/// neighbors, add the missing edge between them. This reduction is exact:
/// suppressing a degree-two vertex produces a minor, while a decomposition of
/// the filled graph extends by attaching the bag {vertex, first, second}.
/// Reversing the eliminations and attaching each new bag to a later bag that
/// contains its surviving neighbor set yields bags of size at most three.
inline std::optional<width_two_tree_decomposition>
tree_decomposition_width_two(
int vertex_count, const std::vector<std::pair<int, int>> &edges) {
assert(vertex_count >= 0);
std::vector<std::vector<int>> graph(vertex_count);
std::unordered_set<std::uint64_t> present;
present.reserve(2 * (edges.size() + std::size_t(vertex_count)) + 1);
auto edge_key = [](int first, int second) {
if (first > second) {
std::swap(first, second);
}
return (std::uint64_t(std::uint32_t(first)) << 32) |
std::uint32_t(second);
};
for (auto [first, second] : edges) {
assert(0 <= first && first < vertex_count);
assert(0 <= second && second < vertex_count);
assert(first != second);
bool inserted = present.insert(edge_key(first, second)).second;
assert(inserted);
if (!inserted) {
continue;
}
graph[first].push_back(second);
graph[second].push_back(first);
}
std::vector<int> degree(vertex_count);
std::vector<bool> alive(vertex_count, true);
std::vector<int> ready;
ready.reserve(vertex_count + 2 * edges.size());
for (int vertex = 0; vertex < vertex_count; vertex++) {
degree[vertex] = int(graph[vertex].size());
if (degree[vertex] <= 2) {
ready.push_back(vertex);
}
}
std::vector<std::vector<int>> later_neighbors(vertex_count);
std::vector<int> elimination_order;
elimination_order.reserve(vertex_count);
while (!ready.empty()) {
int vertex = ready.back();
ready.pop_back();
if (!alive[vertex] || degree[vertex] > 2) {
continue;
}
std::vector<int> neighbors;
for (int next : graph[vertex]) {
if (alive[next]) {
neighbors.push_back(next);
}
}
assert(int(neighbors.size()) == degree[vertex]);
later_neighbors[vertex] = neighbors;
elimination_order.push_back(vertex);
alive[vertex] = false;
for (int next : neighbors) {
degree[next]--;
if (degree[next] <= 2) {
ready.push_back(next);
}
}
if (neighbors.size() == 2) {
int first = neighbors[0];
int second = neighbors[1];
if (present.insert(edge_key(first, second)).second) {
graph[first].push_back(second);
graph[second].push_back(first);
degree[first]++;
degree[second]++;
}
}
}
if (int(elimination_order.size()) != vertex_count) {
return std::nullopt;
}
width_two_tree_decomposition result;
result.bags.resize(vertex_count);
std::vector<int> bag_containing_vertex(vertex_count, -1);
std::unordered_map<std::uint64_t, int> edge_bag;
edge_bag.reserve(2 * (edges.size() + std::size_t(vertex_count)) + 1);
int created = 0;
int previous_root = -1;
for (auto iterator = elimination_order.rbegin();
iterator != elimination_order.rend(); ++iterator) {
int vertex = *iterator;
int bag_id = created++;
std::vector<int> &bag = result.bags[bag_id];
bag.push_back(vertex);
bag.insert(bag.end(), later_neighbors[vertex].begin(),
later_neighbors[vertex].end());
result.width = std::max(result.width, int(bag.size()) - 1);
int parent = -1;
if (later_neighbors[vertex].size() == 1) {
parent = bag_containing_vertex[later_neighbors[vertex][0]];
} else if (later_neighbors[vertex].size() == 2) {
parent = edge_bag.at(
edge_key(later_neighbors[vertex][0], later_neighbors[vertex][1]));
} else if (previous_root != -1) {
parent = previous_root;
}
if (parent != -1) {
result.tree_edges.emplace_back(parent, bag_id);
}
if (later_neighbors[vertex].empty()) {
previous_root = bag_id;
}
for (int member : bag) {
bag_containing_vertex[member] = bag_id;
}
for (int first = 0; first < int(bag.size()); first++) {
for (int second = first + 1; second < int(bag.size()); second++) {
edge_bag[edge_key(bag[first], bag[second])] = bag_id;
}
}
}
return result;
}
} // namespace noya
#endif // NOYA_TREE_DECOMPOSITION_WIDTH_TWO_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// @complexity Time: Expected O(V + E).
/// Space: O(V + E).
namespace noya {
struct width_two_tree_decomposition {
int width = 0;
std::vector<std::vector<int>> bags;
std::vector<std::pair<int, int>> tree_edges;
};
/// @brief Recognize treewidth at most two and construct a decomposition.
/// Repeatedly remove a live vertex of degree at most two; when it has two
/// neighbors, add the missing edge between them. This reduction is exact:
/// suppressing a degree-two vertex produces a minor, while a decomposition of
/// the filled graph extends by attaching the bag {vertex, first, second}.
/// Reversing the eliminations and attaching each new bag to a later bag that
/// contains its surviving neighbor set yields bags of size at most three.
inline std::optional<width_two_tree_decomposition>
tree_decomposition_width_two(
int vertex_count, const std::vector<std::pair<int, int>> &edges) {
assert(vertex_count >= 0);
std::vector<std::vector<int>> graph(vertex_count);
std::unordered_set<std::uint64_t> present;
present.reserve(2 * (edges.size() + std::size_t(vertex_count)) + 1);
auto edge_key = [](int first, int second) {
if (first > second) {
std::swap(first, second);
}
return (std::uint64_t(std::uint32_t(first)) << 32) |
std::uint32_t(second);
};
for (auto [first, second] : edges) {
assert(0 <= first && first < vertex_count);
assert(0 <= second && second < vertex_count);
assert(first != second);
bool inserted = present.insert(edge_key(first, second)).second;
assert(inserted);
if (!inserted) {
continue;
}
graph[first].push_back(second);
graph[second].push_back(first);
}
std::vector<int> degree(vertex_count);
std::vector<bool> alive(vertex_count, true);
std::vector<int> ready;
ready.reserve(vertex_count + 2 * edges.size());
for (int vertex = 0; vertex < vertex_count; vertex++) {
degree[vertex] = int(graph[vertex].size());
if (degree[vertex] <= 2) {
ready.push_back(vertex);
}
}
std::vector<std::vector<int>> later_neighbors(vertex_count);
std::vector<int> elimination_order;
elimination_order.reserve(vertex_count);
while (!ready.empty()) {
int vertex = ready.back();
ready.pop_back();
if (!alive[vertex] || degree[vertex] > 2) {
continue;
}
std::vector<int> neighbors;
for (int next : graph[vertex]) {
if (alive[next]) {
neighbors.push_back(next);
}
}
assert(int(neighbors.size()) == degree[vertex]);
later_neighbors[vertex] = neighbors;
elimination_order.push_back(vertex);
alive[vertex] = false;
for (int next : neighbors) {
degree[next]--;
if (degree[next] <= 2) {
ready.push_back(next);
}
}
if (neighbors.size() == 2) {
int first = neighbors[0];
int second = neighbors[1];
if (present.insert(edge_key(first, second)).second) {
graph[first].push_back(second);
graph[second].push_back(first);
degree[first]++;
degree[second]++;
}
}
}
if (int(elimination_order.size()) != vertex_count) {
return std::nullopt;
}
width_two_tree_decomposition result;
result.bags.resize(vertex_count);
std::vector<int> bag_containing_vertex(vertex_count, -1);
std::unordered_map<std::uint64_t, int> edge_bag;
edge_bag.reserve(2 * (edges.size() + std::size_t(vertex_count)) + 1);
int created = 0;
int previous_root = -1;
for (auto iterator = elimination_order.rbegin();
iterator != elimination_order.rend(); ++iterator) {
int vertex = *iterator;
int bag_id = created++;
std::vector<int> &bag = result.bags[bag_id];
bag.push_back(vertex);
bag.insert(bag.end(), later_neighbors[vertex].begin(),
later_neighbors[vertex].end());
result.width = std::max(result.width, int(bag.size()) - 1);
int parent = -1;
if (later_neighbors[vertex].size() == 1) {
parent = bag_containing_vertex[later_neighbors[vertex][0]];
} else if (later_neighbors[vertex].size() == 2) {
parent = edge_bag.at(
edge_key(later_neighbors[vertex][0], later_neighbors[vertex][1]));
} else if (previous_root != -1) {
parent = previous_root;
}
if (parent != -1) {
result.tree_edges.emplace_back(parent, bag_id);
}
if (later_neighbors[vertex].empty()) {
previous_root = bag_id;
}
for (int member : bag) {
bag_containing_vertex[member] = bag_id;
}
for (int first = 0; first < int(bag.size()); first++) {
for (int second = first + 1; second < int(bag.size()); second++) {
edge_bag[edge_key(bag[first], bag[second])] = bag_id;
}
}
}
return result;
}
} // namespace noya