Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees

In this paper we consider the problem of partitioning complete multipartite graphs with edges colored by 2 colors into the minimum number of vertex disjoint monochromatic cycles, paths and trees, respectively. For general graphs we simply address the decision version of these three problems the 2-PGMC, 2-PGMP and 2-PGMT problems, respectively. We show that both 2-PGMC and 2-PGMP problems are NP-complete for complete multipartite graphs and the 2-PGMT problem is NP-complete for bipartite graphs. This also implies that all these three problems are NP-complete for general graphs, which solves a question proposed by the authors in a previous paper. Nevertheless, we show that the 2-PGMT problem can be solved in polynomial time for complete multipartite graphs. Research supported by NSFC.     

A characterization of linearizable instances of the quadratic minimum spanning tree problem

We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph \(G=(V,E)\) that can be solved as a linear minimum spanning tree problem. We give a characterization of such problems when G is a complete graph, which is the standard case in the QMSTP literature. We extend our characterization to a larger class of graphs that include complete bipartite graphs and cactuses, among others. Our characterization can be verified in \(O(|E|^2)\) time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in O(|E|) time. Related open problems are also indicated.     

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.     

The densest <Emphasis Type="Italic">k</Emphasis>-subgraph problem on clique graphs

The Densest k-Subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The problem is strongly NP-hard, as a generalization of the well known Clique problem and we also know that it does not admit a Polynomial Time Approximation Scheme (PTAS). In this paper we focus on special cases of the problem, with respect to the class of the input graph. Especially, towards the elucidation of the open questions concerning the complexity of the problem for interval graphs as well as its approximability for chordal graphs, we consider graphs having special clique graphs. We present a PTAS for stars of cliques and a dynamic programming algorithm for trees of cliques. M.L. is co-financed within Op. Education by the ESF (European Social Fund) and National Resources. V.Z. is partially supported by the Special Research Grants Account of the University of Athens under Grant 70/4/5821.     

Probabilistic graph-coloring in bipartite and split graphs

We revisit in this paper the stochastic model for minimum graph-coloring introduced in (Murat and Paschos in Discrete Appl. Math. 154:564–586, 2006), and study the underlying combinatorial optimization problem (called probabilistic coloring) in bipartite and split graphs. We show that the obvious 2-coloring of any connected bipartite graph achieves standard-approximation ratio 2, that when vertex-probabilities are constant probabilistic coloring is polynomial and, finally, we propose a polynomial algorithm achieving standard-approximation ratio 8/7. We also handle the case of split graphs. We show that probabilistic coloring is NP-hard, even under identical vertex-probabilities, that it is approximable by a polynomial time standard-approximation schema but existence of a fully a polynomial time standard-approximation schema is impossible, even for identical vertex-probabilities, unless P=NP. We finally study differential-approximation of probabilistic coloring in both bipartite and split graphs. Part of this research has been performed while the second author was with the LAMSADE on a research position funded by the CNRS.     

Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs

A set D?V of a graph G=(V,E) is a dominating set of G if every vertex in V?D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if the induced subgraph, G[D], has a perfect matching. Given a graph G=(V,E) and a positive integer k, the paired-domination problem is to decide whether G has a paired-dominating set of cardinality at most k. The paired-domination problem is known to be NP-complete for bipartite graphs. In this paper, we, first, strengthen this complexity result by showing that the paired-domination problem is NP-complete for perfect elimination bipartite graphs. We, then, propose a linear time algorithm to compute a minimum paired-dominating set of a chordal bipartite graph, a well studied subclass of bipartite graphs.     

On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph \(G=(V,E)\), the complete width of G is the minimum k such that there exist k independent sets \(\mathtt {N}_i\subseteq V\), \(1\le i\le k\), such that the graph \(G'\) obtained from G by adding some new edges between certain vertices inside the sets \(\mathtt {N}_i\), \(1\le i\le k\), is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on \(3K_2\)-free bipartite graphs and polynomially solvable on \(2K_2\)-free bipartite graphs and on \((2K_2,C_4)\)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on \(\overline{3K_2}\)-free co-bipartite graphs and polynomially solvable on \(C_4\)-free co-bipartite graphs and on \((2K_2, C_4)\)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most \(2^k\) vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most \(2^k\) vertices. Finally we determine all graphs of small complete width \(k\le 3\).     

On the max-weight edge coloring problem

We study the following generalization of the classical edge coloring problem: Given a weighted graph, find a partition of its edges into matchings (colors), each one of weight equal to the maximum weight of its edges, so that the total weight of the partition is minimized. We explore the frontier between polynomial and NP-hard variants of the problem, with respect to the class of the underlying graph, as well as the approximability of NP-hard variants. In particular, we present polynomial algorithms for bounded degree trees and star of chains, as well as an approximation algorithm for bipartite graphs of maximum degree at most twelve which beats the best known approximation ratios.     

The Travelling Salesman Problem on Permuted Monge Matrices

We consider traveling salesman problems (TSPs) with a permuted Monge matrix as cost matrix where the associated patching graph has a specially simple structure: a multistar, a multitree or a planar graph. In the case of multistars, we give a complete, concise and simplified presentation of Gaikov's theory. These results are then used for designing an O(m3 + mn) algorithm in the case of multitrees, where n is the number of cities and m is the number of subtours in an optimal assignment. Moreover we show that for planar patching graphs, the problem of finding an optimal subtour patching remains NP-complete.     

Minimal path decomposition of complete bipartite graphs

This paper deals with the subject of minimal path decomposition of complete bipartite graphs. A path decomposition of a graph is a decomposition of it into simple paths such that every edge appears in exactly one path. If the number of paths is the minimum possible, the path decomposition is called minimal. Algorithms that derive such decompositions are presented, along with their proof of correctness, for the three out of the four possible cases of a complete bipartite graph.     

A rearrangement of adjacency matrix based approach for solving the crossing minimization problem

In this paper, we first present a binary linear programming formulation for the crossing minimization problem (CMP) in bipartite graphs. Then we use the models of a modified minimum cost flow problem (MMCF) and a travelling salesman problem (TSP) to approximatively solve the CMP by rearranging the adjacency matrix of the bipartite graph. Our approaches are useful for problems defined on dense bipartite graphs. In addition, we compute the exact crossing numbers for some general dense 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.     

Broadcasting multiple messages in the 1-in port model in optimal time

In the 1-in port model, every vertex of a synchronous network can receive at most one message in each time unit. We consider simultaneous broadcasting of multiple messages from the same source or from distinct sources in such networks with an additional restriction that every received message can be sent out to neighbors only in the next time unit and never to already informed vertex. We use a general concept of level-disjoint partitions developed for this scenario. Here we introduce a subgraph extension technique for efficient spreading information within this concept. Surprisingly, this approach with so called biwheels leads to simultaneous broadcasting of optimal number of messages on a wide class of graphs in optimal time. In particular, we provide tight results for bipartite tori, meshes, hypercubes, Knödel graphs, circulant graphs. We also propose several open problems and conjectures.     

Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs

For given a pair of nodes in a graph, the minimum non-separating path problem looks for a minimum weight path between the two nodes such that the remaining graph after removing the path is still connected. The balanced connected bipartition (BCP₂) problem looks for a way to bipartition a graph into two connected subgraphs with their weights as equal as possible. In this paper we present an algorithm in time O(NlogN) for finding a minimum weight non-separating path between two given nodes in a grid graph of N nodes with positive weight. This result leads to a 5/4-approximation algorithm for the BCP₂ problem on grid graphs, which is the currently best ratio achieved in polynomial time. We also developed an exact algorithm for the BCP₂ problem on grid graphs. Based on the exact algorithm and a rounding technique, we show an approximation scheme, which is a fully polynomial time approximation scheme for fixed number of rows.     

Augmenting weighted graphs to establish directed point-to-point connectivity

We consider an augmentation problem on undirected and directed graphs, where given a directed (an undirected) graph G and p pairs of vertices \(P=\left\{ {\left( {s_1 ,t_1 } \right) ,\ldots ,\left( {s_p ,t_p } \right) } \right\} \), one has to find the minimum weight set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented to have) directed paths between the specified pairs of vertices. In the undirected case, we present an FPT-algorithm with respect to the number of new edges. Also, we have implemented and evaluated the algorithm on some real-world networks to show its efficiency in decreasing the size of input graphs and converting them to much smaller kernels. In the directed case, we consider the complexity of the problem with respect to the various parameters and present some parameterized algorithms and parameterized complexity results for it.     

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.     

Lower bounds for positive semidefinite zero forcing and their applications

The positive semidefinite zero forcing number of a graph is a parameter that is important in the study of minimum rank problems. In this paper, we focus on the algorithmic aspects of computing this parameter. We prove that it is NP-complete to find the positive semidefinite zero forcing number of a given graph, and this problem remains NP-complete even for graphs with maximum vertex degree 7. We present a linear time algorithm for computing the positive semidefinite zero forcing number of generalized series–parallel graphs. We introduce the constrained tree cover number and apply it to improve lower bounds for positive semidefinite zero forcing. We also give formulas for the constrained tree cover number and the tree cover number on graphs with special structures.     

The thickness of the complete multipartite graphs and the join of graphs

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is known for relatively few classes of graphs, compared to other topological invariants, e.g., genus and crossing number. For the complete bipartite graphs, Beineke et al. (Proc Camb Philos Soc 60:1–5, 1964) gave the answer for most graphs in this family in 1964. In this paper, we derive formulas and bounds for the thickness of some complete k-partite graphs. And some properties for the thickness for the join of two graphs are also obtained.     

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.     

Fast searching games on graphs

Given a graph, suppose that intruders hide on vertices or along edges of the graph. The fast searching problem is to find the minimum number of searchers required to capture all the intruders satisfying the constraint that every edge is traversed exactly once and searchers are not allowed to jump. In this paper, we prove lower bounds on the fast search number. We present a linear time algorithm to compute the fast search number of Halin graphs and their extensions. We present a quadratic time algorithm to compute the fast search number of cubic graphs.