A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs

Journal of Combinatorial Optimization - Let $$G = (V, E, w)$$ be an undirected connected edge-weighted graph, where V is the n-vertices set, E is the m-edges set, and $$w: E rightarrow mathbb...     

Paired-domination in generalized claw-free graphs

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199–206). A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. If G does not contain a graph F as an induced subgraph, then G is said to be F-free. Haynes and Slater (Networks 32 (1998) 199–206) showed that if G is a connected graph of order , then and this bound is sharp for graphs of arbitrarily large order. Every graph is -free for some integer a ≥ 0. We show that for every integer a ≥ 0, if G is a connected -free graph of order n ≥ 2, then with infinitely many extremal graphs.     

An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration

This paper consider m uniform (parallel) machine scheduling with linear deterioration to minimize the makespan. In an uniform machine environment, all machines have different processing speeds. Linear deterioration means that job’s actual processing time is a linear increasing function on its execution starting time. We propose a fully polynomial-time approximation scheme (FPTAS) to show the problem is NP-hard in the ordinary sense.     

Algorithms for the maximum k-club problem in graphs

Given a simple undirected graph G, a k-club is a subset of vertices inducing a subgraph of diameter at most k. The maximum k-club problem (MkCP) is to find a k-club of maximum cardinality in G. These structures, originally introduced to model cohesive subgroups in social network analysis, are of interest in network-based data mining and clustering applications. The maximum k-club problem is NP-hard, moreover, determining whether a given k-club is maximal (by inclusion) is NP-hard as well. This paper first provides a sufficient condition for testing maximality of a given k-club. Then it proceeds to develop a variable neighborhood search (VNS) heuristic and an exact algorithm for MkCP that uses the VNS solution as a lower bound. Computational experiments with test instances available in the literature show that the proposed algorithms are very effective on sparse instances and outperform the existing methods on most dense graphs from the testbed.     

The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance

This paper addresses the problem of modifying the edge lengths of a tree in minimum total cost such that a prespecified vertex becomes the 1-center of the perturbed tree. This problem is called the inverse 1-center problem on trees. We focus on the problem under Chebyshev norm and Hamming distance. From special properties of the objective functions, we can develop combinatorial algorithms to solve the problem. Precisely, if there does not exist any vertex coinciding with the prespecified vertex during the modification of edge lengths, the problem under Chebyshev norm or bottleneck Hamming distance is solvable in \(O(n\log n)\) time, where \(n+1\) is the number of vertices of the tree. Dropping this condition, the problem can be solved in \(O(n^{2})\) time.     

A linear-time algorithm for clique-coloring problem in circular-arc graphs

A maximal clique of G is a clique not properly contained in any other clique. A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no maximal clique with at least two vertices is monochromatic. The smallest integer k admitting a k-clique-coloring of G is called clique-coloring number of G. Cerioli and Korenchendler (Electron Notes Discret Math 35:287–292, 2009) showed that there is a polynomial-time algorithm to solve the clique-coloring problem in circular-arc graphs and asked whether there exists a linear-time algorithm to find an optimal clique-coloring in circular-arc graphs or not. In this paper we present a linear-time algorithm of the optimal clique-coloring in circular-arc graphs.     

The density maximization problem in graphs

We consider a framework for bi-objective network construction problems where one objective is to be maximized while the other is to be minimized. Given a host graph G=(V,E) with edge weights w _e ∈? and edge lengths ? _e ∈? for e∈E we define the density of a pattern subgraph H=(V′,E′)?G as the ratio ?(H)=∑ _e∈E′ w _e /∑ _e∈E′ ? _e . We consider the problem of computing a maximum density pattern H under various additional constraints. In doing so, we compute a single Pareto-optimal solution with the best weight per cost ratio subject to additional constraints further narrowing down feasible solutions for the underlying bi-objective network construction problem. First, we consider the problem of computing a maximum density pattern with weight at least W and length at most L in a host G. We call this problem the biconstrained density maximization problem. This problem can be interpreted in terms of maximizing the return on investment for network construction problems in the presence of a limited budget and a target profit. We consider this problem for different classes of hosts and patterns. We show that it is NP-hard, even if the host has treewidth 2 and the pattern is a path. However, it can be solved in pseudo-polynomial linear time if the host has bounded treewidth and the pattern is a graph from a given minor-closed family of graphs. Finally, we present an FPTAS for a relaxation of the density maximization problem, in which we are allowed to violate the upper bound on the length at the cost of some penalty. Second, we consider the maximum density subgraph problem under structural constraints on the vertex set that is used by the patterns. While a maximum density perfect matching can be computed efficiently in general graphs, the maximum density Steiner-subgraph problem, which requires a subset of the vertices in any feasible solution, is NP-hard and unlikely to admit a constant-factor approximation. When parameterized by the number of vertices of the pattern, this problem is W[1]-hard in general graphs. On the other hand, it is FPT on planar graphs if there is no constraint on the pattern and on general graphs if the pattern is a path.     

Extremal coloring for the anti-Ramsey problem of matchings in complete graphs

Given a graph G, the anti-Ramsey number \(AR(K_n,G)\) is defined to be the maximum number of colors in an edge-coloring of \(K_n\) which does not contain any rainbow G (i.e., all the edges of G have distinct colors). The anti-Ramsey number was introduced by Erd?s et al. (Infinite and finite sets, pp 657–665, 1973) and so far it has been determined for several special graph classes. Another related interesting problem posed by Erd?s et al. is the uniqueness of the extremal coloring for the anti-Ramsey number. Contrary to the anti-Ramsey number, there are few results about the extremal coloring. In this paper, we show the uniqueness of such extremal coloring for the anti-Ramsey number of matchings in the complete graph.     

A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date

We address the single machine scheduling problem to minimize the total weighted earliness and tardiness about a nonrestrictive common due date. This is a basic problem with applications to the just-in-time manufacturing. The problem is linked to a Boolean programming problem with a quadratic objective function, known as the half-product. An approach to developing a fast fully polynomial-time approximation scheme (FPTAS) for the problem is identified and implemented. The running time matches the best known running time for an FPTAS for minimizing a half-product with no additive constant.     

The matching extension problem in general graphs is co-NP-complete

A simple connected graph G with 2n vertices is said to be k-extendable for an integer k with \(0<k<n\) if G contains a perfect matching and every matching of cardinality k in G is a subset of some perfect matching. Lakhal and Litzler (Inf Process Lett 65(1):11–16, 1998) discovered a polynomial algorithm that decides whether a bipartite graph is k-extendable. For general graphs, however, it has been an open problem whether there exists a polynomial algorithm. The new result presented in this paper is that the extendability problem is co-NP-complete.     

On the generalized multiway cut in trees problem

Given a tree $T = (V, E)$ with $n$ vertices and a collection of terminal sets $D = \{S_1, S_2, \ldots , S_c\}$ , where each $S_i$ is a subset of $V$ and $c$ is a constant, the generalized multiway cut in trees problem (GMWC(T)) asks to find a minimum size edge subset $E^{\prime } \subseteq E$ such that its removal from the tree separates all terminals in $S_i$ from each other for each terminal set $S_i$ . The GMWC(T) problem is a natural generalization of the classical multiway cut in trees problem, and has an implicit relation to the Densest $k$ -Subgraph problem. In this paper, we show that the GMWC(T) problem is fixed-parameter tractable by giving an $O(n^2 + 2^k)$ time algorithm, where $k$ is the size of an optimal solution, and the GMWC(T) problem is polynomial time solvable when the problem is restricted in paths.We also discuss some heuristics for the GMWC(T) problem     

Partial degree bounded edge pacing problem for graphs and $$$$-uniform hypergraphs

Given a graph \(G=(V,E)\) and a non-negative integer \(c_u\) for each \(u\in V\), partial degree bounded edge packing problem is to find a subgraph \(G^{\prime }=(V,E^{\prime })\) with maximum \(|E^{\prime }|\) such that for each edge \((u,v)\in E^{\prime }\), either \(deg_{G^{\prime }}(u)\le c_u\) or \(deg_{G^{\prime }}(v)\le c_v\). The problem has been shown to be NP-hard even for uniform degree constraint (i.e., all \(c_u\) being equal). In this work we study the general degree constraint case (arbitrary degree constraint for each vertex) and present two combinatorial approximation algorithms with approximation factors \(4\) and \(2\). Then we give a \(\log _2 n\) approximation algorithm for edge-weighted version of the problem and an efficient exact algorithm for edge-weighted trees with time complexity \(O(n\log n)\). We also consider a generalization of this problem to \(k\)-uniform hypergraphs and present a constant factor approximation algorithm based on linear programming using Lagrangian relaxation.     

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.     

Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem

A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over of the -th entry of the first vector plus the sum of the first k – + 1 entries of the second vector. For this problem a new algorithm with O(n log n) running time is presented thus improving upon the straightforward O(n ²) time bound.The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme (FPTAS) for the classical 0–1 knapsack problem by the same authors.     

An efficient algorithm for distance total domination in block graphs

The \(k\)-distance total domination problem is to find a minimum vertex set \(D\) of a graph such that every vertex of the graph is within distance \(k\) from some vertex of \(D\) other than itself, where \(k\) is a fixed positive integer. In the present paper, by using a labeling method, we design an efficient algorithm for solving the \(k\)-distance total domination problem on block graphs, a superclass of trees.     

An integer programming framework for critical elements detection in graphs

This study presents an integer programming framework for minimizing the connectivity and cohesiveness properties of a given graph by removing nodes and edges subject to a joint budgetary constraint. The connectivity and cohesiveness metrics are assumed to be general functions of sizes of the remaining connected components and node degrees, respectively. We demonstrate that our approach encompasses, as special cases (possibly, under some mild conditions), several other models existing in the literature, including minimization of the total number of connected node pairs, minimization of the largest connected component size, and maximization of the number of connected components. We discuss computational complexity issues, derive linear mixed integer programming (MIP) formulations, and describe additional modeling enhancements aimed at improving the performance of MIP solvers. We also conduct extensive computational experiments with real-life and randomly generated network instances under various settings that reveal interesting insights and demonstrate advantages and limitations of the proposed framework.     

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.     

An efficient generalized network-simplex-based algorithm for manufacturing network flows

Fang and Qi (Optim. Methods Softw. 18:143–165, 2003) introduced a new generalized network flow model called manufacturing network flow model for manufacturing process modeling. A key distinguishing feature of such models is the assembling of component raw-materials, in a given proportion, into an end-product. This assembling operation cannot be modeled using usual generalized networks (which allow gains and losses in flows), or using multi-commodity networks (which allow flows of multiple commodity types on a single arc). The authors developed a network-simplex-based algorithm to solve a minimum cost flow problem formulated on such a generalized network and indicated systems of linear equations that need to be solved during the course of the network-simplex-based solution procedure. In this paper, it is first shown how various steps of the network-simplex-based solution procedure can be performed efficiently using appropriate data structures. Further, it is also shown how the resulting system of linear equations can be solved directly on the generalized network.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.