1
$\begingroup$

Petersen's theorem states that every cubic, bridgeless graph contains a perfect matching. It implies that the edge set $E$ can be partitioned into a perfect matching and a 2-factor.

Determining the existence of a decomposition of bridgeless cubic graph $G(V,E)$ into a perfect matching and a connected 2-factor is NP-complete (Since Hamiltonian cycle problem is NP-complete). A generalization is the decomposition of bridgeless cubic graph into a perfect matching and a 2-factor with given cycle type. A cycle type of a 2-factor $\zeta= (a_3,a_4,..., a_i, ..., a_n)$ where $a_i$ is the number of cycles of length $i$. (For Hamiltonian cycle problem $\zeta=(0,0,0, ...,1)$) Formally,

Input: Given a bridgeless cubic graph $G$ and a cycle type $\zeta$

Question: Is $G$ decomposable into 2-factor with cycle type $\zeta$

For which cycle types is this problem polynomial-time solvable? Is there a known dichotomy for efficiently solvable cases vs NP-complete cases?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.