Edge decompositions and rooted packings of graphs
In this paper, the problem of edge decomposition of graphs is considered from the viewpoint of computational complexity. For a fixed family of graphs \(\mathcal{H}\), given a graph \(G\), the graph decomposition problem DEC(\(\mathcal{H}\)) asks whether there is an edge decomposition of \(G\) into the members of \(\mathcal{H}\), which is called an \(\mathcal{H}\)-decomposition. When \(\mathcal{H}\) consists of just one graph \(H\), there is a dichotomous result stating that if every component of the graph \(H\) has one or two edges then the problem DEC(\(\{H\}\)) is polynomial-time solvable; otherwise, it is NP-complete. In this paper, the computational complexity of the problem DEC (\(\{2K_2,H\}\)) is studied. The authors give a partial solution to the problem by showing that for some large classes of graphs \(H\) this problem is polynomial-time solvable, while for some other large classes of graphs it is NP-complete. In the proofs, the so-called rooted packings into graphs which are mutual generalizations of both edge decompositions and factors of graphs are applied.
- Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
- Polynomial cases of graph decomposition: A complete solution of Holyer's problem
- Towards a solution of the Holyer's problem
- Graph factors and factorization: 1985--2003: a survey
- scientific article; zbMATH DE number 1156583
- Decomposition of multigraphs into isomorphic graphs with two edges
- scientific article; zbMATH DE number 398969
- On some multigraph decomposition problems and their computational complexity
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- An algorithm for finding factorizations of complete graphs
- 3K2-decomposition of a graph
- A note on the decomposition of graphs into isomorphic matchings
- Combinatorial and computational aspects of graph packing and graph decomposition
- Delta-system decompositions of graphs
- Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
- Edge decompositions into two kinds of graphs
- Efficient subgraphs packing
- Factors and factorizations of graphs. Proof techniques in factor theory
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- scientific article; zbMATH DE number 3974987 (Why is no real title available?)
- scientific article; zbMATH DE number 398969 (Why is no real title available?)
- scientific article; zbMATH DE number 1033810 (Why is no real title available?)
- NP-completeness of graph decomposition problems
- On rooted packings, decompositions, and factors of graphs
- On the Complexity of General Graph Factor Problems
- On the complexity of some edge-partition problems for graphs
- Packing subgraphs in a graph
- Packings by cliques and by finite families of graphs
- Packings by Complete Bipartite Graphs
- Polynomial cases of graph decomposition: A complete solution of Holyer's problem
- The NP-Completeness of Some Edge-Partition Problems
- Polynomial cases of graph decomposition: A complete solution of Holyer's problem
- Edge decompositions into two kinds of graphs
- A decomposition of 2-weak vertex-packing polytopes
- Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
- Orthogonal decomposition and packing of complete graphs
- On some multigraph decomposition problems and their computational complexity
- A matroid approach to finding edge connectivity and packing arborescences
- On the complexity of some edge-partition problems for graphs
- Combinatorial and computational aspects of graph packing and graph decomposition
- Edge connectivity, packing spanning trees, and eigenvalues of graphs
- On rooted packings, decompositions, and factors of graphs
- scientific article; zbMATH DE number 2190098 (Why is no real title available?)
This page was built for publication: Edge decompositions and rooted packings of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2675822)
