A complexity dichotomy and a new boundary class for the dominating set problem

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.     

Polynomial-time approximation algorithms for the coloring problem in some cases

We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the open three cases, we present approximation polynomial-time algorithms with performance guarantees.     

Discovering classes in microarray data using island counts

We present a new biclustering algorithm to simultaneously discover tissue classes and identify a set of genes that well-characterize these classes from DNA microarray data sets. We employ a combinatorial optimization approach where the object is to simultaneously identify an interesting set of genes and a partition of the array samples that optimizes a certain score based on a novel color island statistic. While this optimization problem is NP-complete in general, we are effectively able to solve problems of interest to optimality using a branch-and-bound algorithm. We have tested the algorithm on a 30 sample Cutaneous T-cell Lymphoma data set; it was able to almost perfectly discriminate short-term survivors from long-term survivors and normal controls. Another useful feature of our method is that can easily handle missing expression data.     

Generalized median graphs and applications

We study the so-called Generalized Median graph problem where the task is to construct a prototype (i.e., a ‘model’) from an input set of graphs. While our primary motivation comes from an important biological imaging application, the problem effectively captures many vision (e.g., object recognition) and learning problems, where graphs are increasingly being adopted as a powerful representation tool. Existing techniques for his problem are evolutionary search based; in this paper, we propose a polynomial time algorithm based on a linear programming formulation. We propose an additional algorithm based on a bi-level method to obtain solutions arbitrarily close to the optimal in (worst case) non-polynomial time. Within this new framework, one can optimize edit distance functions that capture similarity by considering vertex labels as well as he graph structure simultaneously. We first discuss experimental evaluations in context of molecular image analysis problems—he methods will provide the basis for building a topological map of all 23 pairs of the human chromosome. Later, we include (a) applications to other biomedical problems and (b) evaluations on a public pattern recognition graph database. This work was supported by NSF grants CCF-0546509, IIS-0713489, and NIH grant GM 072131-23. The second author was also supported in part by the Department of Biostatistics and Medical Informatics, UW-Madison and UW ICTR, funded through an NIH Clinical and Translational Science Award (CTSA), grant number 1 UL1 RR025011.     

Multi-way clustering and biclustering by the Ratio cut and Normalized cut in graphs

In this paper, we consider the multi-way clustering problem based on graph partitioning models by the Ratio cut and Normalized cut. We formulate the problem using new quadratic models. Spectral relaxations, new semidefinite programming relaxations and linearization techniques are used to solve these problems. It has been shown that our proposed methods can obtain improved solutions. We also adapt our proposed techniques to the bipartite graph partitioning problem for biclustering.     

Fibonacci index and stability number of graphs: a polyhedral study

The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this paper, we establish tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs and connected graphs. Turán graphs frequently appear in extremal graph theory. We show that Turán graphs and a connected variant of them are also extremal for these particular problems. We also make a polyhedral study by establishing all the optimal linear inequalities for the stability number and the Fibonacci index, inside the classes of general and connected graphs of order n.     

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.     

Some graph optimization problems with weights satisfying linear constraints

In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including maximum matching problem under linear constraints (max-MLC), minimum perfect matching problem under linear constraints (min-PMLC), shortest path problem under linear constraints (SPLC) and vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and find the optimal solutions of corresponding graph optimization problems among all feasible choices of weights. We find that these problems are NP-hard and are hard to be approximated in general. These findings suggest us to explore various special cases of them. In particular, we show that when the number of constraints is a fixed constant, all these problems are polynomially solvable. Moreover, if the total number of distinct weights is a fixed constant, then max-MLC, min-PMLC and SPLC are polynomially solvable, and VCLC has a 2-approximation algorithm. In addition, we propose approximation algorithms for various cases of max-MLC.

     

A Greedy Randomized Adaptive Search Procedure for the Feedback Vertex Set Problem

A Greedy Randomized Adaptive Search Procedure (GRASP) is a randomized heuristic that has produced high quality solutions for a wide range of combinatorial optimization problems. The NP-complete Feedback Vertex Set (FVS) Problem is to find the minimum number of vertices that need to be removed from a directed graph so that the resulting graph has no directed cycle. The FVS problem has found applications in many fields, including VLSI design, program verification, and statistical inference. In this paper, we develop a GRASP for the FVS problem. We describe GRASP construction mechanisms and local search, as well as some efficient problem reduction techniques. We report computational experience on a set of test problems using three variants of GRASP.     

Separator-based data reduction for signed graph balancing

Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.     

Approximation of knapsack problems with conflict and forcing graphs

We study the classical 0–1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be included in the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs. By modifying a recent result of Lokstanov et al. (Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 570–581, 2014) we derive a fairly complicated FPTAS for the knapsack problem on weakly chordal conflict graphs. Next, we show that the techniques of modular decompositions and clique separators, widely used in the literature for solving the independent set problem on special graph classes, can be applied to the knapsack problem with conflict graphs. In particular, we can show that every positive approximation result for the atoms of prime graphs arising from such a decomposition carries over to the original graph. We point out a number of structural results from the literature which can be used to show the existence of an FPTAS for several graph classes characterized by the exclusion of certain induced subgraphs. Finally, a PTAS for the knapsack problem with H-minor free conflict graph is derived. This includes planar graphs and, more general, graphs of bounded genus. The PTAS is obtained by expanding a general result of Demaine et al. (Proceedings of 46th annual IEEE symposium on foundations of computer science, FOCS 2005, pp 637–646, 2005). The knapsack problem with forcing graphs can be transformed into a minimization knapsack problem with conflict graphs. It follows immediately that all our FPTAS results of the current and a previous paper carry over from conflict graphs to forcing graphs. In contrast, the forcing graph variant is already inapproximable on planar graphs.     

On consecutive edge magic total labelings of connected bipartite graphs

Since Sedlá\(\breve{\hbox {c}}\)ek introduced the notion of magic labeling of a graph in 1963, a variety of magic labelings of a graph have been defined and studied. In this paper, we study consecutive edge magic labelings of a connected bipartite graph. We make a useful observation that there are only four possible values of b for which a connected bipartite graph has a b-edge consecutive magic labeling. On the basis of this fundamental result, we deduce various interesting results on consecutive edge magic labelings of bipartite graphs. As a matter of fact, we do not focus just on specific classes of graphs, but also discuss the more general classes of non-bipartite and bipartite graphs.     

Flows with unit path capacities and related packing and covering problems

Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log?m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an $O(\sqrt{m})Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an O(?m)O(\sqrt{m}) -approximation algorithm. We argue that this performance guarantee is best possible, unless P=NP.     

Feature Selection for Consistent Biclustering via Fractional 0–1 Programming

Biclustering consists in simultaneous partitioning of the set of samples and the set of their attributes (features) into subsets (classes). Samples and features classified together are supposed to have a high relevance to each other which can be observed by intensity of their expressions. We define the notion of consistency for biclustering using interrelation between centroids of sample and feature classes. We prove that consistent biclustering implies separability of the classes by convex cones. While previous works on biclustering concentrated on unsupervised learning and did not consider employing a training set, whose classification is given, we propose a model for supervised biclustering, whose consistency is achieved by feature selection. The developed model involves solution of a fractional 0–1 programming problem. Preliminary computational results on microarray data mining problems are reported.This research work was partially supported by NSF, NIH and AirForce grants.     

A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

Given an undirected graph G and two vertex subsets H1 and H2, the bi-level augmentation problem is that of adding to G the smallest number of edges such that the resulting graph contains two internally vertex-disjoint paths between every pair of vertices in H1 and two edge-disjoint paths between every pair of vertices in H2. We present an algorithm to solve this problem in linear time. By properly setting H1 and H2, this augmentation algorithm subsumes existing optimal algorithms for several graph augmentation problems.     

Complexity analysis for maximum flow problems with arc reversals

We provide a comprehensive study on network flow problems with arc reversal capabilities. The problem is to identify the arcs to be reversed in order to achieve a maximum flow from source(s) to sink(s). The problem finds its applications in emergency transportation management, where the lanes of a road network could be reversed to enable flow in the opposite direction. We study several network flow problems with the arc reversal capability and discuss their complexity. More specifically, we discuss the polynomial time algorithms for the maximum dynamic flow problem with arc reversal capability having a single source and a single sink, and for the maximum (static) flow problem. The presented algorithms are based on graph transformations and reductions to polynomially solvable flow problems. In addition, we show that the quickest transshipment problem with arc reversal capability and the problem of minimizing the total cost resulting from arc switching costs are NP\mathcal{NP} -hard.     

Order consolidation for hierarchical product lines

We consider the batch production of hierarchical product lines in raw material industry where the whole or parts of multiple customer orders may be consolidated and processed in the same batch if their product specifications are compatible. The objective of the problem is to find maximum possible number of batches completely filled up to their capacity. The compatibility relationship among product specifications is represented by a graph called the compatibility graph. If the compatibility graph is an arbitrary graph, the problem is proven to be NP-hard and belongs to Max SNP-hard class. We develop an optimum algorithm for an important subclass of the problem where the graph is a quasi-threshold graph which in fact is the case for producing hierarchical product lines that are often found in raw materials industry.     

The optimum traversal of a graph

For a given graph (network) having costs [c_ij] associated with its links, the present paper examines the problem of finding a cycle which traverses every link of the graph at least once, and which incurs the minimum cost of traversal. This problem (called thegraph traversal problem, or theChinese postman problem [9]) can be formulated in ways analogous to those used for the well-known travelling salesman problem, and using this apparent similarity, Bellman and Cooke [1] have produced a dynamic programming formulation. This method of solution of the graph traversal problem requires computational times which increase exponentially with the number of links in the graph. Approximately the same rate of increase of computational effort with problem size would result by any other method adapting a travelling salesman algorithm to the present problem.This paper describes an efficient algorithm for the optimal solution of the graph traversal problem based on the matching method of Edmonds [5, 6]. The computational time requirements of this algorithm increase as a low order (2 or 3) power of the number of links in the graph. Computational results are given for graphs of up to 50 vertices and 125 links.The paper then discusses a generalised version of the graph traversal problem, where not one but a number of cycles are required to traverse the graph. In this case each link has (in addition to its cost) a quantity q_ij associated with it, and the sum of the quantities of the links in any one cycle must be less than a given amount representing the cycle capacity. A heuristic algorithm for the solution of this problem is given. The algorithm is based on the optimal algorithm for the single-cycle graph traversal problem and is shown to produce near-optimal results.There is a large number of possible applications where graph traversal problems arise. These applications include: the spraying of roads with salt-grit to prevent ice formation, the inspection of electric power lines, gas, or oil pipelines for faults, the delivery of letter post, etc.     

Graph Algorithms with Small Communication Costs

We study minimizing communication cost in parallel algorithm design, by minimizing the number of communication phases in coarse-grained parallel computers. There have been several recent papers dealing with parallel algorithms of small communication cost under different models. Most of these results are for computational geometry problems. For these problems it has been possible to decompose tasks into appropriate subproblems in a communication-efficient way. It appears to be somewhat more difficult to design parallel algorithms with small communication phases for graph theory problems. In this paper we focus on the design of deterministic algorithms with a small number of communication phases for the list ranking problem and the shortest path problem.     

Compact labelings for efficient first-order model-checking

We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checking a first-order formula with free set variables in the graphs of every class that is nicely locally clique-width-decomposable. This notion generalizes that of a nicely locally tree-decomposable class. The graphs of such classes can be covered by graphs of bounded clique-width with limited overlaps. We also consider such labelings for bounded first-order formulas on graph classes of bounded expansion. Some of these results are extended to counting queries.