Search

An Italian dominating function on a simple undirected graph G is a function f : V ( G ) ⟶ { 0 , 1 , 2 } satisfying the condition that for each vertex v with f ( v ) = 0 , ∑ u ∈ N G ( v ) f ( u ) ≥ 2 . An Italian dominating function f on G is called a perfect Italian dominating function on G if for each vertex v with f ( v ) = 0 , ∑ u ∈ N G ( v ) f ( u ) = 2 . The weight of a function f on a graph G , denoted by w ( f ) , is the sum ∑ v ∈ V ( G ) f ( v ) . For a simple undirected graph G , Min-PIDF is the problem of finding the minimum weight of a perfect Italian dominating function on G . First, we discuss the complexity difference between Min-PIDF and the problem of finding the minimum weight of an Italian dominating function. We then establish the NP -completeness of the decision version of Min-PIDF in chordal graphs and investigate the hardness of approximation of Min-PIDF in general graphs. Finally, we present linear time algorithms for computing the minimum weight of a perfect Italian dominating function in block graphs and series-parallel graphs.

In this paper, we propose several algorithms for determining an optimal length tree-like refutation of linear feasibility in systems of Unit Two Variable Per Inequality (UTVPI) constraints. Given an infeasible UTVPI constraint system (UCS), a refutation certifies its infeasibility. The problem of finding refutations in a UCS finds applications in domains such as program verification and operations research. In general, there exist several types of refutations of feasibility in constraint systems. In this paper, we focus on a specific type of refutation called a tree-like refutation. Tree-like refutations are complete, in the sense that if a system of linear constraints is infeasible, then it must have a tree-like refutation. Associated with a refutation is its length, which equals the total number of constraints (accounting for the reuse of constraints) that are used to establish the infeasibility of the corresponding linear constraint system. Our goal in this paper is to find an optimal length tree-like refutation (OTLR) of an infeasible UCS. We describe two deterministic algorithms that find an OTLR of a UCS. If m is the number of constraints, n is the number of variables in the system, and k is the length of an OTLR, then our two algorithms run in O ( n 3 ⋅ log k ) time and O ( m ⋅ n ⋅ k ) time respectively. We also propose a true-biased, randomized algorithm for this problem. This algorithm runs in O ( m ⋅ n ⋅ log n ) time, and returns the length of an OTLR with probability ( 1 − 1 e ) . We extend our work to weighted UTVPI constraint systems (WUCS), where a positive weight is associated with each UTVPI constraint. The weight of a tree-like refutation is defined as the sum of the weights of the constraints used by the refutation. The problem of finding a minimum weight refutation in a WUCS is called the weighted optimal length tree-like refutation (WOTLR) problem and is known to be NP-hard. We propose a pseudo-polynomial time algorithm for the WOTLR problem and convert it into a fully polynomial time approximation scheme (FPTAS).

Given a bipartite graph G = ( V 1 , V 2 , E ) , a biclique of G is a complete bipartite subgraph of G , and a biclique partitioning of G is a set A ⊆ E such that the bipartite graph G ′ = ( V 1 , V 2 , A ) is a vertex-disjoint union of bicliques. The biclique partitioning problem (BPP) consists of, given a complete bipartite graph G = ( V 1 , V 2 , E ) with edge weights w e ∈ R for all e ∈ E (thus, negative weights are allowed), finding a biclique partitioning A ⊆ E of minimum weight. The bicluster editing problem (BEP) is a variant of the BPP and consists of editing a minimum number of edges of an input bipartite graph G in order to transform its edge set into a biclique partitioning. Editing an edge consists of either adding it to the graph or deleting it from the graph. In addition to the BPP and the BEP, other problems in the literature aim at finding biclique partitionings, and this motivates the study of the biclique partitioning polytope P n m of the complete bipartite graph K n m (i.e., P n m is the convex hull of the incidence vectors of the biclique partitionings of K n m ). In this paper we develop such a polyhedral study and show that ladder, bellows, and grid inequalities induce facets of P n m . Our computational results show that these inequalities are very effective in solving the BEP. In particular, they are able to improve the value of the relaxed solution by up to 20%.

The Steiner tree problem asks for a minimum weight subtree of an undirected graph spanning distinct terminal nodes. As one of the most fundamental network design problems, it has received much attention from both the mathematical programming and the algorithmic community and indeed, many integer linear programming (ILP) formulations of varying strength are known. The practical usefulness of the formulations can be enhanced with additional valid inequalities that reduce the gap between the efficiently computable continuous relaxation and the computationally difficult integer linear program. We aim to better understand the structure of these inequalities. In particular, we want to know how the inequalities can be obtained through Chvatal–Gomory cuts; a general procedure that is implemented in state-of-the-art ILP solver software. We start with the most basic ILP formulation for the Steiner tree problem and analyze how two known classes of strengthening inequalities – partition inequalities and odd-hole inequalities – can be derived systematically as Chvatal–Gomory cuts and how these inequalities themselves can be used to derive Chvatal–Gomory cuts. Along the way, we prove that the Chvatal rank of k -partition and k -odd-hole inequalities is at most k − 2 and k − 1 , respectively. In particular, this proves that k iterations of the Chvatal–Gomory cut procedure suffice to obtain a given k + 2 -partition or a given k + 1 -odd-hole inequality.

Given an assignment of real weights to the ground elements of a matroid, the min–max weight of a ground element e is the minimum, over all circuits containing e , of the maximum weight of an element in that circuit with the element e removed. We use this concept to answer the following structural questions for the minimum weight basis problem. Which elements are persistent under a given weighting (belong to all or to none of the optimal bases)? What changes of the weights are allowed while preserving optimality of optimal bases? How does the minimum weight of a basis change when the weight of a single ground element is changed, or when a ground element is contracted or deleted? Our answer to this latter question gives the tropical ( min , + , − ) analogue of Kirchhoff’s arithmetic ( + , × , ∕ ) effective conductance formula for electrical networks.

A set S of vertices is a perfect dominating set of a graph G if every vertex not in S is adjacent to exactly one vertex of S . The minimum cardinality of a perfect dominating set is the perfect domination number γ p ( G ) . A perfect Roman dominating function (PRDF) on a graph G = ( V , E ) is a function f : V → { 0 , 1 , 2 } satisfying the condition that every vertex u with f ( u ) = 0 is adjacent to exactly one vertex v for which f ( v ) = 2 . The weight of a PRDF is the sum of its function values over all vertices, and the minimum weight of a PRDF of G is the perfect Roman domination number γ R p ( G ) . Obviously, for every graph G , γ R p ( G ) ≤ 2 γ p ( G ) , and those graphs attaining the equality are called perfect Roman graphs. In this paper, we provide a characterization of perfect Roman trees.

A double Roman dominating function (DRDF) on a graph G = ( V , E ) is a function f : V ⟶ { 0 , 1 , 2 , 3 } such that every vertex v ∈ V with f ( v ) = 0 is either adjacent to a vertex u with f ( u ) = 3 or two distinct vertices x and y with f ( x ) = f ( y ) = 2 , and every vertex v ∈ V with f ( v ) = 1 is adjacent to a vertex u with f ( u ) ≥ 2 . The weight of f is the sum f ( V ) = ∑ v ∈ V f ( v ) . The minimum weight of a DRDF on G is the double Roman domination number of G , denoted by γ d R ( G ) . A graph G is a double Roman Graph if γ d R ( G ) = 3 γ ( G ) , where γ ( G ) is the domination number of G . In this paper, we first show that the decision problem associated to double Roman domination is NP-complete even when restricted to planar graphs. Then, we study the complexity issue of a problem posed in [R.A. Beeler, T.W. Haynesa and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29], and show that the problem of deciding whether a given graph is double Roman is NP-hard even when restricted to bipartite or chordal graphs. Then, we give linear algorithms that compute the domination number and the double Roman domination number of a given unicyclic graph. Finally, we give a linear algorithm that decides whether a given unicyclic graph is double Roman.

A perfect Italian dominating function of a graph $G=(V,E)$ is a function $f : V \to \{0,1,2\}$ such that for every vertex $f(v) = 0$, it holds that $\sum_{u \in N(v)} f(u) = 2$, i.e., the weight of the labels assigned by $f$ to the neighbors of $v$ is exactly two. The weight of a perfect Italian function is the sum of the weights of the vertices. The perfect Italian domination number of $G$, denoted by $\gamma^p_I(G)$, is the minimum weight of any perfect Italian dominating function of $G$. While introducing the parameter, Haynes and Henning (Discrete Appl. Math. (2019), 164--177) also proposed the problem of determining the best possible constants $c_\mathcal{G}$ such that $\gamma^p_I(G) \leq c_\mathcal{G} \times n$ for all graphs of order $n$ when $G$ is in a particular class $\mathcal{G}$ of graphs. They proved that $c_\mathcal{G} = 1$ when $\mathcal{G}$ is the class of bipartite graphs, and raised the question for planar graphs and regular graphs. We settle their question precisely for planar graphs by proving that $c_\mathcal{G} = 1$ and for cubic graphs by proving that $c_\mathcal{G} = 2/3$. For split graphs, we also show that $c_\mathcal{G} = 1$. In addition, we characterize the graphs $G$ with $\gamma^p_I(G)$ equal to 2 and 3 and determine the exact value of the parameter for several simple structured graphs. We conclude by proving that it is NP-complete to decide whether a given bipartite planar graph admits a perfect Italian dominating function of weight $k$., Comment: To appear in Discrete Applied Mathematics

Correlation immunity (CI) of Boolean functions is an important concept relevant both in the design of nonlinear combiners and for the protection against side-channel cryptanalysis to name a few applications. In this article we give further simplification of the proofs of some known characterizations of these functions, including some new results related to certain properties of the algebraic normal form of these functions. We also provide two efficient constructions of CI functions, thus extending the known construction methods. In particular, a special case of our first construction method is well suited for construction of low-weight CI functions. It is shown that Carlet and Chen conjecture (Carlet and Chen, 2018) on the minimum weight of 3-CI functions (equivalent to the existence of Hadamard matrices of order n = 4 k ) is valid for a great variety of input sizes n , thus apart from the case n = 2 k which was already proved in Carlet and Chen (2018). This further confirms that the conjecture might be correct for any input size n .

A double Roman dominating function (DRDF) on a graph G = ( V , E ) is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f ( v ) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f ( w ) = 3 , and if f ( v ) = 1 , then vertex v must have at least one neighbor w with f ( w ) ≥ 2 . The weight of a DRDF is the sum of its function values over all vertices, and the double Roman domination number γ d R ( G ) is the minimum weight of a DRDF on G . Let G be a connected graph G of order n and minimum degree at least two. With the exception of seven graphs of order at most seven, Beeler et al. (2016) observed that γ d R ( G ) ≤ 6 n 5 and posed the question whether this bound can be improved. Amjadi et al. (2018) settled this question by proving that γ d R ( G ) ≤ 8 n 7 . In this paper, we improve this bound to γ d R ( G ) ≤ 11 n 10 . Moreover, we provide an infinite family of graphs attaining this bound.

A perfect Italian dominating function on a graph G is a function f : V ( G ) → { 0 , 1 , 2 } satisfying the condition that for every vertex u with f ( u ) = 0 , the total weight of f assigned to the neighbors of u is exactly two. The weight of a perfect Italian dominating function is the sum of the weights of the vertices. The perfect Italian domination number of G , denoted γ I p ( G ) , is the minimum weight of a perfect Italian dominating function of G . We show that if G is a tree on n ≥ 3 vertices, then γ I p ( G ) ≤ 4 5 n , and for each positive integer n ≡ 0 ( mod 5 ) there exists a tree of order n for which equality holds in the bound.

Let G = ( V , E ) be a graph of order n and let B ( D ) be the set of vertices in V ∖ D that have a neighbor in the vertex set D . The differential of a vertex set D is defined as ∂ ( D ) = | B ( D ) | − | D | and the maximum value of ∂ ( D ) for any subset D of V is the differential of G , denoted by ∂ ( G ) . A Roman dominating function of G is a function f : V → { 0 , 1 , 2 } such that every vertex u with f ( u ) = 0 is adjacent to a vertex v with f ( v ) = 2 . The weight of a Roman dominating function is the value f ( V ) = ∑ u ∈ V f ( u ) . The minimum weight of a Roman dominating function of a graph G is the Roman domination number of G , written γ R ( G ) . Bermudo, et al. proved that these two parameters are complementary with respect to the order n of the graph, that is, ∂ ( G ) + γ R ( G ) = n . In this work we prove that, for any graph G with order n ≥ 9 and minimum degree two, ∂ ( G ) ≥ 3 γ ( G ) 4 , consequently, γ R ( G ) ≤ n − 3 γ ( G ) 4 , where γ ( G ) is the domination number of G . We also prove that for any graph with order n ≥ 15 , minimum degree two and without any induced tailed 5-cycle graph of seven vertices or tailed 5-cycle graph of seven vertices together with a particular edge, it is satisfied ∂ ( G ) ≥ 5 n 17 , consequently, γ R ( G ) ≤ 12 n 17 .

The class of Boolean functions, which can never occur as output of a faulty combinational circuit, is known as Impossible Class of Faulty Functions (ICFF). Despite years of research, the characterization of ICFF for a complex logic network is yet a significantly open problem. In a recent work (Das et al., 2014), a partial characterization of ICFF was done by completely enumerating a subclass of ICFFs, also called the root functions. For 2 -level AND-OR logic networks for up to 6 -variable the root functions were completely enumerated. This paper significantly extends this line of research by providing a more general framework for handling this class of functions. Both the upper and lower bounds are derived and the maximum cardinality of the weight of non-affine root functions is established. A constructive method for obtaining non-affine root functions of maximum possible weight is provided and it is shown that there are no other such functions than those obtained by our method. The direct correspondence of these functions to the independent dominating sets in the n -dimensional hypercube G n is used for establishing new results concerning the minimum weight of these functions. In particular, we give the exact value of the minimum cardinality of independent dominating set in G n for any n = 2 r − 1 , where r ≥ 2 . Since our approach is also constructive, we essentially efficiently solve this problem for any n = 2 r − 1 , where r ≥ 2 , and our results conform to the observation of Harary and Livingston (2010). Finally, the problem of classifying and enumerating root functions is addressed leading to some non-trivial lower bounds on their number, though the problem appears to be hard and further research in this direction is needed.

We study a variant of the classical transportation problem in which suppliers with limited capacities have a choice of which demands (markets) to satisfy. We refer to this problem as the transportation problem with market choice (TPMC). While the classical transportation problem is known to be strongly polynomial-time solvable, we show that its market choice counterpart is strongly NP-complete. For the special case when all potential demands are no greater than two, we show that the problem reduces in polynomial time to minimum weight perfect matching in a general graph, and thus can be solved in polynomial time. We give valid inequalities and coefficient update schemes for general mixed-integer sets that are substructures of TPMC. Finally, we give conditions under which these inequalities define facets, and report our preliminary computational experiments with using them in a branch-and-cut algorithm.

Given an edge-weighted graph G and a list of source–sink pairs of terminal vertices of G, the minimum multicut problem consists in selecting a minimum weight set of edges of G whose removal leaves no path from the ith source to the ith sink, for each i. Few tractable special cases are known for this problem. In this paper, we give a simple polynomial-time algorithm solving it in undirected planar graphs where (I) all the terminals lie on the outer face and (II) there is a bounded number of terminals.

Let G be a graph and let k be a positive integer. A subset D of the vertex set of G is a k-dominating set if every vertex not in D has at least k neighbors in D. The k-domination [email protected]"k(G) is the minimum cardinality among the k-dominating sets of G. A Romank-dominating function on G is a function f:V(G)@?{0,1,2} such that every vertex u for which f(u)=0 is adjacent to at least k vertices v"1,v"2,...,v"k with f(v"i)=2 for i=1,2,...,k. The weight of a Roman k-dominating function is the value f(V(G))[email protected]?"v"@?"V"("G")f(v). The minimum weight of a Roman k-dominating function on a graph G is called the Romank-domination [email protected]"k"R(G). In 2007, Rautenbach and Volkmann [D. Rautenbach, L. Volkmann, New bounds on the k-domination number and the k-tuple domination number, Appl. Math. Lett. 20 (2007) 98-102] gave an upper bound for the k-domination number @c"k(G). Using again the probabilistic method, we achieve better bounds for this parameter and prove new bounds for the k-Roman domination number @c"k"R(G). Moreover, we generalize known inequalities for the case k=1 [V.I. Arnautov, Estimations of the external stability number of a graph by means of the minimal degree of vertices, Prikl. Mat. Programm. 11 (1974) 3-8 (in Russian); C. Payan, Sur le nombre d'absorption d'un graphe simple, Cahiers Centre Etudes Recherche Oper. 17 (1975) 307-317; E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-22].

A Roman dominating function of a graph G=(V,E) is a function f:V→{0,1,2} such that every vertex x with f(x)=0 is adjacent to at least one vertex y with f(y)=2. The weight of a Roman dominating function is defined to be f(V)=∑x∈Vf(x), and the minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. In this paper we first answer an open question mentioned in [E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22] by showing that the Roman domination number of an interval graph can be computed in linear time. We then show that the Roman domination number of a cograph (and a graph with bounded cliquewidth) can be computed in linear time. As a by-product, we give a characterization of Roman cographs. It leads to a linear-time algorithm for recognizing Roman cographs. Finally, we show that there are polynomial-time algorithms for computing the Roman domination numbers of AT-free graphs and graphs with a d-octopus.

A standard Quadratic Programming problem (StQP) consists in minimizing a (nonconvex) quadratic form over the standard simplex. For solving a StQP we present an exact and a heuristic algorithm, that are based on new theoretical results for quadratic and convex optimization problems. With these results a StQP is reduced to a constrained nonlinear minimum weight clique problem in an associated graph. Such a clique problem, which does not seem to have been studied before, is then solved with an exact and a heuristic algorithm. Some computational experience shows that our algorithms are able to solve StQP problems of at least one order of magnitude larger than those reported in the literature.

Given an edge- or vertex-weighted graph or digraph and a list of source-sink pairs, the minimum multicut problem consists in selecting a minimum weight set of edges or vertices whose removal leaves no path from each source to the corresponding sink. This is a classical NP-hard problem, and we show that the edge version becomes tractable in bounded tree-width graphs if the number of source-sink pairs is fixed, but remains NP-hard in directed acyclic graphs and APX-hard in bounded tree-width and bounded degree unweighted digraphs. The vertex version, although tractable in trees, is proved to be NP-hard in unweighted cacti of bounded degree and bounded path-width.

The performance of a linear t-error correcting code over a q-ary symmetric memoryless channel with symbol error probability ε is characterized by the probability that a transmission error will remain undetected. This probability is a function of ε involving the code weight distribution and the weight distribution of the cosets of minimum weight at most t. When the undetectable error probability is an increasing function of ε, the code is called t-proper.The paper presents sufficient conditions for t-properness and a list of codes known to be proper, many of which have been studied by these sufficient conditions. Special attention is paid to error detecting codes of interest in modern communication.

We consider the following complete optimal stars-clustering-tree problem: Given a complete graph G=(V,E) with a weight on every edge and a collection of subsets of V, we want to find a minimum weight spanning tree T such that each subset of the vertices in the collection induces a complete star in T. One motivation for this problem is to construct a minimum cost (weight) communication tree network for a collection of (not necessarily disjoint) groups of customers such that each group induces a complete star. As a result the network will provide a “group broadcast” property, “group fault tolerance” and “group privacy”. We present another motivation from database systems with replications. For the case where the intersection graph of the subsets is connected we present a structure theorem that describes all feasible solutions. Based on it we provide a polynomial algorithm for finding an optimal solution. For the case where each subset induces a complete star minus at most k leaves we prove that the problem is NP-hard.

The set cover problem is that of computing a minimum weight subfamily F′, given a family F of weighted subsets of a base set U, such that every element of U is covered by some subset in F′. The k-set cover problem is a variant in which every subset is of size at most k. It has been long known that the problem can be approximated within a factor of H(k)=∑i=1k(1/i) by the greedy heuristic, but no better bound has been shown except for the case of unweighted subsets. In this paper we consider approximation of a restricted version of the weighted 3-set cover problem, as a first step towards better approximation of general k-set cover problem, where any two distinct subset costs differ by a multiplicative factor of at least 2. It will be shown, via LP duality, that an improved approximation bound of H(3)-1/6 can be attained, when the greedy heuristic is suitably modified for this case. A key to our algorithm design and analysis is the Gallai–Edmonds structure theorem for maximum matchings.

We investigate the approximability of minimum and maximum linear ordering problems (MIN-LOP and MAX-LOP) and related feedback set problems such as maximum weight acyclic subdiagraph (MAX-W-SUBDAG), minimum weight feedback arc/vertex set (MIN-W-FAS/ MIN-W-FVS) and a generalization of the latter called MIN-Subset-FAS/MIN-Subset-FVS. MAX-LOP and the other problems have been studied by many researchers but, though MINLOP arises in many practical contexts, it appears that it has not been studied before. In this paper, we first note that these minimization (respectively, maximization) problems are equivalent with respect to strict reduction and so have the same approximability properties. While MAX-LOP is APX-complete, MIN-LOP is only APX-hard. We conjecture that MIN-LOP is not in APX, unless P = NP. We obtain a result connecting extreme points of linear ordering polytope with approximability of MIN-LOP via LP-relaxation which seems to suggest that constant factor approximability of MIN-LOP may not be obtainable via this method. We also prove that (a) MIN-Subset-FAS cannot be approximated within a factor (1 - e) log n, for any e > 0, unless NP ⊂ DTIME(n log log n), and (b) MIN-W-k-FAS, a generalization of MIN-LOP, is NPO-complete. We then show that Δt-MIN-LOP (respectively, Δt-MAX-LOP), in which the weight matrix satisfies a parametrized version of a stronger form of triangle inequality, with parameter t ∈ (0,2], is approximable within a factor (2 + t)/2t (respectively, 4/(2 + t)). We also show that these restricted versions are in PO iff t = 2 and are not in PTAS for t ∈ (0, 2), unless P = NP.

In Steiner tree game associated with a graph G=(V,E), players consist of a subset N⊆V of nodes. The characteristic function value of a subset S⊆N of the players is the minimum weight of a Steiner tree that spans S. We show that it is NP-hard to determine whether a Steiner tree game is totally balanced, i.e., cores for all its subgames are non-empty. In addition, the NP-hardness result is also proven for deciding whether the core is non-empty, or whether an imputation is a member of the core.

This paper deals with the problem of constructing Steiner trees of minimum weight with diameter bounded by d, spanning a given set of ν vertices in a graph. Exact solutions or logarithmic ratio approximation algorithms were known before for the cases of d⩽5. Here we give a polynomial-time approximation algorithm of ratio O(logν) for constant d, which is asymptotically optimal unless P=NP, and an algorithm of ratio O(νε), for any fixed 0

Let G = ( V , E ) be a graph with positive edge weights and let V '⊆ V . The min V 1 -cut problem is to find a minimum weight set E '⊆ E such that no two nodes of V ' occur in the same component of G' = (V, E E' ) . Our main results are two new structural theorems for optimal solutions to the min V '-cut problem when G is planar. The first theorem establishes for the first time a close connection between the planar min V '-cut problem and the well-known “Gomory-Hu” cut collections. The second theorem establishes a connection between the planar min V '-cut problem and a particular matroid. Each theorem results in a simple algorithm for the planar min V '-cut problem. The first algorithm is based upon the most efficient previous algorithm for this problem (due to Dahlhaus et al.) and achieves a lower time complexity.

Minimizing the number of precedence constrained, unit-time tardy jobs is strongly NP-hard on a single machine. We study a special case of the problem where a job is tardy if it is finished more than a fixed K time units after its earliest possible completion time under the precedence constraints. We prove that the problem remains strongly NP-hard even with these special due dates. We also present polynomial time solutions for the weighted version of the problem if the precedence constraints are out-forests or interval orders. In the process, we also present a polynomial time solution for a special case of the minimum weight hitting set problem.

A three-valued function f defined on the vertices of a graph G = (V, E), f : V → {−1, 0, 1}, is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is, for every v ϵ V, f(N[v]⩾1), where N[v] consists of v and every vertex adjacent to v. The weight of a minus dominating function is f(V) = ∑ f(v), over all vertices v ϵ V. The minus domination number of a graph G, denoted γ−(G), equals the minimum weight of a minus dominating function of G. The upper minus domination number of a graph G, denoted Γ−(G), equals the maximum weight of a minimal minus dominating function of G. In this paper we present a variety of algorithmic results. We show that the decision problem corresponding to the problem of computing γ− (respectively, Γ−) is NP-complete even when restricted to bipartite graphs or chordal graphs. We also present a linear time algorithm for finding a minimum minus dominating function in an arbitrary tree.

Given a graph G = (V, E), a cut in G that partitions V into two sets with right perpendicular 1/2V left perpendicular and inverted right perpendicular 1/2V inverted left perpendicular nodes is called an equicut. Suppose that there are weights assigned to the edges in E. The problem of finding a minimum weight equicut in G is known to be NP-hard. The equicut polytope is defined as the convex hull of the incidence vectors of the equicuts in G, In this paper we describe several new classes of facets for the equicut polytope; they arise as various generalizations of an inequality based on a cycle introduced by Conforti et al. (1990). Most of our inequalities have the interesting feature that their support graphs are planar but for some of them both planarity and connectivity properties are lost. Finally we show how our results can be applied to obtain new classes of facets for the cut polytope.

We present a generalization of the Steiner problem in a directed graph. Given nonnegative weights on the arcs, the problem is to find a minimum weight subset F of the arc set such that the subgraph induced by F contains a given number of arc-disjoint directed paths from a certain root node to each given terminal node. Some applications of the problem are discussed and properties of associated polyhedra are studied. Results from a cutting plane algorithm are reported.

In this paper we continue the investigation of a family of linear block codes based on the geometry of the Grassmann variety G(k,n) of k-planes in the n-dimensional vector space over Z2. These codes, denoted by C(k,n), have as their generator matrix the nk× |G(k,n)| matrix whose columns are the Plücker coordinates of the points of G(k,n).The major results established herein are: •The minimum weight of C(k,n) is equal to 2k(n−k).•The number of codewords in C(k,n) of minimal weight is equal to |G(k,n)|.•The minimal weight codewords of C(k,n) are the affine charts of G(k,n).

We study the structure of the minimum weight base of a matroid M = (E, I) the order of whose element set E is determined by the interleaving of two ordered subsets of E, R and W. The results imply an interesting application in economics, and are useful for the rapid recomputation of the minimum weight base when the order of E is successively modified by changing the interleaving of R and W. As a special case of the main result, the following parametric problem is efficiently solved: For M = (E, I) a matroid with weighted element set E, and R a subset of E, find for all feasible values of q, the minimum weight base of M containing exactly q elements of R. This parametric problem is a weighted matroid intersection problem and hence can be solved by known matroid intersection algorithms. The approach in this paper is different, and vastly improves the efficiency of the solution, as well as determining structural information about the bases.

The well known blossom-algorithm for solving minimum weight perfect matching problems makes use of the optimality criteria arising from LP-duality and complementary slackness. But these instruments seem to fail when such a matching problem is considered with a different objective function as for instance the bottleneck objective which is also relevant in practice. Such a dilemma occurs for all those combinatorial optimization problems with algorithms based on Linear Programming. Therefore we present a rarely combinatorially motivated approach in this paper.

The quasi-greedy algorithm , as proposed by Glover and Klingman [8], efficiently solves minimum weight spanning tree problems with a fixed (or bounded) number of edges incident to a specified vertex. As observed in [8], the results carry through to general matroid problems (where a base contains a bounded number of elements from a specified set). We extend this work to provide an efficient 2- quasi-greedy algorithm where a minimum weight base is constrained to have a fixed number of elements from two disjoint sets. Our main results show that optimal bases for adjacent states may not themselves be adjacent. However, optimal solutions for adjacent states may be identified solely from information available in the current base, yielding a method whose efficiency rivals that of the quasi-greedy method. We also give theorems making it possible to jump over certain adjacent states, further increasing efficiency.

We consider the problem of finding a strictly fundamental cycle basis of minimum weight in the cycle space associated with an undirected connected graph G , where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Several heuristics have been proposed to tackle this NP-hard problem, which has some interesting applications. In this paper we show that this problem is APX-hard, even when restricted to unweighted graphs, and hence does not admit a polynomial-time approximation scheme, unless P = NP . Using a recent result on the approximability of lower-stretch spanning trees (Elkin et?al. (2005)?7]), we obtain that the problem is approximable within O ( log 2 n log log n ) for arbitrary graphs. We obtain tighter approximability bounds for dense graphs. In particular, the problem restricted to complete graphs admits a polynomial-time approximation scheme.

In the group Steiner problem we are given an edge-weighted graph G = (V, E, w) and m subsets of vertices {gi}i=1m. Each subset gi is called a group and the vertices in ∪igi are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group.We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant e > 0, our algorithm gives an O((log Σi|gi|1+eċ log m) approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of O(log |V|) in the approximation ratio, where |V| is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of O(log(maxi|gi|)ċlog m) provided by the LP based approaches.

The weight of a code is the number of coordinate positions where not all codewords are zero. The rth minimum weight dr is the least weight of an r-dimensional subcode. Wei and Yang conjectured a formula for the minimum weights of some product codes, and this conjecture has recently been proved in two different ways. In this self-contained paper, we give a further generalisation, with a new proof which also covers the old results.

We consider a partitioning problem, defined for bipartite and 2-connected plane graphs, where each node should be covered exactly once by either an edge or by a cycle surrounding a face. The objective is to maximize the number of face boundaries in the partition. This problem arises in mathematical chemistry in the computation of the Clar number of hexagonal systems. In this paper we establish that a certain minimum weight covering problem of faces by cuts is a strong dual of the partitioning problem. Our proof relies on network flow and linear programming duality arguments, and settles a conjecture formulated by Hansen and Zheng in the context of hexagonal systems [P. Hansen, M. Zheng, Upper Bounds for the Clar Number of Benzenoid Hydrocarbons, Journal of the Chemical Society, Faraday Transactions 88 (1992) 1621–1625].

Total graphs of trees were proved strongly chordal by Martin Farber. We give a new proof of this fact by directly constructing a strong elimination ordering. Our method can be implemented to run in linear time. As an application, we give a new linear algorithm for the minimum weight total dominating set problem for trees.