Search

For a positive integer t, a t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times of their distance in G. In this paper, we consider the problem of finding a t-spanner with minimum number of edges in a given graph, which we call Minimum t -Spanner Problem . For t ≥ 2 , Minimum t -Spanner Problem is known to be NP-hard in general graphs. When the input graph is planar, it is shown by Brandes and Handke in 1997 that this problem is NP-hard for t ≥ 5 . Since then, the case of t ∈ { 2 , 3 , 4 } has been open for more than two decades. The main contribution of this paper is to settle this open problem by showing the NP-hardness of Minimum t -Spanner Problem in planar graphs for t ∈ { 2 , 3 , 4 } . As a byproduct, we show the NP-hardness of the problem on degree-bounded graphs, which improves previously known degree-bounds. We also present a fixed-parameter algorithm for this problem in which the number of removed edges is regarded as a parameter.

We study a combinatorial problem arising from the microarray synthesis. The objective of the Border Minimization Problem (BMP) is to place a set of sequences in the array and to find an embedding of these sequences into a common supersequence such that the sum of the “border length” is minimized. A variant of the problem, called P-BMP, is that the placement is given and the concern is simply to find the embedding. An exponential time algorithm has been proposed for the problem but it is unknown whether the problem is NP-hard or not. In this paper, we give a comprehensive study of different variations of BMP by presenting NP-hardness proofs and approximation algorithms. We show that BMP, P-BMP, and 1D-BMP are all NP-hard and 1D-BMP is polynomial time solvable. The interesting implications include (i) the BMP is NP-hard regardless of the dimension (1D or 2D) of the array; (ii) the array dimension differentiates the complexity of the P-BMP; and (iii) for 1D array, whether placement is given differentiates the complexity of the BMP. Another contribution of the paper is devising approximation algorithms, and in particular, we present a randomized approximation algorithm for BMP with approximation ratio O ( n 1 ∕ 4 log 2 n ) , where n is the total number of sequences.

Murota (1998) and Murota and Shioura (1999) introduced concepts of M-convex function and M♮-convex function as discrete convex functions, which are generalizations of valuated matroids due to Dress and Wenzel (1992). In the present paper we consider a new operation defined by a convolution of sections of an M♮-convex function that transforms the given M♮-convex function to an M-convex function, which we call a compression of an M♮-convex function. For the class of valuated generalized matroids, which are special M♮-convex functions, the compression induces a valuated permutohedron together with a decomposition of the valuated generalized matroid into flag-matroid strips, each corresponding to a maximal linearity domain of the induced valuated permutohedron. We examine the details of the structure of flag-matroid strips and the induced valuated permutohedron by means of discrete convex analysis of Murota.

We consider the following variant of the Mortality Problem: given $k\times k$ matrices $A_1, A_2, \dots,A_{t}$, does there exist nonnegative integers $m_1, m_2, \dots,m_t$ such that the product $A_1^{m_1} A_2^{m_2} \cdots A_{t}^{m_{t}}$ is equal to the zero matrix? It is known that this problem is decidable when $t \leq 2$ for matrices over algebraic numbers but becomes undecidable for sufficiently large $t$ and $k$ even for integral matrices. In this paper, we prove the first decidability results for $t>2$. We show as one of our central results that for $t=3$ this problem in any dimension is Turing equivalent to the well-known Skolem problem for linear recurrence sequences. Our proof relies on the Primary Decomposition Theorem for matrices that was not used to show decidability results in matrix semigroups before. As a corollary we obtain that the above problem is decidable for $t=3$ and $k \leq 3$ for matrices over algebraic numbers and for $t=3$ and $k=4$ for matrices over real algebraic numbers. Another consequence is that the set of triples $(m_1,m_2,m_3)$ for which the equation $A_1^{m_1} A_2^{m_2} A_3^{m_3}$ equals the zero matrix is equal to a finite union of direct products of semilinear sets. For $t=4$ we show that the solution set can be non-semilinear, and thus it seems unlikely that there is a direct connection to the Skolem problem. However we prove that the problem is still decidable for upper-triangular $2 \times 2$ rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations., Full version of the MFCS submission

The Ramsey number $R_X(p,q)$ for a class of graphs $X$ is the minimum $n$ such that every graph in $X$ with at least $n$ vertices has either a clique of size $p$ or an independent set of size $q$. We say that Ramsey numbers are linear in $X$ if there is a constant $k$ such that $R_{X}(p,q) \leq k(p+q)$ for all $p,q$. In the present paper we conjecture that if $X$ is a hereditary class defined by finitely many forbidden induced subgraphs, then Ramsey numbers are linear in $X$ if and only if $X$ excludes a forest, a disjoint union of cliques and their complements. We prove the "only if" part of this conjecture and verify the "if" part for a variety of classes. We also apply the notion of linearity to bipartite Ramsey numbers and reveal a number of similarities and differences between the bipartite and non-bipartite case., 24 pages

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs ( s 1 , t 1 ) and ( s 2 , t 2 ) , and the objective is to find two vertex-disjoint paths P 1 and P 2 such that P i is a shortest path from s i to t i for i = 1 , 2 , if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.

This paper concerns the minimax center of a collection of linear subspaces. When the subspaces are $k$-dimensional subspaces of $\mathbb{R}^n$, this can be cast as finding the center of a minimum enclosing ball on a Grassmann manifold, Gr$(k,n)$. For subspaces of different dimension, the setting becomes a disjoint union of Grassmannians rather than a single manifold, and the problem is no longer well-defined. However, natural geometric maps exist between these manifolds with a well-defined notion of distance for the images of the subspaces under the mappings. Solving the initial problem in this context leads to a candidate minimax center on each of the constituent manifolds, but does not inherently provide intuition about which candidate is the best representation of the data. Additionally, the solutions of different rank are generally not nested so a deflationary approach will not suffice, and the problem must be solved independently on each manifold. We propose and solve an optimization problem parametrized by the rank of the minimax center. The solution is computed using a subgradient algorithm on the dual. By scaling the objective and penalizing the information lost by the rank-$k$ minimax center, we jointly recover an optimal dimension, $k^*$, and a central subspace, $U^* \in$ Gr$(k^*,n)$ at the center of the minimum enclosing ball, that best represents the data., 26 pages

A linear extension of a polytope Q is any polytope which can be mapped onto Q via an affine transformation. The extension complexity of a polytope is the minimum number of facets of any linear extension of this polytope. In general, computing the extension complexity of a given polytope is difficult. The extension complexity is also equal to the nonnegative rank of any slack matrix of the polytope. In this paper, we introduce a new geometric lower bound on the extension complexity of a polytope, i.e., which relies only on the knowledge of some of its geometric characteristics. It is based on the monotone behaviour of the f -vector of polytopes under affine maps. We present numerical results showing that this bound can improve upon existing geometric lower bounds, and provide a generalization of this lower bound for the nonnegative rank of any matrix.

There has been much research into freeness properties of finitely generated matrix semigroups under various constraints, such as the dimensions of the generator matrices and the semiring over which the matrices are defined. Most freeness problems have been shown to be undecidable starting from dimension three, even for upper-triangular matrices over the natural numbers. There are many open problems still remaining in dimension two. A recent paper has also investigated freeness properties of bounded languages of matrices, which are matrices from a set M∗1 M∗2· · · M∗k ⊆ Fn×n for some semiring F and a fixed value k ∈ N>0, where matrices M1, . . . , Mk are given [1]. We consider a notion of freeness and ambiguity for scalar reachability problems in matrix semigroups and bounded languages of matrices. Scalar reachability concerns the set {ρTMτ |M ∈ S}, where ρ, τ ∈ F n are vectors and S ⊆ F n×n is a finitely generated matrix semigroup. Ambiguity and freeness problems are defined in terms of the uniqueness of factorizations for each scalar. Such problems have also been studied in connection to formal power series. We show various undecidability results and their connections to weighted and probabilistic finite automata.

The Second Malta Conference in Graph Theory and Combinatorics was held in June 2017. This conference commemorated the 75th birthday of Professor Stanley Fiorini, who had introduced graph theory and combinatorics at the University of Malta. Many may wonder when the previous Malta Conference was held. The First Malta Conference on Graphs and Combinatorics was convened during the period 28 May to 2 June, 1990, at the Suncrest Hotel, in Qawra, St Paul’s Bay. It differed from a number of similar conferences held in the central Mediterranean region at that time in that it consisted of three types of talks. László Lovász and Carsten Thomassen delivered two instructional courses of five one-hour lectures each; the former was A Survey of Independent Sets in Graphs and the latter was Embeddings of Graphs. There were also four invited speakers, L.W. Beineke, N.L. Biggs, R. Graham and D.J.A. Welsh, each of whom gave a one-hour lecture. The third type were the twenty-minute contributed talks running in two parallel sessions and given by 39 speakers. Volume 124 (1994) of the journal Discrete Mathematics was a special edition dedicated to this conference; it was edited by Stanley Fiorini and Josef Lauri, and it consisted of 22 selected papers., N/A

A mapping of k-bit strings into n-bit strings is called an (α,β)-map if k-bit strings which are more than αk apart are mapped to n-bit strings that are more than βn apart in Hamming distance. This is a relaxation of the classical problem of constructing error-correcting codes, which corresponds to α=0. Existence of an (α,β)-map is equivalent to existence of a graph homomorphism H¯(k,αk)→H¯(n,βn), where H(n,d) is a Hamming graph with vertex set {0,1}n and edges connecting vertices differing in d or fewer entries. This paper proves impossibility results on achievable parameters (α,β) in the regime of n,k→∞ with a fixed ratio nk=ρ. This is done by developing a general criterion for existence of graph-homomorphism based on the semi-definite relaxation of the independence number of a graph (known as the Schrijver's θ-function). The criterion is then evaluated using some known and some new results from coding theory concerning the θ-function of Hamming graphs. As an example, it is shown that if β>1/2 and nk – integer, the nk-fold repetition map achieving α=β is asymptotically optimal. Finally, constraints on configurations of points and hyperplanes in projective spaces over F2 are derived., National Science Foundation (U.S.) (Grant No CCF-13-1862), Simons Institute for the Theory of Computing

Given an n-vertex directed graph G=(V,E) and a set [email protected]?VxV of requests, we consider assigning a set of edges to each vertex in G so that for every request (u,v) in R the union of the edge sets assigned to u and v contains a path from u to v. The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinalities of the edge sets assigned to each vertex. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs and restricted request structures, such as bidirectional trees with requests of all pairs of vertices. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general R has @Q(logn) lower and upper bounds on approximation ratio under the assumption P NP. We then assume R forms a clique structure, called Subset-Full, which is a natural setting in the context of the application. Interestingly, under this natural setting, MCD becomes 2-approximable, though it has still no polynomial time approximation algorithm whose factor is better than 677/676 unless P=NP. Finally, we show that this approximation ratio can be improved to 3/2 for the undirected variant of MCD with Subset-Full.

In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Biro et al. defined the problem of finding a maximum cardinality matching that contains minimum number of blocking pairs. They proved that this problem is not approximable within some constant @d>1 unless P=NP, even when all preference lists are of length at most 3. In this paper, we improve this constant @d to n^1^-^@e for any @e>0, where n is the number of men in an input.

§0. INTRODUCTION THiS PAPER computes the odd dimensional, projective, surgery groups LPn+I(~) for all finite groups 7r. The computat ion is made as follows. We reduce by Dress induction to the case 1r is 2-hyperelementary and here, we express LPn+l(Tr) as a direct sum of class groups C(X) where X ranges over the irreducible characters of ~r. Several precise numerical calculations are deduced from the general computation. One such calculation is the following: If the Schur index of any irreducible character of a 2-hyperelementary subgroup of ,r is trivial then L1e(Tr) -0; this is the case, for example, if either zr itself or, more generally, every 2-hyperelementary subgroup of is a direct product of abelian and dihedral groups. Another precise calculation is the following: If the 2-hyperelementary subgroups of ~r are abelian then L 3 P ( T T ) ~ (Z[2Z) r°-I where r0 is the number of real, irreducible characters of ~-. The latter calculation and a special case of the former have appeared already in Bak [4]. It is worth mentioning that the even dimensional, projective, surgery groups L~',(~') of finite groups 7r are computed in the following papers; in the case that the 2-hyperelementary subgroups of ~" are abelian, they have been computed already in Bak[4 ,7] and Bak-Schar lau[9] and in the general case, they are computed in Kolster [21] and Kolster [21.1]. We describe now the organization and results of the paper. In §l, we recall briefly the required notation from the Ktheory of quadratic forms; in particular, if A is an involution invariant subring of a semisimple ring B with involution and if A = _+ l then fWo~(A) denotes the Witt group of A-forms (equivalently nonsingular min-quadratic modules) on finitely generated, project ive A-modules which become free of even rank over B. We then cite an exact sequence of Witt groups due to Pardon and Ranicki. In §2, we compute the cokernel of the canonical homorphism

Publishing personal data without giving up privacy is becoming an increasingly important problem in different fields. In the last years, different interesting approaches have been proposed, i.e. k-Anonymity and l-Diversity. Given an input table, these approaches partition its rows so that the computed partition satisfies some constraint, in order to prevent the inference of the individuals the data belong to. Then, the rows in a same set of the partition are related to the same rows by suppressing some of their entries. Here we focus on the l-Diversity problem, where the attributes of the input table are distinguished in sensitive attributes and quasi-identifier attributes. The goal is to partition the rows of the input table, so that each set C of the partition contains at most |C|/l rows having a specific value in the sensitive attribute, and the number of suppressions is minimized. In this paper we investigate the approximation and parameterized complexity of l-Diversity. First, we prove that the problem is not approximable within factor c ln l, for some constant c>0, even if the input table consists of only two columns, and that the problem is APX-hard, even if l=4 and the input table contains exactly three columns. Then we give an approximation algorithm of factor m (where m+1 is the number of columns in the input table), when the sensitive attribute ranges over an alphabet of constant size. Concerning the parameterized complexity, we prove that the problem is W[1]-hard when parameterized by the cost-bound, by l, and by the size of the alphabet. Then we prove that the problem admits a fixed-parameter algorithm when both the maximum number of different values in a column and the number of columns are parameters

Many real-world systems are modeled as evolving bipartite networks and their one-mode projections. In particular, Discrete Combinatorial Systems (DCSs), which consist of a finite set of elementary units and different combinations of these units, can be modeled by a subclass of bipartite networks known as Alphabetic Bipartite Networks or alpha-BiNs, where the bottom partite-set contains a fixed number of nodes (the elementary units) and the top partite-set grows unboundedly with time through the addition of nodes (the combinations). The principal questions in the study of alpha-BIN evolution are to predict the degree distribution of the bottom set and that of the projection onto the bottom set (the bottom projection), from a knowledge of the bipartite growth dynamics. In this paper, we propose a realistic growth model for alpha-BiNs, where the degree distribution of the top set (i.e., the distribution of the number of elementary units in the composite entities in the DCS) can be any arbitrary distribution with finite first and second moments. Utilizing an exact correspondence between the preferential growth of alpha-BiNs and the Polya Urn scheme, we analytically solve the model to compute exact degree distributions of the bottom (fixed) set and the bottom projection. To the best of our knowledge, this is the first work which proposes and solves such a generalized growth model for alpha-BiNs. We also derive that the degree distributions of both the bottom set and the bottom projection, suitably normalized with time, converge to distributions that are invariant over time. We also verify that this improved model can accurately explain the degree distributions of several real-world DCSs and their projections. (C) 2012 Elsevier B.V. All rights reserved.

The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e., finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.

The generalized Petersen graphs (GPGs) which have been invented by Watkins, may serve for perhaps the simplest nontrivial examples of "galactic" graphs, i.e. those with a nice property of having a semiregular automorphism. Some of them are also vertex-transitive or even more highly symmetric, and some are Cayley graphs. In this paper, we study a further extension of the notion of GPGs with the emphasis on the symmetry properties of the newly defined graphs. © 2006 Elsevier B.V. All rights reserved.

Since 1782, when Euler addressed the question of existence of a pair of orthogonal Latin squares (OLS) by stating his famous conjecture, these structures have remained an active area of research. In this paper, we examine the polyhedral aspects of OLS. In particular, we establish the dimension of the OLS polytope, describe all cliques of the underlying intersection graph and categorize them into three classes. Two of these classes are shown to induce facet-defining inequalities of Chvátal rank two. For each such class, we provide a polynomial separation algorithm of the lowest possible complexity.

Let k be a field. Let R be a finite-dimensional k-algebra with centre k which is representation-finite and hereditary; thus R is Morita equivalent to the tensor algebra of a k-species with underlying graph A a disjoint union of Dynkin diagrams, and the set of isomorphism classes of indecomposable R-modules corresponds bijectively to the set @+ of positive roots of the corresponding semisimple complex Lie algebra g (see [G] and [DRl ] ). Consequently, the Grothendieck group K( R mod) of all finitely generated R-modules modulo split exact sequences is the free abelian group with basis indexed by @ +. Let h be a Cartan subalgebra of g and g = n + @ h 0 n _ the corresponding triangular decomposition. Note that n+ is the direct sum of one-dimensional complex vectorspaces indexed by the elements of @ +, so we may identify K(R mod) Q @ and n + as vectorspaces, and we deal with the problem of how to recover the Lie multiplication of n, on K( R mod). We have shown in [R2] that the Grothendieck group K(R mod) may be considered in a natural way as a Lie algebra by using as structure constants the evaluations of Hall polynomials at 1. The aim of this paper is to show that this Lie algebra K(R mod) can be identified with a Chevalley H-form of n + ; in particular K( R mod) @ @ and n+ are isomorphic as Lie algebras. We are going to determine all possible polynomials which occur as Hall polynomials ~p;;~, where x, y, z E @ + . There are precisely 16 different polynomials (including the zero polynomial cpO), and the absolute value of their evaluations at 1 is bounded by 3. One easily observes that q;X = 0 in case y #z +x; thus let us assume y = z + x. In this case, precisely one of the two polynomials cp,‘, and cpzZ is non-zero. The non-zero polynomials cp;’ can be written in the form irqi, where [, = C’:i T’, with 1 d r 6 3, and (pi is one of the following 12 integral polynomials

Summary It was proved by Ahlswede (1971) that codes whose codewords form a group or even a linear space do not achieve Shannon's capacity for discrete memoryless channels even if the decoding procedure is arbitrary. Sharper results were obtained in Part I of this paper. For practical purposes, one is interested not only in codes which allow a short encoding procedure but also an efficient decoding procedure. Linear codes—the codewords form a linear space and the decoding is done by coset leader decoding — have a fairly efficient decoding procedure. But in order to achieve high rates the following slight generalization turns out to be very useful: We allow the encoder to use a coset of a linear space as a set of codewords. We call these codes shifted linear codes or coset codes. They were implicitly used by Dobrushin (1963) . This new code concept has all the advantages of the previous one with respect to encoding and decoding efficiency and enables us to achieve positive rate on discrete memoryless channels whenever Shannon's channel capacity is positive and the length of the alphabet is less or equal to 5 (Theorem 3.1.1). (The result holds very likely also for all alphabets with a length a = ps, p prime, s positive integer). A disadvantage of the concepts of linear codes and of shifted linear codes is that they can be defined only for alphabets whose length is a prime power. In order to overcome this difficulty, we introduce generalized shifted linear codes. With these codes we can achieve a positive rate on arbitrary discrete memoryless channels if Shannon's capacity is positive (Theorem 3.2.1)