The maximum flow problem with disjunctive constraints

We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at least one arc has to carry flow in a feasible solution. It is convenient to represent the negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the arcs of the underlying graph, and whose edges encode the constraints. Analogously we represent the positive disjunctive constraints by a so-called forcing graph. For conflict graphs we prove that the maximum flow problem is strongly $\mathcal{NP}$ -hard, even if the conflict graph consists only of unconnected edges. This result still holds if the network consists only of disjoint paths of length three. For forcing graphs we also provide a sharp line between polynomially solvable and strongly $\mathcal{NP}$ -hard instances for the case where the flow values are required to be integral. Moreover, our hardness results imply that no polynomial time approximation algorithm can exist for both problems. In contrast to this we show that the maximum flow problem with a forcing graph can be solved efficiently if fractional flow values are allowed.     

Maximum cardinality neighbourly sets in quadrilateral free graphs

Neighbourly set of a graph is a subset of edges which either share an end point or are joined by an edge of that graph. The maximum cardinality neighbourly set problem is known to be NP-complete for general graphs. Mahdian (Discret Appl Math 118:239–248, 2002) proved that it is in polynomial time for quadrilateral-free graphs and proposed an \(O(n^{11})\) algorithm for the same, here n is the number of vertices in the graph, (along with a note that by a straightforward but lengthy argument it can be proved to be solvable in \(O(n^5)\) running time). In this paper we propose an \(O(n^2)\) time algorithm for finding a maximum cardinality neighbourly set in a quadrilateral-free graph.     

A refined algorithm for maximum independent set in degree-4 graphs

The maximum independent set problem is one of the most important problems in theoretical analysis on time and space complexities of exact algorithms. Theoretical improvement on upper bounds on time complexity to solve this problem in low-degree graphs can lead to an improvement on that to the problem in general graphs. In this paper, we derive an upper bound \(O^*(1.1376^n)\) on the time complexity of a polynomial-space algorithm that solves the maximum independent set problem in an n-vertex graph with degree bounded by 4, improving all previous upper bounds on the time complexity of exact algorithms to this problem. Our algorithm is a branch-and-reduce algorithm and analyzed by using the measure-and-conquer method. To make an amortized analysis of the running time bound, we use an idea of “shift” to save some decrease of the measure from good branches to bad branches. Our algorithm first deals with small vertex cuts and vertices of degree \({\ge }5\), which may be created in our algorithm even if the input graph has maximum degree 4, then eliminates cycles of length 3 and 4 containing degree-4 vertices, and finally branches on degree-4 vertices. We invoke an exact algorithm for this problem in graphs with maximum degree 3 directly when the graph has no vertices of degree \({\ge }4\). Branching on degree-4 vertices on special local structures will be the bottleneck case, and we carefully design rules of choosing degree-4 vertices to branch on so that the resulting instances after branching decrease the measure effectively in the next step.     

Recognition of overlap graphs

Overlap graphs occur in computational biology and computer science, and have applications in genome sequencing, string compression, and machine scheduling. Given two strings \(s_{i}\) and \(s_{j}\) , their overlap string is defined as the longest string \(v\) such that \(s_{i} = uv\) and \(s_{j} = vw\) , for some non empty strings \(u,w\) , and its length is called the overlap between these two strings. A weighted directed graph is an overlap graph if there exists a set of strings with one-to-one correspondence to the vertices of the graph, such that each arc weight in the graph equals the overlap between the corresponding strings. In this paper, we characterize the class of overlap graphs, and we present a polynomial time recognition algorithm as a direct consequence. Given a weighted directed graph \(G\) , the algorithm constructs a set of strings that has \(G\) as its overlap graph, or decides that this is not possible.     

On computing a minimum secure dominating set in block graphs

In a graph \(G=(V,E)\), a set \(D \subseteq V\) is said to be a dominating set of G if for every vertex \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\). A secure dominating set of the graph G is a dominating set D of G such that for every \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\) and \((D{\setminus }\{v\})\cup \{u\}\) is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.     

Special Issue for FAW 2014

For a graph \(G=(V,E)\), a dominating set is a set \(D\subseteq V\) such that every vertex \(v\in V\setminus D\) has a neighbor in \(D\). The minimum outer-connected dominating set (Min-Outer-Connected-Dom-Set) problem for a graph \(G\) is to find a dominating set \(D\) of \(G\) such that \(G[V\setminus D]\), the induced subgraph by \(G\) on \(V\setminus D\), is connected and the cardinality of \(D\) is minimized. In this paper, we consider the complexity of the Min-Outer-Connected-Dom-Set problem. In particular, we show that the decision version of the Min-Outer-Connected-Dom-Set problem is NP-complete for split graphs, a well known subclass of chordal graphs. We also consider the approximability of the Min-Outer-Connected-Dom-Set problem. We show that the Min-Outer-Connected-Dom-Set problem cannot be approximated within a factor of \((1-\varepsilon ) \ln |V|\) for any \(\varepsilon >0\), unless NP \(\subseteq \) DTIME(\(|V|^{\log \log |V|}\)). For sufficiently large values of \(\varDelta \), we show that for graphs with maximum degree \(\varDelta \), the Min-Outer-Connected-Dom-Set problem cannot be approximated within a factor of \(\ln \varDelta -C \ln \ln \varDelta \) for some constant \(C\), unless P \(=\) NP. On the positive side, we present a \(\ln (\varDelta +1)+1\)-factor approximation algorithm for the Min-Outer-Connected-Dom-Set problem for general graphs. We show that the Min-Outer-Connected-Dom-Set problem is APX-complete for graphs of maximum degree 4.     

Reconfiguration of dominating sets

We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph G is a set S of vertices such that each vertex is either in S or has a neighbour in S. In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions s and t such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of k, we consider properties of \(D_k(G)\), the graph consisting of a node for each dominating set of size at most k and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that \(D_{\varGamma (G)+1}(G)\) is not necessarily connected, for \(\varGamma (G)\) the maximum cardinality of a minimal dominating set in G. The result holds even when graphs are constrained to be planar, of bounded tree-width, or b-partite for \(b \ge 3\). Moreover, we construct an infinite family of graphs such that \(D_{\gamma (G)+1}(G)\) has exponential diameter, for \(\gamma (G)\) the minimum size of a dominating set. On the positive side, we show that \(D_{n-\mu }(G)\) is connected and of linear diameter for any graph G on n vertices with a matching of size at least \(\mu +1\).     

The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set

The classical greedy heuristic for approximating maximum independent set is simple and efficient. It achieves a performance ratio of ( + 2)/3, where is the maximum node degree of the input graph. All known algorithms for the problem with better performance ratios are much more complicated and inefficient. In this paper, we propose a natural extension of the greedy heuristic. It is as simple and as efficient as the classical greedy heuristic. By a careful analysis on the structure of the intermediate graphs manipulated by our heuristic, we prove that the performance ratio is improved to ( + 3)/3.25.     

Arcs in $$\mathbb Z^2_{2p}$$

An arc in \(\mathbb Z^2_n\) is defined to be a set of points no three of which are collinear. We describe some properties of arcs and determine the maximum size of arcs for some small n.     

Modified linear programming and class 0 bounds for graph pebbling

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move removes two pebbles from some vertex and places one pebble on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. First, we improve on results of Hurlbert, who introduced a linear optimization technique for graph pebbling. In particular, we use a different set of weight functions, based on graphs more general than trees. We apply this new idea to some graphs from Hurlbert’s paper to give improved bounds on their pebbling numbers. Second, we investigate the structure of Class 0 graphs with few edges. We show that every n-vertex Class 0 graph has at least \(\frac{5}{3}n - \frac{11}{3}\) edges. This disproves a conjecture of Blasiak et al. For diameter 2 graphs, we strengthen this lower bound to \(2n - 5\), which is best possible. Further, we characterize the graphs where the bound holds with equality and extend the argument to obtain an identical bound for diameter 2 graphs with no cut-vertex.     

On maximum Wiener index of trees and graphs with given radius

Let G be a connected graph of order n. The long-standing open and close problems in distance graph theory are: what is the Wiener index W(G) or average distance \(\mu (G)\) among all graphs of order n with diameter d (radius r)? There are very few number of articles where were worked on the relationship between radius or diameter and Wiener index. In this paper, we give an upper bound on Wiener index of trees and graphs in terms of number of vertices n, radius r, and characterize the extremal graphs. Moreover, from this result we give an upper bound on \(\mu (G)\) in terms of order and independence number of graph G. Also we present another upper bound on Wiener index of graphs in terms of number of vertices n, radius r and maximum degree \(\Delta \), and characterize the extremal graphs.     

On Integrality, Stability and Composition of Dicycle Packings and Covers

Given a digraph D, the minimum integral dicycle cover problem (known also as the minimum feedback arc set problem) is to find a minimum set of arcs that intersects every dicycle; the maximum integral dicycle packing problem is to find a maximum set of pairwise arc disjoint dicycles. These two problems are NP-complete.Assume D has a 2-vertex cut. We show how to derive a minimum dicycle cover (a maximum dicycle packing) for D, by composing certain covers (packings) of the corresponding pieces. The composition of the covers is simple and was partially considered in the literature before. The main contribution of this paper is to the packing problem. Let be the value of a minimum integral dicycle cover, and * () the value of a maximum (integral) dicycle packing. We show that if = then a simple composition, similar to that of the covers, is valid for the packing problem. We use these compositions to extend an O(n³) (resp., O(n⁴)) algorithm for finding a minimum integral dicycle cover (resp., packing) from planar digraphs to K_3,3-free digraphs (i.e., digraphs not containing any subdivision of K_3,3).However, if , then such a simple composition for the packing problem is not valid. We show, that if the pieces satisfy, what we call, the stability property, then a simple composition does work. We prove that if = * holds for each piece, then the stability property holds as well. Further, we use the stability property to show that if = * holds for each piece, then = * holds for D as well.     

Safe sets in graphs: Graph classes and structural parameters

A safe set of a graph \(G=(V,E)\) is a non-empty subset S of V such that for every component A of G[S] and every component B of \(G[V {\setminus } S]\), we have \(|A| \ge |B|\) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.     

Algorithm complexity of neighborhood total domination and $$(\rho ,\gamma _{nt})$$-graphs

A neighborhood total dominating set, abbreviated for NTD-set D, is a vertex set of G such that D is a dominating set with an extra property: the subgraph induced by the open neighborhood of D has no isolated vertex. The neighborhood total domination number, denoted by \(\gamma _{nt}(G)\), is the minimum cardinality of a NTD-set in G. In this paper, we prove that NTD problem is NP-complete for bipartite graphs and split graphs. Then we give a linear-time algorithm to determine \(\gamma _{nt}(T)\) for a given tree T. Finally, we characterize a constructive property of \((\gamma _{nt},2\gamma )\)-trees and provide a constructive characterization for \((\rho ,\gamma _{nt})\)-graphs, where \(\gamma \) and \(\rho \) are domination number and packing number for the given graph, respectively.     

The <Emphasis Type="Italic">k</Emphasis>-hop connected dominating set problem: approximation and hardness

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (\({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\)). We prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {NP}\)-hard on planar bipartite graphs of maximum degree 4. We also prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {APX}\)-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\). Finally, when \(k=1\), we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators.     

Maximum flows in generalized processing networks

Processing networks (cf. Koene in Minimal cost flow in processing networks: a primal approach, 1982) and manufacturing networks (cf. Fang and Qi in Optim Methods Softw 18:143–165, 2003) are well-studied extensions of traditional network flow problems that allow to model the decomposition or distillation of products in a manufacturing process. In these models, so called flow ratios \(\alpha _e \in [0,1]\) are assigned to all outgoing edges of special processing nodes. For each such special node, these flow ratios, which are required to sum up to one, determine the fraction of the total outgoing flow that flows through the respective edges. In this paper, we generalize processing networks to the case that these flow ratios only impose an upper bound on the respective fractions and, in particular, may sum up to more than one at each node. We show that a flow decomposition similar to the one for traditional network flows is possible and can be computed in strongly polynomial time. Moreover, we show that there exists a fully polynomial-time approximation scheme (FPTAS) for the maximum flow problem in these generalized processing networks if the underlying graph is acyclic and we provide two exact algorithms with strongly polynomial running-time for the problem on series–parallel graphs. Finally, we study the case of integral flows and show that the problem becomes \({\mathcal {NP}}\)-hard to solve and approximate in this case.     

Graphs with large paired-domination number

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 199–206. A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. Let G be a connected graph of order n with minimum degree at least two. Haynes and Slater (1998) Networks 32: 199–206, showed that if n ≥ 6, then . In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For n ≥ 14, we show that and we characterize the (infinite family of) graphs that achieve equality in this bound.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

The minimum vulnerability problem on specific graph classes

Suppose that each edge e of an undirected graph G is associated with three nonnegative integers \(\mathsf{cost}(e)\), \(\mathsf{vul}(e)\) and \(\mathsf{cap}(e)\), called the cost, vulnerability and capacity of e, respectively. Then, we consider the problem of finding \(k\) paths in G between two prescribed vertices with the minimum total cost; each edge e can be shared without any cost by at most \(\mathsf{vul}(e)\) paths, and can be shared by more than \(\mathsf{vul}(e)\) paths if we pay \(\mathsf{cost}(e)\), but cannot be shared by more than \(\mathsf{cap}(e)\) paths even if we pay the cost for e. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem is NP-hard even for bipartite outerplanar graphs, 2-trees, graphs with pathwidth two, complete bipartite graphs, and complete graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the number \(k\) of required paths.     

Neighbor sum distinguishing list total coloring of subcubic graphs

Let \(G=(V, E)\) be a simple graph and denote the set of edges incident to a vertex v by E(v). The neighbor sum distinguishing (NSD) total choice number of G, denoted by \(\mathrm{ch}_{\Sigma }^{t}(G)\), is the smallest integer k such that, after assigning each \(z\in V\cup E\) a set L(z) of k real numbers, G has a total coloring \(\phi \) satisfying \(\phi (z)\in L(z)\) for each \(z\in V\cup E\) and \(\sum _{z\in E(u)\cup \{u\}}\phi (z)\ne \sum _{z\in E(v)\cup \{v\}}\phi (z)\) for each \(uv\in E\). In this paper, we propose some reducible configurations of NSD list total coloring for general graphs by applying the Combinatorial Nullstellensatz. As an application, we present that \(\mathrm{ch}^{t}_{\Sigma }(G)\le \Delta (G)+3\) for every subcubic graph G.