Feedback vertex sets in star graphs

In a graph G=(V,E), a subset F⊂V(G) is a feedback vertex set of G if the subgraph induced by V(G)?F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs.     

A note on finding all homogeneous set sandwiches

A module is a set of vertices H of a graph G=(V,E) such that each vertex of V?H is either adjacent to all vertices of H or to none of them. A homogeneous set is a nontrivial module. A graph G_s=(V,E_s) is a sandwich for a pair of graphs G_t=(V,E_t) and G=(V,E) if E_t⊆E_s⊆E. In a recent paper, Tang et al. [Inform. Process. Lett. 77 (2001) 17-22] described an O(Δn²) algorithm for testing the existence of a homogeneous set in sandwich graphs of G_t=(V,E_t) and G=(V,E) and then extended it to an enumerative algorithm computing all these possible homogeneous sets. In this paper, we invalidate this latter algorithm by proving there are possibly exponentially many such sets, even if we restrict our attention to strong modules. We then give a correct characterization of a homogeneous set of a sandwich graph.     

Minimal proper interval completions

Given an arbitrary graph G=(V,E) and a proper interval graph H=(V,F) with E⊆F we say that H is a proper interval completion of G. The graph H is called a minimal proper interval completion of G if, for any sandwich graph H^′=(V,F^′) with E⊆F^′⊂F, H^′ is not a proper interval graph. In this paper we give a O(n+m) time algorithm computing a minimal proper interval completion of an arbitrary graph. The output is a proper interval model of the completion.     

Counting edge crossings in a 2-layered drawing

Given a bipartite graph G=(V,W,E) with a bipartition {V,W} of a vertex set and an edge set E, a 2-layered drawing of G in the plane means that the vertices of V and W are respectively drawn as distinct points on two parallel lines and the edges as straight line segments. We consider the problem of counting the number of edge crossings. In this paper, we design two algorithms to this problem based on the dynamic programming and divide-and-conquer approaches. These algorithms run in O(n₁n₂) time and O(m) space and in O(min{n₁n₂,|E|log(min{|V|,|W|})}) time and O(m) space, respectively. Our algorithms outperform the previously fastest Θ(|E|log(min{|V|,|W|})) time algorithm for dense graphs.     

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 ⁿ ).     

Power Domination in Circular-Arc Graphs

A set S?V is a power dominating set (PDS) of a graph G=(V,E) if every vertex and every edge in G can be observed based on the observation rules of power system monitoring. The power domination problem involves minimizing the cardinality of a PDS of a graph. We consider this combinatorial optimization problem and present a linear time algorithm for finding the minimum PDS of an interval graph if the interval ordering of the graph is provided. In addition, we show that the algorithm, which runs in Θ(nlogn) time, where n is the number of intervals, is asymptotically optimal if the interval ordering is not given. We also show that the results hold for the class of circular-arc graphs.     

The labeled perfect matching in bipartite graphs

In this paper, we deal with both the complexity and the approximability of the labeled perfect matching problem in bipartite graphs. Given a simple graph G=(V,E) with |V|=2n vertices such that E contains a perfect matching (of size n), together with a color (or label) function , the labeled perfect matching problem consists in finding a perfect matching on G that uses a minimum or a maximum number of colors.     

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

A linear-time algorithm for paired-domination problem in strongly chordal graphs

Let G=(V,E) be a simple graph without isolated vertices. A vertex set S⊆V is a paired-dominating set if every vertex in V−S has at least one neighbor in S and the induced subgraph G[S] has a perfect matching. In this paper, we present a linear-time algorithm to find a minimum paired-dominating set in strongly chordal graphs if the strong (elimination) ordering of the graph is given in advance.     

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.     

Flow equivalent trees in undirected node-edge-capacitated planar graphs

Given an edge-capacitated undirected graph G=(V,E,C) with edge capacity , n=|V|, an s−t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s−t edge cut is an s−t edge cut with the minimum cut value among all s−t edge cuts. A theorem given by Gomory and Hu states that there are only n−1 distinct values among the n(n−1)/2 minimum edge cuts in an edge-capacitated undirected graph G, and these distinct cuts can be compactly represented by a tree with the same node set as G, which is referred to the flow equivalent tree. In this paper we generalize their result to the node-edge cuts in a node-edge-capacitated undirected planar graph. We show that there is a flow equivalent tree for node-edge-capacitated undirected planar graphs, which represents the minimum node-edge cut for any pair of nodes in the graph through a novel transformation.     

Weighted Coloring: further complexity and approximability results

Given a vertex-weighted graph G=(V,E;w), w(v)?0 for any v∈V, we consider a weighted version of the coloring problem which consists in finding a partition S=(S₁,…,Sk) of the vertex set of G into stable sets and minimizing where the weight of S is defined as . In this paper, we continue the investigation of the complexity and the approximability of this problem by answering some of the questions raised by Guan and Zhu [D.J. Guan, X. Zhu, A coloring problem for weighted graphs, Inform. Process. Lett. 61 (2) (1997) 77-81].     

Simplicial powers of graphs

In a graph, a vertex is simplicial if its neighborhood is a clique. For an integer k≥1, a graph G=(V_G,E_G) is the k-simplicial power of a graph H=(V_H,E_H) (H a root graph of G) if V_G is the set of all simplicial vertices of H, and for all distinct vertices x and y in V_G, xyE_G if and only if the distance in H between x and y is at most k. This concept generalizes k-leaf powers introduced by Nishimura, Ragde and Thilikos which were motivated by the search for underlying phylogenetic trees; k-leaf powers are the k-simplicial powers of trees. Recently, a lot of work has been done on k-leaf powers and their roots as well as on their variants phylogenetic roots and Steiner roots. For k≤5, k-leaf powers can be recognized in linear time, and for k≤4, structural characterizations are known. For k≥6, the recognition and characterization problems of k-leaf powers are still open. Since trees and block graphs (i.e., connected graphs whose blocks are cliques) have very similar metric properties, it is natural to study k-simplicial powers of block graphs. We show that leaf powers of trees and simplicial powers of block graphs are closely related, and we study simplicial powers of other graph classes containing all trees such as ptolemaic graphs and strongly chordal graphs.     

Note on the connectivity of line graphs

Let G be a connected graph with vertex set V(G), edge set E(G), vertex-connectivity κ(G) and edge-connectivity λ(G).A subset S of E(G) is called a restricted edge-cut if G−S is disconnected and each component contains at least two vertices. The restricted edge-connectivity λ₂(G) is the minimum cardinality over all restricted edge-cuts. Clearly λ₂(G)?λ(G)?κ(G).In 1969, Chartrand and Stewart have shown that

     

The algorithmic complexity of mixed domination in graphs

Let G=(V,E) be a simple graph with vertex set V and edge set E. A subset W⊆V∪E is a mixed dominating set if every element x∈(V∪E)?W is either adjacent or incident to an element of W. The mixed domination problem is to find a minimum mixed dominating set of G. In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs.     

Signed and minus clique-transversal functions on graphs

A minus (respectively, signed) clique-transversal function of a graph G=(V,E) is a function (respectively, {−1,1}) such that _∑u∈Cf(u)?1 for every maximal clique C of G. The weight of a minus (respectively, signed) clique-transversal function of G is f(V)=_∑v∈Vf(v). The minus (respectively, signed) clique-transversal problem is to find a minus (respectively, signed) clique-transversal function of G of minimum weight. In this paper, we present a unified approach to these two problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. We also prove that the signed clique-transversal problem is NP-complete for chordal graphs and planar graphs.     

An efficient distributed algorithm for finding all hinge vertices in networks

Let G=(V, E) be a graph with vertex set V of size n and edge set E of size m. A vertex v∈V is called a hinge vertex if there exist two vertices in V\{v} such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O(n ²) time complexity and O(m) message complexity. In particular, the total messages exchanged during the algorithm are at most 2m(log n+nlog n+1) bits.     

A Cubic-Vertex Kernel for Flip Consensus Tree

Given a bipartite graph G=(V _c ,V _t ,E) and a nonnegative integer k, the NP-complete Minimum-Flip Consensus Tree problem asks whether G can be transformed, using up to k edge insertions and deletions, into a graph that does not contain an induced P ₅ with its first vertex in V _t (a so-called M-graph or Σ-graph). This problem plays an important role in computational phylogenetics, V _c standing for the characters and V _t standing for taxa. Chen et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3:165–173, 2006). showed that Minimum-Flip Consensus Tree is NP-complete and presented a parameterized algorithm with running time O(6 ^k ?|V _t |?|V _c |). Subsequently, Böcker et al. (ACM Trans. Algorithms 8:7:1–7:17, 2012) presented a refined search tree algorithm with running time O(4.42 ^k (|V _t |+|V _c |)+|V _t |?|V _c |). We continue the study of Minimum-Flip Consensus Tree parameterized by k. Our main contribution are polynomial-time executable data reduction rules yielding a problem kernel with O(k ³) vertices. In addition, we present an improved search tree algorithm with running time O(3.68 ^k ?|V _c |²|V _t |).     

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

Total restrained domination in graphs

In this paper, we initiate the study of a variation of standard domination, namely total restrained domination. Let G=(V,E) be a graph. A set D⊆V is a total restrained dominating set if every vertex in V−D has at least one neighbor in D and at least one neighbor in V−D, and every vertex in D has at least one neighbor in D. The total restrained domination number of G, denoted by γ_tr(G), is the minimum cardinality of all total restrained dominating sets of G. We determine the best possible upper and lower bounds for γ_tr(G), characterize those graphs achieving these bounds and find the best possible lower bounds for where both G and are connected.