Struct CrownDecomposition 

pub struct CrownDecomposition {
    pub crown: Vec<usize>,
    pub head: Vec<usize>,
    pub reduced_adj: Vec<Vec<usize>>,
}

Crown decomposition for vertex cover kernelization. Returns (crown vertices, head vertices, reduced graph adjacency).

Fields

crown: Vec<usize>

The crown C: an independent set with a perfect matching into H.

head: Vec<usize>

The head H: neighbors of C that are matched to C.

reduced_adj: Vec<Vec<usize>>

Reduced graph adjacency (V - H - C).

Implementations

impl CrownDecomposition

pub fn compute(adj: &[Vec<usize>], _k: usize) -> Self

Compute a crown decomposition for vertex cover on the given graph. Uses LP-based half-integrality: vertices with LP value 0 are in crown, vertices with LP value 1 are in head.

pub fn head_size(&self) -> usize

Returns the number of vertices in the head (= reduction in budget k).

pub fn verify(&self, adj: &[Vec<usize>]) -> bool

Verify: the crown is an independent set and every crown vertex has a neighbor in head.

Trait Implementations

impl Clone for CrownDecomposition

fn clone(&self) -> CrownDecomposition

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for CrownDecomposition

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.