corollaryroutine

Subexponential counting for graph problems

Corollary·cor:graph-counting·§1 Introduction

Statement (paper)

On simple graphs with vv vertices and ee edges, the number of independent sets and, for each fixed q⩾2q\ge2, the number of proper qq-colorings can be computed deterministically in 2o(v)2^{o(v)} time and poly⁡q(v,e)\poly_q(v,e) space. The number of perfect matchings can be computed deterministically in 2o(v+e)2^{o(v+e)} time and poly⁡(v,e)\poly(v,e) space.

In plain English

Independent sets and, for each fixed q⩾2q\ge2, proper qq-colorings of a graph with vv vertices and ee edges can be counted deterministically in 2o(v)2^{o(v)} time and poly⁡q(v,e)\poly_q(v,e) space. Perfect matchings can be counted deterministically in 2o(v+e)2^{o(v+e)} time and poly⁡(v,e)\poly(v,e) space.

Why it's here

This corollary applies the main theorem's subexponential kk-CNF counting algorithm to standard graph counting problems. Each problem is encoded as a low-width CNF counting instance whose variable count is O(v)O(v) (or O(v+e)O(v+e) for matchings), so the 2o(n)2^{o(n)} bound turns into the stated subexponential bounds.
Classified routine:
Direct consequence of the paper's main k-CNF counting theorem (thm-main) via standard CNF encodings of independent sets, q-colorings (one-hot encoding with O(qv) variables) and perfect matchings (edge variables with at-most/at-least-one constraints, using auxiliary variables to keep clause width bounded).

Uses

thmSubexponential deterministic k-CNF model counting

Used by

Nothing in the paper

Sources

PaperOpen
Section
§1 Introduction
Page
—
Label
cor:graph-counting
Line
main_full_version.tex:151
Leannot aligned

Phase 2 aligns this node to a Lean declaration.