Search

Given a connected graph G = (V , E) , with n ≔ | V | vertices and m ≔ | E | edges, a cut can be represented as a bipartition { S , S ¯ } of the vertices or as the set of those edges in E having one endpoint in S and the other in S ¯ , denoted by δ G (S , S ¯). A cut is minimal, or also called bond , if and only if the two induced subgraphs obtained by removing the edges in the cut are both connected. When the bond separates two given vertices s and t , we talk about s , t - bond. In this work, we consider the problems of listing all the bonds and listing all the s , t -bonds in a graph. These fundamental problems find application in many research areas, such as, beyond graph theory, network reliability, bioinformatics, and chemistry. The state-of-the-art algorithm exploits binary partition to output each s , t -bond in O (m) per bond, being thus classified as an O (m) -delay algorithm. Here we present two new algorithms to address these problems. The first one implements a slightly different branching strategy than the state of the art, though achieving the same complexity. Anyway, we can improve it by relying on dynamic data structures and amortized analysis, obtaining an algorithm that outputs a new bond in O ˜ (n). By assuming only the two bond-shores are output for every bond, this is the first output-linear algorithm listing bonds. In case we commit to explicitly providing the entire edge-set of every bond, the delay becomes O ˜ (n) + | δ G (S , S ¯) |. • We study the problem of listing all minimal cuts (or bonds) in a graph. • We exploit a different branching strategy than Tsukiyama et al. (1980). • We provide a first algorithm having the same complexity as Tsukiyama et al. (1980). • We rely on dynamic data structures and amortized analysis to improve our approach. • We propose the first O ˜ (n) -delay algorithm to list all bonds in a graph. [ABSTRACT FROM AUTHOR]

Let B be a positive integer and let G be a simple graph. An excessive [ B]-factorization of G is a minimum set of matchings, each of size B, whose union is [ABSTRACT FROM AUTHOR]

Coalitions of weighted voting games can be restricted to be connected components of a graph. As a consequence, coalition formation, and therefore a player’s power, depends on the topology of the graph. We analyze the problems of computing the Banzhaf and the Shapley–Shubik power indexes for this class of voting games and prove that calculating them is #P-complete in the strong sense for general graphs. For trees, we provide pseudo-polynomial time algorithms and prove #P-completeness in the weak sense for both indexes. [ABSTRACT FROM AUTHOR]

The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Due to the high rate of noise in the biological data, more flexible definitions of the problem have been outlined. We present in this paper two inapproximability results for two different optimization variants of Graph Motif: one where the size of the solution is maximized, the other when the number of substitutions of colors to obtain the motif from the solution is minimized. We also study a decision version of Graph Motif where the connectivity constraint is replaced by the well known notion of graph modularity. While the problem remains N P-complete, it allows algorithms in F P T for biologically relevant parameterizations. [ABSTRACT FROM AUTHOR]

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]

We show that the following fundamental edge-colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge-colouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes. [ABSTRACT FROM AUTHOR]

Abstract: In the context of non-coding RNA (ncRNA) multiple structural alignment, Davydov and Batzoglou (2006) introduced in the problem of finding the largest nested linear graph that occurs in a set of linear graphs, the so-called Max-NLS problem. This problem generalizes both the longest common subsequence problem and the maximum common homeomorphic subtree problem for rooted ordered trees. In the present paper, we give a fast algorithm for finding the largest nested linear subgraph of a linear graph and a polynomial-time algorithm for a fixed number (k) of linear graphs. Also, we strongly strengthen the result of Davydov and Batzoglou (2006) by proving that the problem is NP-complete even if is composed of nested linear graphs of height at most 2, thereby precisely defining the borderline between tractable and intractable instances of the problem. Of particular importance, we improve the result of Davydov and Batzoglou (2006) by showing that the Max-NLS problem is approximable within ratio in running time, where is the size of an optimal solution. We also present -approximation of Max-NLS problem running in time for restricted linear graphs. In particular, for ncRNA derived linear graphs, a -approximation is presented. [Copyright &y& Elsevier]

Abstract: In the context of comparative analysis of protein–protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex (pattern graph) in the protein–protein interaction graph (target graph) of another species with respect to (w.r.t.) orthologous proteins. We give an efficient exponential-time randomized algorithm in case the occurrence of the pattern graph in the target graph is required to be exact. For approximate occurrences, we prove a tight inapproximability result and give four approximation algorithms that deal with bounded degree graphs, small ortholog numbers, linear forests and very simple yet hard instances, respectively. [Copyright &y& Elsevier]

Abstract: We consider graphs which contain both directed and undirected edges (partially directed graphs). We show that the problem of covering the edges of such graphs with a minimum number of edge-disjoint directed paths respecting the orientations of the directed edges is polynomially solvable. We exhibit a good characterization for this problem in the form of a min–max theorem. We introduce a more general problem including weights on possible orientations of the undirected edges. We show that this more general weighted formulation is equivalent to the weighted bipartite b-factor problem. This implies the existence of a strongly polynomial algorithm for this weighted generalization of Euler''s problem to partially directed graphs (compare this with the negative results for the mixed Chinese postman problem). We also provide a compact linear programming formulation for the weighted generalization that we propose. [Copyright &y& Elsevier]

Abstract: Given a digraph and an , denotes the digraph obtained from D by reversing those arcs with exactly one end in X. A digraph D is called acyclically pushable when there exists an such that is acyclic. Huang, MacGillivray and Yeo have recently characterized, in terms of two excluded induced subgraphs on 7 and 8 nodes, those bipartite permutation digraphs which are acyclically pushable. We give an algorithmic proof of their result. Our proof delivers an time algorithm to decide whether a bipartite permutation digraph is acyclically pushable and, if yes, to find a set X such that is acyclic. (Huang, MacGillivray and Yeo''s result clearly implies an time algorithm to decide but the polynomiality of constructing X was still open.) We define a strongly acyclic digraph as a digraph D such that is acyclic for every X. We show how a result of Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1–3) (1999) 27–33] can be essentially regarded as a characterization of strongly acyclic digraphs and also provides linear time algorithms to find a strongly acyclic orientation of an undirected graph, if one exists. Besides revealing this connection, we add simplicity to the structural and algorithmic results first given in Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1–3) (1999) 27–33]. In particular, we avoid decomposing the graph into triconnected components. We give an alternate proof of a theorem of Huang, MacGillivray and Wood characterizing acyclically pushable bipartite tournaments. Our proof leads to a linear time algorithm which, given a bipartite tournament as input, either returns a set X such that is acyclic or a proof that D is not acyclically pushable. [Copyright &y& Elsevier]

We give a simple algorithm for finding a minimum T-cut. At present, all known efficient algorithms for this problem go through the computation of a Gomory–Hu tree. While our algorithm bases on the same fundamental properties of uncrossing as the previous methods, still it provides an ad hoc solution. This solution is easier to implement and faster to run. Our results extend to the whole of symmetric submodular functions. [Copyright &y& Elsevier]

Let G be an undirected graph. The Chinese postman problem (CPP) asks for a shortest postman tour in G, i.e., a closed walk using each edge at least once. The shortest cycle cover problem (SCC) asks for a family C of circuits of G such that each edge is in some circuit of C and the total length of all circuits in C is as small as possible. Clearly, an optimal solution of CPP cannot be greater than a solution of SCC. A graph G has the CPP = SCC property when the solutions to the two problems have the same value. Graph G is said to have the cycle cover property if for every Eulerian 1,2-weighting w : E(G) ↦ {1,2} there exists a family C of circuits of G such that every edge e is in precisely we circuits of C. The cycle cover property implies the CPP = SCC property. We give a counterexample to a conjecture of Zhang (J. Graph Theory 14(5) (1990) 537; Ann. Discrete Math. 55 (1993) 183; Integer Flows and Cycle Covers of Graphs, Marcel Dekker, New York, 1997; Deans, Graph Structure Theory, AMS, Providence, RI, 1993, pp. 677–688) stating the equivalence of the cycle cover property and the CPP = SCC property for 3-connected graphs. This is also a counterexample to the stronger conjecture of Lai and Zhang, stating that every 3-connected graph with the CPP = SCC property has a nowhere-zero 4-flow. We actually obtain infinitely many cyclically 4-connected counterexamples to both conjectures. [Copyright &y& Elsevier]

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]

Abstract: A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting () or crossing (). Given a family of linear graphs, and a non-empty subset , we are interested in the Maximum Common Structured Pattern (MCSP) problem: find a maximum size edge-disjoint graph, with edge pairs all comparable by one of the relations in , that occurs as a subgraph in each of the linear graphs of the family. The MCSP problem generalizes many structure-comparison and structure-prediction problems that arise in computational molecular biology. We give tight hardness results for the MCSP problem for -structured patterns and -structured patterns. Furthermore, we prove that the problem is approximable within ratios: (i) for -structured patterns, (ii) for -structured patterns, and (iii) for -structured patterns, where is the size of the optimal solution and is the th harmonic number. Also, we provide combinatorial results concerning different types of structured patterns that are of independent interest in their own right. [Copyright &y& Elsevier]

A sequence of vertices in a graph G is called a legal dominating sequence if every vertex in the sequence dominates at least one vertex not dominated by those vertices that precede it, and at the end all vertices of G are dominated. While the length of a shortest such sequence is the domination number of G , in this paper we investigate legal dominating sequences of maximum length, which we call the Grundy domination number of G . We prove that every graph has a legal dominating sequence of each possible length between its domination number and its Grundy domination number, and characterize the graphs for which the domination number and Grundy domination number are both equal to k , for k ≤ 3 . We also prove that the decision version of the Grundy domination number is NP-complete, even when restricted to the class of chordal graphs, and present linear time algorithms for determining this number in trees, cographs and split graphs. Several results are extended to the context of edge covers in hypergraphs. [ABSTRACT FROM AUTHOR]