# 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)].

##### MSC:
 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:
##### References:
  Alon, N., Splitting digraphs, Combin. Probab. Comput., 15, 933-937, (2006) · Zbl 1116.05033  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  Bang-Jensen, J.; Gutin, G., Digraphs: theory, algorithms and applications, (2009), Springer-Verlag London · Zbl 1170.05002  Bensmail, J., On the complexity of partitioning a graph into a few connected subgraphs, J. Comb. Optim., 30, 174-187, (2015) · Zbl 1325.90075  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  Chen, X.; Hu, X.; Zang, W., A MIN-MAX theorem on tournaments, SIAM J. Comput., 37, 3, 923-937, (2007) · Zbl 1191.90028  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  Földes, S.; Hammer, P., Split graphs, Congr. Numer., 19, 311-315, (1977)  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  Hajnal, P., Partition of graphs with condition on the connectivity and minimum degree, Combinatorica, 3, 95-99, (1983) · Zbl 0529.05030  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  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  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  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  Liu, M. H.; Xu, B. G., Bipartition of graph under degree constraints, Sci. China Math., 58, 869-874, (2015) · Zbl 1317.05152  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  Neumann-Lara, V., The dichromatic number of a digraph, J. Combin. Theory Ser. B, 33, 265-270, (1982) · Zbl 0506.05031  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  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  Stiebitz, M., Decomposition of graphs and digraphs, (KAM Series in Discrete Mathematics-Combinatorics-Operations Research-Optimization 95-309, (1995), Charles University Prague)  Suzuki, H.; Takahashi, N.; Nishizeki, T., A linear algorithm for bipartion of biconnected graphs, Inform. Process. Lett., 33, 227-231, (1990) · Zbl 0696.68074  Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory, 7, 165-167, (1983) · Zbl 0515.05045  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.