zbMATH — the first resource for mathematics

Finding good 2-partitions of digraphs. II. Enumerable properties. (English) Zbl 1345.68168
Summary: We continue the study, initiated in Part I [the first and the last author, ibid. 636, 85–94 (2016; Zbl 1342.68150)], of the complexity of deciding whether a given digraph \(D\) has a vertex-partition into two disjoint subdigraphs with given structural properties and given minimum cardinality. Let \(\mathcal{E}\) be the following set of properties of digraphs: \(\mathcal{E} =\{\)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, having an in-branching\(\}\). In this paper we determine, for all choices of \(\mathbb{P}_1\), \(\mathbb{P}_2\) from \(\mathcal{E}\) and all pairs of fixed positive integers \(k_1\), \(k_2\), the complexity of deciding whether a digraph has a vertex partition into two digraphs \(D_1\), \(D_2\) such that \(D_i\) has property \(\mathbb{P}_i\) and \(| V(D_i) | \geq k_i\), \(i = 1, 2\). We also classify the complexity of the same problems when restricted to strongly connected digraphs. The complexity of the analogous problems when \(\mathbb{P}_1 \in \mathcal{H}\) and \(\mathbb{P}_2 \in \mathcal{H} \cup \mathcal{E}\), where \(\mathcal{H} =\{\text{acyclic, complete, arc-less, oriented (no 2-cycle), semicomplete, symmetric, tournament}\}\) were completely characterized in [loc. cit.].

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.; Gutin, G., Digraphs: theory, algorithms and applications, (2009), Springer-Verlag London · Zbl 1170.05002
[3] Bang-Jensen, J.; Havet, F., Finding good 2-partitions of digraphs I. hereditary properties, Theoret. Comput. Sci., 636, 85-94, (2016) · Zbl 1342.68150
[4] Bang-Jensen, J.; Havet, F.; Maia de Oliveira, A. K., Finding a subdivision of a digraph, Theoret. Comput. Sci., 562, 20, (2015) · Zbl 1303.68064
[5] Bang-Jensen, J.; Kriesell, M., On the problem of finding disjoint cycles and dicycles in a digraph, Combinatorica, 31, 639-668, (2011) · Zbl 1261.05047
[6] Bang-Jensen, J.; Kriesell, M.; Maddaloni, A.; Simonsen, S., Vertex-disjoint directed and undirected cycles in general digraphs, J. Combin. Theory Ser. B, 106, 1-14, (2014) · Zbl 1297.05095
[7] Bang-Jensen, J.; Yeo, A., Arc-disjoint spanning sub(di)graphs in digraphs, Theoret. Comput. Sci., 438, 48-54, (2012) · Zbl 1247.68096
[8] Bensmail, J., On the complexity of partitioning a graph into a few connected subgraphs, J. Comb. Optim., 30, 174-187, (2015) · Zbl 1325.90075
[9] 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
[10] Cowen, L.; Goddard, W.; Jesurum, C. E., Defective coloring revisited, J. Graph Theory, 24, 3, 205-219, (1997) · Zbl 0877.05019
[11] 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
[12] Földes, S.; Hammer, P., Split graphs, Congr. Numer., 19, 311-315, (1977)
[13] Goncalves, D.; Havet, F.; Pinlou, A.; Thomassé, S., On spanning galaxies in digraphs, Discrete Appl. Math., 160, 744-754, (2012) · Zbl 1241.05043
[14] Grigoriev, A.; Sitters, R., Connected feedback vertex set in planar graphs, (Graph Theoretical Concepts in Computer Science, 35th International Workshop, WG2009, Lecture Notes in Comp. Science, vol. 5911, (2009), Springer Verlag Berlin), 143-153 · Zbl 1273.68409
[15] Hajnal, P., Partition of graphs with condition on the connectivity and minimum degree, Combinatorica, 3, 95-99, (1983) · Zbl 0529.05030
[16] Kawarabayashi, K.; Kreutzer, S., The directed grid theorem, CoRR, (2014), abs/1411.5681
[17] 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
[18] 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
[19] 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
[20] Lichiardopol, N., Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of stiebitz, Int. J. Comb., 9, (2012) · Zbl 1236.05095
[21] Liu, M. H.; Xu, B. G., Bipartition of graph under degree constraints, Sci. China Math., 58, 869-874, (2015) · Zbl 1317.05152
[22] McCuaig, W., Intercyclic digraphs, (Graph Structure Theory, Seattle, WA, 1991, Contemp. Math., vol. 147, (1993), American Mathematical Society), 203-245 · Zbl 0789.05042
[23] 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
[24] 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
[25] Schaefer, T. J., The complexity of satisfiability problems, (Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC 10, New York, (1978), ACM), 216-226 · Zbl 1282.68143
[26] Stiebitz, M., Decomposition of graphs and digraphs, (KAM Series in Discrete Mathematics-Combinatorics-Operations Research-Optimization 95-309, (1995), Charles University Prague)
[27] Suzuki, H.; Takahashi, N.; Nishizeki, T., A linear algorithm for bipartion of biconnected graphs, Inform. Process. Lett., 33, 227-231, (1990) · Zbl 0696.68074
[28] Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory, 7, 165-167, (1983) · Zbl 0515.05045
[29] Thomassen, C., Even cycles in directed graphs, European J. Combin., 6, 1, 85-89, (1985) · Zbl 0606.05039
[30] 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.