Search

A graph G is said to be a set graph if it admits an acyclic orientation that is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, a set graph is the underlying graph of the digraph representation of a hereditarily finite set. In this paper, we continue the study of set graphs and related topics, focusing on computational complexity aspects. We prove that set graph recognition is NP-complete, even when the input is restricted to bipartite graphs with exactly two leaves. The problem remains NP-complete if, in addition, we require that the extensional acyclic orientation be also slim, that is, that the digraph obtained by removing any arc from it is not extensional. Our approach in fact allows us to also show that the counting variants of the above problems are #P-complete, and prove similar complexity results for problems related to a generalization of extensional acyclic digraphs, the so-called hyper-extensional digraphs, which were proposed by Aczel to describe hypersets. Our proofs are based on reductions from variants of the Hamiltonian Path problem. We also consider a variant of the well-known notion of a separating code in a digraph, the so-called open-out-separating code, and show that it is NP-complete to determine whether an input extensional acyclic digraph contains an open-out-separating code of given size. [ABSTRACT FROM AUTHOR]

Abstract: An excessive factorization of a multigraph is a set of 1-factors of whose union is and, subject to this condition, is minimum. The integer is called the excessive index of and denoted by . We set if an excessive factorization does not exist. Analogously, let be a fixed positive integer. An excessive -factorization is a set of matchings of , all of size , whose union is and, subject to this condition, is minimum. The integer is denoted by and called the excessive -index of . Again, we set if an excessive -factorization does not exist. In this paper we shall prove that, for bipartite multigraphs, both the parameters and are computable in polynomial time, and we shall obtain an efficient algorithm for finding an excessive factorization and excessive -factorization, respectively, of any bipartite multigraph. [ABSTRACT FROM AUTHOR]

This paper gives a new and faster algorithm to find a 1-factor in a bipartite Δ-regular graph. The time complexity of this algorithm is O(nΔ + n log n log Δ), where n is the number of nodes. This implies an O(n log n log Δ + m log Δ) algorithm to edge-color a bipartite graph with n nodes, in edges, and maximum degree Δ. [ABSTRACT FROM AUTHOR]

We study a relaxation of the Vector Domination problem called Vector Connectivity ( VecCon ). Given a graph G with a requirement r ( v ) for each vertex v , VecCon asks for a minimum cardinality set S of vertices such that every vertex v ∈ V ∖ S is connected to S via r ( v ) disjoint paths. In the paper introducing the problem, Boros et al. [4] gave polynomial-time solutions for VecCon in trees, cographs, and split graphs, and showed that the problem can be approximated in polynomial time on n -vertex graphs to within a factor of log ⁡ n + 2 , leaving open the question of whether the problem is NP -hard on general graphs. We show that VecCon is APX -hard in general graphs, and NP -hard in planar bipartite graphs and in planar line graphs. We also generalize the polynomial result for trees by solving the problem for block graphs. [ABSTRACT FROM AUTHOR]

Abstract: The Minimum Duplication problem is a well-known problem in phylogenetics and comparative genomics. Given a set of gene trees, the Minimum Duplication problem asks for a species tree that induces the minimum number of gene duplications in the input gene trees. Recently, a variant of the Minimum Duplication problem, called Minimum Duplication Bipartite, has been introduced, where the goal is to find all pre-duplications, that is duplications that in the evolution precede the first speciation with respect to a species tree. In this paper, we investigate the complexity of both Minimum Duplication and Minimum Duplication Bipartite. First of all, we prove that the Minimum Duplication problem is -hard, even when the input consists of five uniquely leaf-labeled gene trees (improving upon known results on the complexity of the problem). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently with a randomized algorithm when the input gene trees have bounded depth. An extended abstract of this paper appeared in SOFSEM 2012 [1]. [Copyright &y& Elsevier]