Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms

For a graph G=(V,E) and a color set C, let f:E→C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G have a path in which all edges are assigned distinct colors. Chakraborty et al. defined the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. Chen et al. introduced the vertex-coloring version of the problem as a variant, and we introduce the total-coloring version in this paper. We settle the precise computational complexities of all the three problems with regards to graph diameters, and also characterize these with regards to certain graph classes: cacti, outer planer and series-parallel graphs. We then give FPT algorithms for the three problems on general graphs when parameterized by the number of colors in C; our FPT algorithms imply that all the three problems can be solved in polynomial time for any graph with n vertices if |C|=O(logn).     

Optimal 1-edge fault-tolerant designs for ladders

A graph G∗ is 1-edge fault-tolerant with respect to a graph G, denoted by 1-EFT(G), if every graph obtained by removing any edge from G∗ contains G. A 1-EFT(G) graph is optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. The kth ladder graph, L_k, is defined to be the cartesian product of the P_k and P₂ where P_n is the n-vertex path graph. In this paper, we present several 1-edge fault-tolerant graphs with respect to ladders. Some of these graphs are proven to be optimal.     

Improved fixed parameter tractable algorithms for two “edge” problems: MAXCUT and MAXDAG

We give improved parameterized algorithms for two “edge” problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite subgraph of the given graph. On the other hand, MAXDAG of a directed graph is a set of arcs of maximum size such that the graph induced on these arcs is acyclic. Our algorithms are obtained through new kernelization and efficient exact algorithms for the optimization versions of the problems. More precisely our results include:

(i)

a kernel with at most αk vertices and βk edges for MAXCUT. Here 0<α?1 and 1<β?2. Values of α and β depends on the number of vertices and the edges in the graph;

(ii)

a kernel with at most 4k/3 vertices and 2k edges for MAXDAG;

(iii)

an O^∗(k^1.2418) parameterized algorithm for MAXCUT in undirected graphs. This improves the O^∗(k^1.4143)¹ algorithm presented in [E. Prieto, The method of extremal structure on the k-maximum cut problem, in: The Proceedings of Computing: The Australasian Theory Symposium (CATS), 2005, pp. 119-126];

(iv)

an O^∗(n²) algorithm for optimization version of MAXDAG in directed graphs. This is the first such algorithm to the best of our knowledge;

(v)

an O^∗(k²) parameterized algorithm for MAXDAG in directed graphs. This improves the previous best of O^∗(k⁴) presented in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458];

(vi)

an O^∗(k¹⁶) parameterized algorithm to determine whether an oriented graph having m arcs has an acyclic subgraph with at least m/2+k arcs. This improves the O^∗(k²) algorithm given in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458].

In addition, we show that if a directed graph has minimum out degree at least f(n) (some function of n) then Directed Feedback Arc Set problem is fixed parameter tractable. The parameterized complexity of Directed Feedback Arc Set is a well-known open problem.     

Boolean-width of graphs

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods-Boolean sums of neighborhoods-across a cut of a graph. For many graph problems, this number is the runtime bottleneck when using a divide-and-conquer approach. For an n-vertex graph given with a decomposition tree of boolean-width k, we solve Maximum Weight Independent Set in time O(n²k2^2k) and Minimum Weight Dominating Set in time O(n²+nk2^3k). With an additional n² factor in the runtime, we can also count all independent sets and dominating sets of each cardinality.Boolean-width is bounded on the same classes of graphs as clique-width. boolean-width is similar to rank-width, which is related to the number of GF(2)-sums of neighborhoods instead of the Boolean sums used for boolean-width. We show for any graph that its boolean-width is at most its clique-width and at most quadratic in its rank-width. We exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n²) vertices has boolean-width Θ(logn) and rank-width, clique-width, tree-width, and branch-width Θ(n).     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

On-line maintenance of triconnected components with SPQR-trees

We consider the problem of maintaining on-line the triconnected components of a graphG. Letn be the current number of vertices ofG. We present anO(n)-space data structure that supports insertions of vertices and edges, and queries of the type “Are there three vertex-disjoint paths between verticesv ₁ andv ₂?” A sequence ofk operations takes timeO(k·α(k, n)) ifG is biconnected(α(k, n) denotes the well-known Ackermann's function inverse), and timeO(n logn+k) ifG is not biconnected. Note that the bounds do not depend on the number of edges ofG. We use theSPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and theBC-tree, which represents the decomposition of a connected graph with respect to its biconnected components.     

Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs

Let G=(V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in?G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick?(J. Assoc. Comput. Mach. 49:289–317, 2002) showed that for any fixed ε>0, stretch 1+ε distances (a path in G between u,v∈V is said to be of stretch t if its length is at most t times the distance between u and v in G) between all pairs of vertices in a weighted directed graph on n vertices can be computed in $\tilde{O}(n^{\omega})$ time, where ω<2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. Here we show that all pairs stretch 2+ε distances for any fixed ε>0 in G can be computed in expected time O(n ^9/4). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n ^9/4) for computing all-pairs stretch 5/2 distances in?G. This combinatorial algorithm will serve as a key step in our all-pairs stretch 2+ε distances algorithm.     

Finding Maximum Edge Bicliques in Convex Bipartite Graphs

A bipartite graph G=(A,B,E) is convex on B if there exists an ordering of the vertices of B such that for any vertex v??A, vertices adjacent to v are consecutive in?B. A complete bipartite subgraph of a graph G is called a biclique of G. Motivated by an application to analyzing DNA microarray data, we study the problem of finding maximum edge bicliques in convex bipartite graphs. Given a bipartite graph G=(A,B,E) which is convex on B, we present a new algorithm that computes a maximum edge biclique of G in O(nlog?³ nlog?log?n) time and O(n) space, where n=|A|. This improves the current O(n ²) time bound available for the problem. We also show that for two special subclasses of convex bipartite graphs, namely for biconvex graphs and bipartite permutation graphs, a maximum edge biclique can be computed in O(n??(n)) and O(n) time, respectively, where n=min?(|A|,|B|) and ??(n) is the slowly growing inverse of the Ackermann function.     

On the bi-enhancement of chordal-bipartite probe graphs

Given a class C of graphs, a graph G=(V,E) is said to be a C-probe graph if there exists a stable (i.e., independent) set of vertices X⊆V and a set F of pairs of vertices of X such that the graph G^′=(V,E∪F) is in the class C. Recently, there has been increasing interest and research on a variety of C-probe graph classes, such as interval probe graphs, chordal probe graphs and chain probe graphs.In this paper we focus on chordal-bipartite probe graphs. We prove a structural result that if B is a bipartite graph with no chordless cycle of length strictly greater than 6, then B is chordal-bipartite probe if and only if a certain “enhanced” graph B^∗ is a chordal-bipartite graph. This theorem is analogous to a result on interval probe graphs in Zhang (1994) [18] and to one on chordal probe graphs in Golumbic and Lipshteyn (2004) [11].     

Exact exponential-time algorithms for finding bicliques

Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E) on n vertices, a pair (X,Y), with X,Y⊆V, X∩Y=∅, is a non-induced biclique if {x,y}∈E for any x∈X and y∈Y. The NP-complete problem of finding a non-induced (k₁,k₂)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such that |X|=k₁ and |Y|=k₂. In this paper, we design a polynomial-space O(n^1.6914)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(n^1.30052). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(n^1.30052).     

Enumerating Minimal Subset Feedback Vertex Sets

The Subset Feedback Vertex Set problem takes as input a pair (G,S), where G=(V,E) is a graph with weights on its vertices, and S?V. The task is to find a set of vertices of total minimum weight to be removed from G, such that in the remaining graph no cycle contains a vertex of S. We show that this problem can be solved in time O(1.8638 ⁿ ), where n=|V|. This is a consequence of the main result of this paper, namely that all minimal subset feedback vertex sets of a graph can be enumerated in time O(1.8638 ⁿ ).     

Restricted arc-connectivity of digraphs

Since interconnection networks are often modeled by graphs or digraphs, the edge-connectivity of a graph or arc-connectivity of a digraph are important measurements for fault tolerance of networks.The restricted edge-connectivity λ^′(G) of a graph G is the minimum cardinality over all edge-cuts S in a graph G such that there are no isolated vertices in G−S. A connected graph G is called λ^′-connected, if λ^′(G) exists.In 1988, Esfahanian and Hakimi [A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988), 195-199] have shown that each connected graph G of order n?4, except a star, is λ^′-connected and satisfies λ^′(G)?ξ(G), where ξ(G) is the minimum edge-degree of G.If D is a strongly connected digraph, then we call in this paper an arc set S a restricted arc-cut of D if D−S has a non-trivial strong component D₁ such that D−V(D₁) contains an arc. The restricted arc-connectivity λ^′(D) is the minimum cardinality over all restricted arc-cuts S.We observe that the recognition problem, whether λ^′(D) exists for a strongly connected digraph D is solvable in polynomial time. Furthermore, we present some analogous results to the above mentioned theorem of Esfahanian and Hakimi for digraphs, and we show that this theorem follows easily from one of our results.     

On an infinite family of graphs with information ratio 2 − 1/k

In this paper we consider the secret sharing problem on special access structures with minimal qualified subsets of size two, i.e. secret sharing on graphs. This means that the participants are the vertices of the graph and the qualified subsets are the subsets of V(G) spanning at least one edge. The information ratio of a graph G is denoted by R(G) and is defined as the ratio of the greatest size of the shares a vertex has to remember and of the size of the secret. Since the determination of the exact information ratio is a non-trivial problem even for small graphs (i.e. for V(G) = 6), every construction can be of particular interest. Let k be the maximal degree in G. In this paper we prove that R(G) = 2 ? 1/k for every graph G with the following properties: (A) every vertex has at most one neighbour of degree one; (B) vertices of degree at least 3 are not connected by an edge; (C) the girth of the graph is at least 6. We prove this by using polyhedral combinatorics arguments and the entropy method.     

On Reversible Cascades in Scale-Free and Erdős-Rényi Random Graphs

Consider the following cascading process on a simple undirected graph G(V,E) with diameter Δ. In round zero, a set S?V of vertices, called the seeds, are active. In round i+1, i∈?, a non-isolated vertex is activated if at least a ρ∈(0,1] fraction of its neighbors are active in round i; it is deactivated otherwise. For k∈?, let min-seed^(k)(G,ρ) be the minimum number of seeds needed to activate all vertices in or before round k. This paper derives upper bounds on min-seed^(k)(G,ρ). In particular, if G is connected and there exist constants C>0 and γ>2 such that the fraction of degree-k vertices in G is at most C/k ^γ for all k∈?⁺, then min-seed^(Δ)(G,ρ)=O(?ρ ^γ?1|V|?). Furthermore, for n∈?⁺, p=Ω((ln(e/ρ))/(ρn)) and with probability 1?exp(?n ^Ω(1)) over the Erd?s-Rényi random graphs G(n,p), min-seed⁽¹⁾(G(n,p),ρ)=O(ρn).     

The edge-orientation problem and some of its variants on weighted graphs

Let G(V, E) be a connected undirected graph with n vertices and m edges, where each vertex v is associated with a cost C(v) and each edge e = (u, v) is associated with two weights, W(u → v) and W(v → u). The issue of assigning an orientation to each edge so that G becomes a directed graph is resolved in this paper. Determining a scheme to assign orientations of all edges such that max_x∈V{C(x)+∑_x→zW(x→z)} is minimized is the objective. This issue is called the edge-orientation problem (the EOP). Two variants of the EOP, the Out-Degree-EOP and the Vertex-Weighted EOP, are first proposed and then efficient algorithms for solving them on general graphs are designed. Ascertaining that the EOP is NP-hard on bipartite graphs and chordal graphs is the second result. Finally, an O(n log n)-time algorithm for the EOP on trees is designed. In general, the algorithmic results in this paper facilitate the implementation of the weighted fair queuing (WFQ) on real networks. The objective of the WFQ is to assign an effective weight for each flow to enhance link utilization. Our findings consequently can be easily extended to other classes of graphs, such as cactus graphs, block graphs, and interval graphs.     

Computing the Map of Geometric Minimal Cuts

In this paper we consider the following problem of computing a map of geometric minimal cuts (called MGMC problem): Given a graph G=(V,E) and a planar rectilinear embedding of a subgraph H=(V _H ,E _H ) of G, compute the map of geometric minimal cuts induced by axis-aligned rectangles in the embedding plane. The MGMC problem is motivated by the critical area extraction problem in VLSI designs and finds applications in several other fields. In this paper, we propose a novel approach based on a mix of geometric and graph algorithm techniques for the MGMC problem. Our approach first shows that unlike the classic min-cut problem on graphs, the number of all rectilinear geometric minimal cuts is bounded by a low polynomial, O(n ³). Our algorithm for identifying geometric minimal cuts runs in O(n ³logn(loglogn)³) expected time which can be reduced to O(nlogn(loglogn)³) when the maximum size of the cut is bounded by a constant, where n=|V _H |. Once geometric minimal cuts are identified we show that the problem can be reduced to computing the L _∞ Hausdorff Voronoi diagram of axis aligned rectangles. We present the first output-sensitive algorithm to compute this diagram which runs in O((N+K)log² NloglogN) time and O(Nlog² N) space, where N is the number of rectangles and K is the complexity of the Hausdorff Voronoi diagram. Our approach settles several open problems regarding the MGMC problem.     

Note on maximal bisection above tight lower bound

In a graph G=(V,E), a bisection (X,Y) is a partition of V into sets X and Y such that |X|?|Y|?|X|+1. The size of (X,Y) is the number of edges between X and Y. In the Max Bisection problem we are given a graph G=(V,E) and are required to find a bisection of maximum size. It is not hard to see that ⌈|E|/2⌉ is a tight lower bound on the maximum size of a bisection of G.We study parameterized complexity of the following parameterized problem called Max Bisection above Tight Lower Bound (Max-Bisec-ATLB): decide whether a graph G=(V,E) has a bisection of size at least ⌈|E|/2⌉+k, where k is the parameter. We show that this parameterized problem has a kernel with O(k²) vertices and O(k³) edges, i.e., every instance of Max-Bisec-ATLB is equivalent to an instance of Max-Bisec-ATLB on a graph with at most O(k²) vertices and O(k³) edges.