On the complexity of the multicut problem in bounded tree-width graphs and digraphs

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.     

Sloane's box stacking problem

Recently, Sloane suggested the following problem: We are given n boxes, labeled 1,2,…,n. For i=1,…,n, box i weighs (m-1)i grams (where m?2 is a fixed integer) and box i can support a total weight of i grams. What is the number of different ways to build a single stack of boxes in which no box will be squashed by the weight of the boxes above it? Prior to this generalized problem, Sloane and Sellers solved the case m=2. More recently, Andrews and Sellers solved the case m?3. In this note we give new and simple proofs of the results of Sloane and Sellers and of Andrews and Sellers, using a known connection with m-ary partitions.     

A group-based search for solutions of the n-queens problem

The n-queens problem is a well-known problem in mathematics, yet a full search for n-queens solutions has been tackled until now using only simple algorithms (with the exception of the Rivin-Zabih algorithm). In this article, we discuss optimizations that mainly rely on group actions on the set of n-queens solutions. Most of our arguments deal with the case of toroidal queens; at the end, the application to the regular n-queens problem is discussed, and also the Rivin-Zabih algorithm.     

Complexity results on restricted instances of a paint shop problem for words

We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of its letters such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters.This is a special case of the paint shop problem for words, which was previously shown to be NP-complete. We show that this special case is also NP-complete and even APX-hard. Furthermore, derive lower bounds for this problem and discuss a transformation into matroid theory enabling us to solve some specific instances within polynomial time.     

Determining tension parameters in rational gamma-spline interpolation

Inspired by the classic γ-spline, we propose a method for constructing a G² rational γ-spline curve that interpolates a given set of distinct ordered data-points (planar or spatial). The only input of our method is just these data-points. We also present a procedure to solve the key problem of determining the tension parameters γ_i which are computed in terms of exponential functions that determine the eccentricities of the common conic osculants at the junction points while keeping in geometrical agreement with data-points. This allows the resulting curve to be modified in the close vicinity of each data-point.     

The generalized nonlinear initial-boundary Riemann problem for linearly degenerate quasilinear hyperbolic systems of conservation laws

This work is a continuation of our previous work, in the present paper we study the generalized nonlinear initial-boundary Riemann problem with small BV data for linearly degenerate quasilinear hyperbolic systems of conservation laws with nonlinear boundary conditions in a half space . We prove the global existence and uniqueness of piecewise C¹ solution containing only contact discontinuities to a class of the generalized nonlinear initial-boundary Riemann problem, which can be regarded as a small BV perturbation of the corresponding nonlinear initial-boundary Riemann problem, for general n×n linearly degenerate quasilinear hyperbolic system of conservation laws; moreover, this solution has a global structure similar to the one of the self-similar solution to the corresponding nonlinear initial-boundary Riemann problem. Some applications to quasilinear hyperbolic systems of conservation laws arising in the string theory and high energy physics are also given.     

On the complexity of crossings in permutations

We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π^∗ which minimizes the number of crossings. In voting and social science theory this is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ distance. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for a series of bipartite graphs or for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. We contribute the max version of the crossing minimization problem, which attempts to minimize the discrimination against any permutation. As our results, we correct the construction from [C. Dwork, R. Kumar, M. Noar, D. Sivakumar, Rank aggregation methods for the Web, Proc. WWW10 (2001) 613-622] and prove the NP-hardness of the common crossing minimization problem for k=4 permutations. Then we establish a 2−2/k-approximation, improving the previous factor of 2. The max version is shown NP-hard for every k≥4, and there is a 2-approximation. Both approximations are optimal, if the common permutation is selected from the given ones. For two permutations crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Existence of distributional solutions of a closed Dirichlet problem for an elliptic-hyperbolic equation

The closed Dirichlet problem for an elliptic-hyperbolic equation arising in linearizing the Monge-Ampère type equation is shown to admit a distributional solution by using an a-b-c integral method.     

Well-posedness of a class of perturbed optimization problems in Banach spaces

Let X be a Banach space and Z a nonempty subset of X. Let J:Z→R be a lower semicontinuous function bounded from below and p?1. This paper is concerned with the perturbed optimization problem of finding z₀∈Z such that ‖x−z₀p^‖+J(z₀)=infz∈Z{‖x−zp^‖+J(z)}, which is denoted by minJ(x,Z). The notions of the J-strictly convex with respect to Z and of the Kadec with respect to Z are introduced and used in the present paper. It is proved that if X is a Kadec Banach space with respect to Z and Z is a closed relatively boundedly weakly compact subset, then the set of all x∈X for which every minimizing sequence of the problem minJ(x,Z) has a converging subsequence is a dense Gδ-subset of X?Z₀, where Z₀ is the set of all points z∈Z such that z is a solution of the problem minJ(z,Z). If additionally p>1 and X is J-strictly convex with respect to Z, then the set of all x∈X for which the problem minJ(x,Z) is well-posed is a dense Gδ-subset of X?Z₀.     

Solutions of nonlinear evolution inclusions

In this paper, the solution of the nonlinear evolution inclusion problem of the form u^′(t)+B(t,u(t))∋f(t) is studied. In this problem, the operators are of type (M) or type (S₊), which are different from those of pseudo-monotone operators that had been studied by many authors. At the same time, we study the perturbation problem. In fact, many kinds of evolution equations can be generalized by this problem. The former results are improved and generalized by our conclusions, and we will give more applications.     

Entropy solutions for a doubly nonlinear elliptic problem with variable exponent

We study the boundary value problem in Ω, u=0 on ∂Ω, where Ω is a smooth bounded domain in RN (N?3) and is a p(x)-Laplace type operator with p(.):Ω→[1,+∞) a measurable function and b a continuous and nondecreasing function from R→R. We prove the existence and uniqueness of an entropy solution for L¹-data f.     

Binary relations and reduced hypergroups

Different partial hypergroupoids are associated with binary relations defined on a set H. In this paper we find sufficient and necessary conditions for these hypergroupoids in order to be reduced hypergroups. Given two binary relations ρ and σ on H we investigate when the hypergroups associated with the relations ρ∩σ, ρ∪σ and ρσ are reduced. We also determine when the cartesian product of two hypergroupoids associated with a binary relation is a reduced hypergroup.     

The multiple originator broadcasting problem in graphs

Given a graph G and a vertex subset S of V(G), the broadcasting time with respect toS, denoted by b(G,S), is the minimum broadcasting time when using S as the broadcasting set. And the k-broadcasting number, denoted by b_k(G), is defined by b_k(G)=min{b(G,S)|S⊆V(G),|S|=k}.Given a graph G and two vertex subsets S, S^′ of V(G), define , d(S,S^′)=min{d(u,v)|u∈S, v∈S^′}, and for all v∈V(G). For all k, 1?k?|V(G)|, the k-radius of G, denoted by r_k(G), is defined as r_k(G)=min{d(G,S)|S⊆V(G), |S|=k}.In this paper, we study the relation between the k-radius and the k-broadcasting numbers of graphs. We also give the 2-radius and the 2-broadcasting numbers of the grid graphs, and the k-broadcasting numbers of the complete n-partite graphs and the hypercubes.     

Existence and porosity for a class of perturbed optimization problems in Banach spaces

Let X be a Banach space and Z a nonempty closed subset of X. Let be an upper semicontinuous function bounded from above. This paper is concerned with the perturbed optimization problem supz∈Z{J(z)+‖x−z‖}, which is denoted by (x,J)-sup. We shall prove in the present paper that if Z is a closed boundedly relatively weakly compact nonempty subset, then the set of all x∈X for which the problem (x,J)-sup has a solution is a dense Gδ-subset of X. In the case when X is uniformly convex and J is bounded, we will show that the set of all points x in X for which there does not exist z₀∈Z such that J(z₀)+‖x−z₀‖=supz∈Z{J(z)+‖x−z‖} is a σ-porous subset of X and the set of all points x∈X?Z⁰ such that there exists a maximizing sequence of the problem (x,J)-sup which has no convergent subsequence is a σ-porous subset of X?Z⁰, where Z⁰ denotes the set of all z∈Z such that z is in the solution set of (z,J)-sup.     

Locating the peaks of least-energy solutions to a quasilinear elliptic Neumann problem, Part II

We continue our work (Y. Li, C. Zhao, Locating the peaks of least-energy solutions to a quasilinear elliptic Neumann problem, J. Math. Anal. Appl. 336 (2007) 1368-1383) to study the shape of least-energy solutions to the quasilinear problem ε^mΔ_mu−u^m−1+f(u)=0 with homogeneous Neumann boundary condition. In this paper we focus on the case 1<m<2 as a complement to our previous work on the case m≥2. We use an intrinsic variation method to show that as the case m≥2, when ε→0⁺, the global maximum point P_ε of least-energy solutions goes to a point on the boundary ∂Ω at a rate of o(ε) and this point on the boundary approaches a global maximum point of mean curvature of ∂Ω.     

An extremal problem on non-full colorable graphs

For a given graph G of order n, a k-L(2,1)-labelling is defined as a function f:V(G)→{0,1,2,…k} such that |f(u)-f(v)|?2 when d_G(u,v)=1 and |f(u)-f(v)|?1 when d_G(u,v)=2. The L(2,1)-labelling number of G, denoted by λ(G), is the smallest number k such that G has a k-L(2,1)-labelling. The hole index ρ(G) of G is the minimum number of integers not used in a λ(G)-L(2,1)-labelling of G. We say G is full-colorable if ρ(G)=0; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with λ(G)=2m and ρ(G)=m, where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole L(2,1)-colorings, Discrete Appl. Math. 130 (2003) 513-519].     

Super-vertex-antimagic total labelings of disconnected graphs

Let G=(V,E) be a finite, simple and non-empty (p,q)-graph of order p and size q. An (a,d)-vertex-antimagic total labeling is a bijection f from V(G)∪E(G) onto the set of consecutive integers 1,2,…,p+q, such that the vertex-weights form an arithmetic progression with the initial term a and the common difference d, where the vertex-weight of x is the sum of values f(xy) assigned to all edges xy incident to vertex x together with the value assigned to x itself, i.e. f(x). Such a labeling is called super if the smallest possible labels appear on the vertices.In this paper, we will study the properties of such labelings and examine their existence for disconnected graphs.     

Least and most colored bases

Consider a matroid M=(E,B), where B denotes the family of bases of M, and assign a color c(e) to every element e∈E (the same color can go to more than one element). The palette of a subset F of E, denoted by c(F), is the image of F under c. Assume also that colors have prices (in the form of a function π(?), where ? is the label of a color), and define the chromatic price as: π(F)=∑_?∈c(F)π(?). We consider the following problem: find a base B∈B such that π(B) is minimum. We show that the greedy algorithm delivers a lnr(M)-approximation of the unknown optimal value, where r(M) is the rank of matroid M. By means of a reduction from SETCOVER, we prove that the lnr(M) ratio cannot be further improved, even in the special case of partition matroids, unless . The results apply to the special case where M is a graphic matroid and where the prices π(?) are restricted to be all equal. This special case was previously known as the minimum label spanning tree (MLST) problem. For the MLST, our results improve over the ln(n-1)+1 ratio achieved by Wan, Chen and Xu in 2002. Inspired by the generality of our results, we study the approximability of coloring problems with different objective function π(F), where F is a common independent set on matroids M₁,…,M_k and, more generally, to independent systems characterized by the k-for-1 property.