Degree constrained 2-partitions of semicomplete digraphs.

*(English)*Zbl 1401.05129Summary: A 2-partition of a digraph \(D\) is a partition \((V_1, V_2)\) of \(V(D)\) into two disjoint non-empty sets \(V_1\) and \(V_2\) such that \(V_1 \cup V_2 = V(D)\). A semicomplete digraph is a digraph with no pair of non-adjacent vertices. We consider the complexity of deciding whether a given semicomplete digraph has a 2-partition such that each part of the partition induces a (semicomplete) digraph with some specified property. J. Bang-Jensen and F. Havet [Theor. Comput. Sci. 636, 85–94 (2016; Zbl 1342.68150)] and J. Bang-Jensen et al. [ibid. 640, 1–19 (2016; Zbl 1345.68168)] determined the complexity of 120 such 2-partition problems for general digraphs. Several of these problems are NP-complete for general digraphs and thus it is natural to ask whether this is still the case for well-structured classes of digraphs, such as semicomplete digraphs. This is the main topic of the paper. More specifically, we consider 2-partition problems where the set of properties are minimum out-, minimum in- or minimum semi-degree. Among other results we prove the following:

i) For all integers \(k_1, k_2 \geq 1\) and \(k_1 + k_2 \geq 3\) it is NP-complete to decide whether a given digraph \(D\) has a 2-partition \((V_1, V_2)\) such that \(D \langle V_i \rangle\) has out-degree at least \(k_i\) for \(i = 1, 2\).

ii) For every fixed choice of integers \(\alpha, k_1, k_2 \geq 1\) there exists a polynomial algorithm for deciding whether a given digraph of independence number at most \(\alpha\) has a 2-partition \((V_1, V_2)\) such that \(D \langle V_i \rangle\) has out-degree at least \(k_i\) for \(i = 1, 2\).

iii) For every fixed integer \(k \geq 1\) there exists a polynomial algorithm for deciding whether a given semicomplete digraph has a 2-partition \((V_1, V_2)\) such that \(D \langle V_1 \rangle\) has out-degree at least one and \(D \langle V_2 \rangle\) has in-degree at least \(k\).

iv) It is NP-complete to decide whether a given semicomplete digraph \(D\) has a 2-partition \((V_1, V_2)\) such that \(D \langle V_i \rangle\) is a strong tournament.

i) For all integers \(k_1, k_2 \geq 1\) and \(k_1 + k_2 \geq 3\) it is NP-complete to decide whether a given digraph \(D\) has a 2-partition \((V_1, V_2)\) such that \(D \langle V_i \rangle\) has out-degree at least \(k_i\) for \(i = 1, 2\).

ii) For every fixed choice of integers \(\alpha, k_1, k_2 \geq 1\) there exists a polynomial algorithm for deciding whether a given digraph of independence number at most \(\alpha\) has a 2-partition \((V_1, V_2)\) such that \(D \langle V_i \rangle\) has out-degree at least \(k_i\) for \(i = 1, 2\).

iii) For every fixed integer \(k \geq 1\) there exists a polynomial algorithm for deciding whether a given semicomplete digraph has a 2-partition \((V_1, V_2)\) such that \(D \langle V_1 \rangle\) has out-degree at least one and \(D \langle V_2 \rangle\) has in-degree at least \(k\).

iv) It is NP-complete to decide whether a given semicomplete digraph \(D\) has a 2-partition \((V_1, V_2)\) such that \(D \langle V_i \rangle\) is a strong tournament.

##### MSC:

05C20 | Directed graphs (digraphs), tournaments |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

68Q25 | Analysis of algorithms and problem complexity |

##### Keywords:

semicomplete digraph; tournament; 2-partition; minimum semi-degree; minimum out-degree; minimum in-degree; NP-complete; digraphs of bounded independence number
PDF
BibTeX
XML
Cite

\textit{J. Bang-Jensen} and \textit{T. M. Christiansen}, Theor. Comput. Sci. 746, 112--123 (2018; Zbl 1401.05129)

Full Text:
DOI

##### References:

[1] | Alon, N., Disjoint directed cycles, J. Combin. Theory Ser. B, 68, 167-178, (1996) · Zbl 0861.05037 |

[2] | N. Alon, J. Bang-Jensen, S. Bessy, Out-colourings of digraphs, submitted for publication, 2017. |

[3] | Bang-Jensen, J.; Gutin, G., Digraphs: theory, algorithms and applications, (2009), Springer Verlag London · Zbl 1170.05002 |

[4] | Bang-Jensen, J.; Havet, F., Finding good 2-partitions of digraphs I. hereditary properties, Theoret. Comput. Sci., 636, 85-94, (2016) · Zbl 1342.68150 |

[5] | Bang-Jensen, J.; Cohen, N.; Havet, F., Finding good 2-partitions of digraphs II. enumerable properties, Theoret. Comput. Sci., 640, 1-19, (2016) · Zbl 1345.68168 |

[6] | Bang-Jensen, J.; Nielsen, M. H., Finding complementary cycles in locally semicomplete digraphs, Discrete Appl. Math., 146, 245-256, (2005) · Zbl 1055.05086 |

[7] | Guo, Y.; Volkmann, L., On complementary cycles in locally semicomplete digraphs, Discrete Math., 135, 121-127, (1994) · Zbl 0816.05036 |

[8] | Kühn, D.; Osthus, D.; Townsend, T., Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle length, Combinatorica, 36, 451-469, (2016) · Zbl 1389.05058 |

[9] | Li, H.; Shu, J., The partition of a strong tournament, Discrete Math., 290, 211-220, (2005) · Zbl 1069.05037 |

[10] | Lichiardopol, N., Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semi-degree: proof for tournaments of a conjecture of stiebitz, Int. J. Comb., 1-9, (2012) · Zbl 1236.05095 |

[11] | McCuaig, W., Intercyclic digraphs, (Graph Structure Theory, Seattle, WA, 1991, Contemp. Math., vol. 147, (1993), American Mathematical Society), 203-245 · Zbl 0789.05042 |

[12] | Moon, J. W., Topics on tournaments, (1968), Holt, Rinehart and Winston New York · Zbl 0191.22701 |

[13] | Reid, K. B., Two complementary circuits in two-connected tournaments, (Cycles in Graphs, North-Holland Mathematical Studies, vol. 115, (1985), North-Holland Amsterdam), 321-334 · Zbl 0573.05031 |

[14] | Stiebitz, M., Decomposition of graphs and digraphs, (KAM Series in Discrete Mathematics-Combinatorics-Operations Research-Optimization, vol. 95-309, (1995)), 56-59 |

[15] | Thomassen, C., Disjoint cycles in digraphs, Combinatorica, 3, 393-396, (1983) · Zbl 0527.05036 |

[16] | Schaefer, T. J., The complexity of satisfiability problems, (Proceedings of the 10th Annual ACM Symposium on Theory of Computing, (1978), ACM New York), 216-226 · Zbl 1282.68143 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.