General Factors in Graphs.
Abstract
Consider a graph G=(N,E) and, for each node i is a member of N, let B sub I be a subset of (0,1,...,d sub G(i)) where d sub G(i) denotes the degree of node i in G. The general factor problem asks whether there exists a subgraph of G, say H=(N,F) where F is a subset of E, such that d sub H(i) is a member of B sub i for every i belonging to N. This problem is NP-complete. A set B sub i is said to have a gap of length P > or = 1 if there exists an integer k is a member of B sub i such that k+1,...,k+p is not a member of B sub i and k+p+1 is a member of B sub i. Lovasz conjectured that the general factor problem can be solved in polynomial time when, in each B sub i, all the gaps (if any) have length one. We prove this conjecture. In cubic graphs, the result is obtained via a reduction to the edge-and-triangle partitioning problem. In general graphs, the proof uses an augmenting path theorem and an Edmonds-type algorithm.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1986
- Accession Number
- ADA173058
Entities
People
- Gérard Cornuéjols
Organizations
- Carnegie Mellon University