The maximum cardinality cut problem in co-bipartite chain graphs

A co-bipartite chain graph is a co-bipartite graph in which the neighborhoods of the vertices in each clique can be linearly ordered with respect to inclusion. It is known that the maximum cardinality cut problem (\({\textsc {MaxCut}}\)) is \({\textsc {NP}}{\text {-hard}}\) in co-bipartite graphs (Bodlaender and Jansen, Nordic J Comput 7(2000):14–31, 2000). We consider \({\textsc {MaxCut}}\) in co-bipartite chain graphs. We first consider the twin-free case and present an explicit solution. We then show that \({\textsc {MaxCut}}\) is polynomial time solvable in this graph class.     

A branch-and-bound algorithm for the minimum cut linear arrangement problem

Given an edge-weighted graph G of order n, the minimum cut linear arrangement problem (MCLAP) asks to find a one-to-one map from the vertices of G to integers from 1 to n such that the largest of the cut values c ₁,…,c _n?1 is minimized, where c _i , i∈{1,…,n?1}, is the total weight of the edges connecting vertices mapped to integers 1 through i with vertices mapped to integers i+1 through n. In this paper, we present a branch-and-bound algorithm for solving this problem. A salient feature of the algorithm is that it employs a dominance test which allows reducing the redundancy in the enumeration process drastically. The test is based on the use of a tabu search procedure developed to solve the MCLAP. We report computational results for both the unweighted and weighted graphs. In particular, we focus on calculating the cutwidth of some well-known graphs from the literature.     

On the performance of mildly greedy players in cut games

We continue the study of the performance of mildly greedy players in cut games initiated by Christodoulou et al. (Theoret Comput Sci 438:13–27, 2012), where a mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than \(1+\epsilon \), for some given \(\epsilon \ge 0\). Hence, in presence of mildly greedy players, the classical concepts of pure Nash equilibria and best-responses generalize to those of \((1+\epsilon )\)-approximate pure Nash equilibria and \((1+\epsilon )\)-approximate best-responses, respectively. We first show that the \(\epsilon \)-approximate price of anarchy, that is the price of anarchy of \((1+\epsilon )\)-approximate pure Nash equilibria, is at least \(\frac{1}{2+\epsilon }\) and that this bound is tight for any \(\epsilon \ge 0\). Then, we evaluate the approximation ratio of the solutions achieved after a \((1+\epsilon )\)-approximate one-round walk starting from any initial strategy profile, where a \((1+\epsilon )\)-approximate one-round walk is a sequence of \((1+\epsilon )\)-approximate best-responses, one for each player. We improve the currently known lower bound on this ratio from \(\min \left\{ \frac{1}{4+2\epsilon },\frac{\epsilon }{4+2\epsilon }\right\} \) up to \(\min \left\{ \frac{1}{2+\epsilon },\frac{2\epsilon }{(1+\epsilon )(2+\epsilon )}\right\} \) and show that this is again tight for any \(\epsilon \ge 0\). An interesting and quite surprising consequence of our results is that the worst-case performance guarantee of the very simple solutions generated after a \((1+\epsilon )\)-approximate one-round walk is the same as that of \((1+\epsilon )\)-approximate pure Nash equilibria when \(\epsilon \ge 1\) and of that of subgame perfect equilibria (i.e., Nash equilibria for greedy players with farsighted, rather than myopic, rationality) when \(\epsilon =1\).     

Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties

Journal of Combinatorial Optimization - In this paper, we introduce the submodular multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in...     

Isolation branching: a branch and bound algorithm for the k-terminal cut problem

Journal of Combinatorial Optimization - In the k-terminal cut problem, we are given a graph with edge weights and k distinct vertices called “terminals.” The goal is to remove a minimum...     

On the Bandpass problem

The complexity of the Bandpass problem is re-investigated. Specifically, we show that the problem with any fixed bandpass number B≥2 is NP-hard. Next, a row stacking algorithm is proposed for the problem with three columns, which produces a solution that is at most 1 less than the optimum. For the special case B=2, the row stacking algorithm guarantees an optimal solution. On approximation, for the general problem, we present an O(B ²)-algorithm, which reduces to a 2-approximation algorithm for the special case B=2.     

On the personnel assignment problem

Recent papers have developed methods for personnel assignment under risk of failure. In this paper, a two-parameter model is given. It uses both mean and standard deviation in the stochastic model to bring the risk of failure under control.     

An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs

Given a vertex-weighted undirected connected graph \(G = (V, E, \ell , \rho )\), where each edge \(e \in E\) has a length \(\ell (e) > 0\) and each vertex \(v \in V\) has a weight \(\rho (v) > 0\), a subset \(T \subseteq V\) of vertices and a set S containing all the points on edges in a subset \(E' \subseteq E\) of edges, the generalized absolute 1-center problem (GA1CP), an extension of the classic vertex-weighted absolute 1-center problem (A1CP), asks to find a point from S such that the longest weighted shortest path distance in G from it to T is minimized. This paper presents a simple FPTAS for GA1CP by traversing the edges in \(E'\) using a positive real number as step size. The FPTAS takes \(O( |E| |V| + |V|^2 \log \log |V| + \frac{1}{\epsilon } |E'| |T| {\mathcal {R}})\) time, where \({\mathcal {R}}\) is an input parameter size of the problem instance, for any given \(\epsilon > 0\). For instances with a small input parameter size \({\mathcal {R}}\), applying the FPTAS with \(\epsilon = \Theta (1)\) to the classic vertex-weighted A1CP can produce a \((1 + \Theta (1))\)-approximation in at most O(|E| |V|) time when the distance matrix is known and \(O(|E| |V| + |V|^2 \log \log |V|)\) time when the distance matrix is unknown, which are smaller than Kariv and Hakimi’s \(O(|E| |V| \log |V|)\)-time algorithm and \(O(|E| |V| \log |V| + |V|^3)\)-time algorithm, respectively.     

Exact and heuristic algorithms for solving the generalized minimum filter placement problem

We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved. We formulate a mixed-integer programming model for the problem and derive valid inequalities for this model by identifying polynomially-solvable subgraphs of the communication network. We also present three heuristics for solving the filter placement problem and evaluate their performance against the optimal solution provided by the mixed-integer programming model. The authors gratefully acknowledge the comments of two anonymous referees, whose input led to an improved version of this paper. Dr. Smith gratefully acknowledges the support of the Office of Naval Research under Grant #N00014-03-1-0510 and the Defense Advanced Research Projects Agency under Grant #N66001-01-1-8925.     

On the generalized constrained longest common subsequence problems

We investigate four variants of the longest common subsequence problem. Given two sequences X, Y and a constrained pattern P of lengths m, n, and ρ, respectively, the generalized constrained longest common subsequence (GC-LCS) problems are to find a longest common subsequence of X and Y including (or excluding) P as a subsequence (or substring). We propose new dynamic programming algorithms for solving the GC-LCS problems in O(mn ρ) time. We also consider the case where the number of constrained patterns is arbitrary.     

The solution of a generalized secretary problem via analytic expressions

Given integers \(1\le k<n\), the Gusein-Zade version of a generalized secretary problem is to choose one of the k best of n candidates for a secretary, which are interviewing in random order. The stopping rule in the selection is based only on the relative ranks of the successive arrivals. It is known that the best policy can be described by a non-decreasing sequence \((s_1, \ldots , s_k)\) of integers with \(l\le s_l<n\) for every \(1\le l\le k\), and conversely, any such a sequence determines the general structure of the best policy. We found a finite analytic expression for the probability of success when using the optimal policy with a sequence \((s_1, \ldots , s_k)\). We also study the problem of the construction of the optimal sequence, i.e. a sequence which maximizes the corresponding probability of success. We discovered finite analytic expressions which enable to calculate the elements \(s_l\) of an optimal sequence one by one, from \(l=k\) to \(l=1\). Until now, such expressions were derived separately, and only for the values \(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.     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).     

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.     

On the power domination number of the generalized Petersen graphs

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. Following a set of rules for power system monitoring, a set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S. The minimum cardinality of a power dominating set of G is the power domination number γ _p (G). In this paper, we investigate the power domination number for the generalized Petersen graphs, presenting both upper bounds for such graphs and exact results for a subfamily of generalized Petersen graphs.     

On the fractionality of the path packing problem

Given an undirected graph G=(N,E), a subset T of its nodes and an undirected graph (T,S), G and (T,S) together are often called a network. A?collection of paths in G whose end-pairs lie in S is called an integer multiflow. When these paths are allowed to have fractional weight, under the constraint that the total weight of the paths traversing a single edge does not exceed 1, we have a fractional multiflow in G. The problems of finding the maximum weight of paths with end-pairs in S over all fractional multiflows in G is called the fractional path packing problem. In 1989, A. Karzanov had defined the fractionality of the fractional path packing problem for a class of networks {G,(T,S)} as the smallest natural D such that for any network from the class, the fractional path packing problem has a solution which becomes integer-valued when multiplied by D (see A.?Karzanov in Linear Algebra Appl. 114–115:293–328, 1989). He proved that the fractional path packing problem has infinite fractionality outside a very specific class of networks, and conjectured that within this class, the fractionality does not exceed 4. A.?Karzanov also proved that the fractionality of the path packing problem is at most 8 by studying the fractionality of the dual problem. Special cases of Karzanov’s conjecture were proved in or are implied by the works of L.R.?Ford and D.R.?Fulkerson, Y.?Dinitz, T.C.?Hu, B.V.?Cherkassky, L.?Lov?sz and H.?Hirai. We prove Karzanov’s conjecture by showing that the fractionality of the path packing problem is at most 4. Our proof is stand-alone and does not rely on Karzanov’s results.