Finding good 2-partitions of digraphs II. Enumerable properties

详细信息    查看全文

• 作者：J. Bang-Jensen^a ; ¹ ; ^{jbj@imada.sdu.dk" class="auth_mail" title="E-mail the corresponding author} ; Nathann Cohen^b ; ^{nathann.cohen@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Fré ; dé ; ric Havet^c ; ² ; ^{frederic.havet@inria.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Oriented ; NP-complete ; Polynomial ; Partition ; Splitting digraphs ; Acyclic ; Semicomplete digraph ; Tournament ; Out-branching ; Feedback vertex set ; 2-Partition ; Minimum degree
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：9 August 2016
• 年：2016
• 卷：640
• 期：Complete
• 页码：1-19
• 全文大小：644 K

文摘

We continue the study, initiated in [3], 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 7148b" title="Click to view the MathML source">E$\mathcal{E}$ be the following set of properties of digraphs: E=$\mathbb{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 P₁,P₂${\mathbb{P}}_1,{\mathbb{P}}_2$ from 7148b" title="Click to view the MathML source">E$\mathcal{E}$ and all pairs of fixed positive integers k₁,k₂$k_1,k_2$, the complexity of deciding whether a digraph has a vertex partition into two digraphs D₁,D₂$D_1,D_2$ such that 7143" title="Click to view the MathML source">D_i$D_i$ has property P_i${\mathbb{P}}_i$ and |V(D_i)|≥k_i$|V(D_i)|\ge k_i$, i=1,2$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 P₁∈H${\mathbb{P}}_1\in \mathcal{H}$ and P₂∈H∪E${\mathbb{P}}_2\in \mathcal{H}\cup \mathcal{E}$, where 330762d8c5d0" title="Click to view the MathML source">H=$\mathbb{H}=${acyclic, complete, arc-less, oriented (no 2-cycle), semicomplete, symmetric, tournament} were completely characterized in [3].