Compatible 2-factors
type: Item
instance of: scholarly article
title: Compatible 2-factors
zbMATH Open document ID: 0778.05064
DOI: 10.1016/0166-218X(92)90257-B
author: Jan Kratochvíl
author: Svatopluk Poljak
published in: Discrete Applied Mathematics
publication date: 1992-09-27T00:00:00Z
review text: A 2-factor of a graph \(G\) is a spanning subgraph \(F\) of \(G\) in which each vertex has degree 2. The pair of edges of \(F\) incident with a vertex \(v\) is called a transition of \(F\) at \(v\). Suppose at each vertex \(v\) of \(G\) we are given a set \(T(v)\) of allowed transitions (pairs of edges incident with \(v)\); a compatible 2-factor is one in which the transition at each \(v\) is from the corresponding set \(T(v)\). The authors study the question of deciding, for a given graph \(G\) with a transition system \(T\), whether or not there is a compatible 2-factor. Each set \(T(v)\) can be viewed as a graph whose vertices are the edges incident on \(v\). The authors give a polynomial algorithm to decide the existence of compatible 2-factors in two special situations: (1) when each \(T(v)\) is a complete multipartite graph (with possibly some isolated vertices); and (2) when each \(T(v)\) is a subgraph of a four-cycle (again with possibly some isolated vertices). Case (1) is solved essentially by reduction to matching, and case (2) by reduction to 2-satisfiability. The authors also show that in all other situations the problems are NP-complete.
reviewed by: Pavol Hell
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 65069
zbMATH Keywords: 2-factor
zbMATH Keywords: spanning subgraph
zbMATH Keywords: transition
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: matching
zbMATH Keywords: NP-complete
MaRDI profile type: Publication
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Q3831045
cites work: Q4198056
cites work: On Restricted Two-Factors
cites work: Q3360899
cites work: Q3802605
cites work: Matching theory
cites work: Color-reversal by local complementation
cites work: The Factors of Graphs
description: scientific article; zbMATH DE number 65069