Struct VertexCoverFPT 

pub struct VertexCoverFPT {
    pub k: usize,
}

Vertex cover FPT algorithm combining LP-based kernelization and bounded search tree.

Fields

k: usize

The parameter k (size of desired vertex cover).

Implementations

impl VertexCoverFPT

pub fn new(k: usize) -> Self

Construct a VertexCoverFPT algorithm for budget k.

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

Apply LP-based 2k kernelization: remove vertices with LP value 1 (high degree), then return the remaining graph with reduced k.

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

Solve vertex cover: apply LP kernel then bounded search tree. Returns Some(cover) if a size-k cover exists, None otherwise.

pub fn running_time(&self) -> String

Returns the running time bound for the FPT algorithm.

Trait Implementations

impl Clone for VertexCoverFPT

fn clone(&self) -> VertexCoverFPT

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for VertexCoverFPT

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

Formats the value using the given formatter.