zbMATH — the first resource for mathematics

Finding good 2-partitions of digraphs. I. Hereditary properties. (English) Zbl 1342.68150
Summary: We study the complexity of deciding whether a given digraph \(D\) has a vertex-partition into two disjoint subdigraphs with given structural properties. Let \(\mathcal{H}\) and \(\mathcal{E}\) denote the following two sets of natural properties of digraphs: \(\mathcal{H} = \{\text{acyclic}\), complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, \(\text{tournament}\}\) and \(\mathcal{E} = \{\text{strongly connected}\), connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, \(\text{having an in-branching}\}\). In this paper, we determine the complexity of deciding, for any fixed pair of positive integers \(k_1\), \(k_2\), whether a given digraph has a vertex partition into two digraphs \(D_1\), \(D_2\) such that \(|V(D_i)| \geq k_i\) and \(D_i\) has property \(\mathbb{P}_i\) for \(i = 1, 2\) when \(\mathbb{P}_1 \in \mathcal{H}\) and \(\mathbb{P}_2 \in \mathcal{H} \cup \mathcal{E}\). We also classify the complexity of the same problems when restricted to strongly connected digraphs.
The complexity of the 2-partition problems where both \(\mathbb{P}_1\) and \(\mathbb{P}_2\) are in \(\mathcal{E}\) is determined in Part II [the authors et al., Theor. Comput. Sci. 640, 1–19 (2016; Zbl 1345.68168)].

68Q25 Analysis of algorithms and problem complexity
05C20 Directed graphs (digraphs), tournaments
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI
[1] Alon, N., Splitting digraphs, Combin. Probab. Comput., 15, 933-937, (2006) · Zbl 1116.05033
[2] Bang-Jensen, J.; Cohen, N.; Havet, F., Finding good 2-partitions of digraphs II. enumerable properties, Theoret. Comput. Sci., (2016), to appear · Zbl 1345.68168
[3] Bang-Jensen, J.; Gutin, G., Digraphs: theory, algorithms and applications, (2009), Springer-Verlag London · Zbl 1170.05002
[4] Bensmail, J., On the complexity of partitioning a graph into a few connected subgraphs, J. Comb. Optim., 30, 174-187, (2015) · Zbl 1325.90075
[5] Bokal, D.; Fijavz, G.; Juvan, M.; Kayl, P. M.; Mohar, B., The circular chromatic number of a digraph, J. Graph Theory, 46, 227-240, (2004) · Zbl 1041.05026
[6] Chen, X.; Hu, X.; Zang, W., A MIN-MAX theorem on tournaments, SIAM J. Comput., 37, 3, 923-937, (2007) · Zbl 1191.90028
[7] Dyer, M. E.; Frieze, A. M., On the complexity of partitioning graphs into connected subgraphs, Discrete Appl. Math., 10, 139-153, (1985) · Zbl 0562.68030
[8] Földes, S.; Hammer, P., Split graphs, Congr. Numer., 19, 311-315, (1977)
[9] Grigoriev, A.; Sitters, R., Connected feedback vertex set in planar graphs, (Graph Theoretical Concepts in Computer Science, 35th International Workshop, WG2009, Lecture Notes in Comput. Sci., vol. 5911, (2009), Springer-Verlag Berlin), 143-153 · Zbl 1273.68409
[10] Hajnal, P., Partition of graphs with condition on the connectivity and minimum degree, Combinatorica, 3, 95-99, (1983) · Zbl 0529.05030
[11] Kühn, D.; Osthus, D., Partitions of graphs with high minimum degree or connectivity, J. Combin. Theory Ser. B, 88, 29-43, (2003) · Zbl 1045.05075
[12] Kühn, D.; Osthus, D.; Townsend, T., Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle length, Combinatorica, (2016), in press · Zbl 1389.05058
[13] Le, H.-O.; Le, V. B.; Müller, H., Splitting a graph into disjoint induced paths or cycles, Discrete Appl. Math., 131, 199-212, (2003) · Zbl 1073.68031
[14] Lichiardopol, N., Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of stiebitz, Int. J. Comb., (2012), 9 pages · Zbl 1236.05095
[15] Liu, M. H.; Xu, B. G., Bipartition of graph under degree constraints, Sci. China Math., 58, 869-874, (2015) · Zbl 1317.05152
[16] Misra, N.; Philip, G.; Raman, V.; Saurabh, S.; Sikdar, S., FPT algorithms for connected feedback vertex set, J. Comb. Optim., 24, 131-146, (2012) · Zbl 1258.05060
[17] Neumann-Lara, V., The dichromatic number of a digraph, J. Combin. Theory Ser. B, 33, 265-270, (1982) · Zbl 0506.05031
[18] Reid, K. B., Two complementary circuits in two-connected tournaments, (Cycles in Graphs, Burnaby, B.C., 1982, North-Holland Math. Stud., vol. 115, (1985), North-Holland), 321-334
[19] Schaefer, T. J., The complexity of satisfiability problems, (Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC 10), (1978), ACM New York), 216-226 · Zbl 1282.68143
[20] Stiebitz, M., Decomposition of graphs and digraphs, (KAM Series in Discrete Mathematics-Combinatorics-Operations Research-Optimization 95-309, (1995), Charles University Prague)
[21] Suzuki, H.; Takahashi, N.; Nishizeki, T., A linear algorithm for bipartion of biconnected graphs, Inform. Process. Lett., 33, 227-231, (1990) · Zbl 0696.68074
[22] Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory, 7, 165-167, (1983) · Zbl 0515.05045
[23] van’t Hof, P.; Paulusma, D.; Woeginger, G. J., Partitioning graphs into connected parts, Theoret. Comput. Sci., 410, 4834-4843, (2009) · Zbl 1194.68179
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.