Computer Science - Discrete Mathematics Publications (50)


Computer Science - Discrete Mathematics Publications

In this study, we provide mathematical and practice-driven justification for using $[0,1]$ normalization of inconsistency indicators in pairwise comparisons. The need for normalization, as well as problems with the lack of normalization, are presented. A new type of paradox of infinity is described. Read More

We resolve a number of long-standing open problems in online graph coloring. More specifically, we develop tight lower bounds on the performance of online algorithms for fundamental graph classes. An important contribution is that our bounds also hold for randomized online algorithms, for which hardly any results were known. Read More

We propose a multi-shell sampling grid and develop corresponding transforms for the accurate reconstruction of the diffusion signal in diffusion MRI by expansion in the spherical polar Fourier (SPF) basis. The transform is exact in the radial direction and accurate, on the order of machine precision, in the angular direction. The sampling scheme uses an optimal number of samples equal to the degrees of freedom of the diffusion signal in the SPF domain. Read More

While greedy algorithms have long been observed to perform well on a wide variety of problems, up to now approximation ratios have only been known for their application to problems having submodular objective functions $f$. Since many practical problems have non-submodular $f$, there is a critical need to devise new techniques to bound the performance of greedy algorithms in the case of non-submodularity. Our primary contribution is the introduction of a novel technique for estimating the approximation ratio of the greedy algorithm for maximization of monotone non-decreasing functions based on the curvature of $f$ without relying on the submodularity constraint. Read More

For each integer $n$ we present an explicit formulation of a compact linear program, with $O(n^3)$ variables and constraints, which determines the satisfiability of any 2SAT formula with $n$ boolean variables by a single linear optimization. This contrasts with the fact that the natural polytope for this problem, formed from the convex hull of all satisfiable formulas and their satisfying assignments, has superpolynomial extension complexity. Our formulation is based on multicommodity flows. Read More

Listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e. Read More

Quantum discord refers to an important aspect of quantum correlations for bipartite quantum systems. In our earlier works we have shown that corresponding to every graph (combinatorial) there are quantum states whose properties are reflected in the structure of the corresponding graph. Here, we attempt to develop a graph theoretic study of quantum discord that corresponds to a necessary and sufficient condition of zero quantum discord states which says that the blocks of density matrix corresponding to a zero quantum discord state are normal and commute with each other. Read More

In a signed graph $G$, a negative clique is a complete subgraph having negative edges only. In this article, we give characteristic polynomial expressions, and eigenvalues of some signed graphs having negative cliques. This includes signed cycle graph, signed path graph, a complete graph with disjoint negative cliques, and star block graph with negative cliques. Read More

In this work we deal with the so-called path convexities, defined over special collections of paths. For example, the collection of the shortest paths in a graph is associated with the well-known geodesic convexity, while the collection of the induced paths is associated with the monophonic convexity; and there are many other examples. Besides reviewing the path convexities in the literature, we propose a general path convexity framework, of which most existing path convexities can be viewed as particular cases. Read More

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size needed for maximally recoverable codes in grid topologies. Read More

The weighted tree augmentation problem (WTAP) is a fundamental network design problem. We are given an undirected tree $G = (V,E)$, an additional set of edges $L$ called links and a cost vector $c \in \mathbb{R}^L_{\geq 1}$. The goal is to choose a minimum cost subset $S \subseteq L$ such that $G = (V, E \cup S)$ is $2$-edge-connected. Read More

We define a new model of stochastically evolving graphs, namely the \emph{Edge-Uniform Stochastic Graphs}. In this model, each possible edge of an underlying general static graph evolves independently being either alive or dead at each discrete time step of evolution following a (Markovian) stochastic rule. The stochastic rule is identical for each possible edge and may depend on the previous $k \ge 0$ observations of the edge's state. Read More

Being an unsupervised machine learning and data mining technique, biclustering and its multimodal extensions are becoming popular tools for analysing object-attribute data in different domains. Apart from conventional clustering techniques, biclustering is searching for homogeneous groups of objects while keeping their common description, e.g. Read More

Computational topology is an area that revisits topological problems from an algorithmic point of view, and develops topological tools for improved algorithms. We survey results in computational topology that are concerned with graphs drawn on surfaces. Typical questions include representing surfaces and graphs embedded on them computationally, deciding whether a graph embeds on a surface, solving computational problems related to homotopy, optimizing curves and graphs on surfaces, and solving standard graph algorithm problems more efficiently in the case of surface-embedded graphs. Read More

In this work, we construct heuristic approaches for the traveling salesman problem (TSP) based on embedding the discrete optimization problem into continuous spaces. We explore multiple embedding techniques -- namely, the construction of dynamical flows on the manifold of orthogonal matrices and associated Procrustes approximations of the TSP cost function. In particular, we find that the Procrustes approximation provides a competitive biasing approach for the Lin--Kernighan heuristic. Read More

There has recently been considerable interest in completing a low-rank matrix or tensor given only a small fraction (or few linear combinations) of its entries. Related approaches have found considerable success in the area of recommender systems, under machine learning. From a statistical estimation point of view, the gold standard is to have access to the joint probability distribution of all pertinent random variables, from which any desired optimal estimator can be readily derived. Read More

Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a $\overline{\mathbb{Q}}$-valued objective function given as a sum of fixed-arity functions, where $\overline{\mathbb{Q}}=\mathbb{Q}\cup\{\infty\}$ is the set of extended rationals. In Boolean surjective VCSPs variables take on labels from $D=\{0,1\}$ and an optimal assignment is required to use both labels from $D$. A classic example is the global min-cut problem in graphs. Read More

Point clouds arising from structured data, mainly as a result of CT scans, provides special properties on the distribution of points and the distances between those. Yet often, the amount of data provided can not compare to unstructured point clouds, i.e. Read More

Recently, Deshpande et al. introduced a new measure of the complexity of a Boolean function. We call this measure the "goal value" of the function. Read More

This paper focuses on the identification of overlapping communities, allowing nodes to simultaneously belong to several communities, in a decentralised way. To that aim it proposes LOCNeSs, an algorithm specially designed to run in a decentralised environment and to limit propagation, two essential characteristics to be applied in mobile networks. It is based on the exploitation of the preferential attachment mechanism in networks. Read More

A finite abstract simplicial complex G defines two finite simple graphs: the Barycentric refinement G1, connecting two simplices if one is a subset of the other and the connection graph G', connecting two simplices if they intersect. We prove that the Poincare-Hopf value i(x)=1-X(S(x)), where X is Euler characteristics and S(x) is the unit sphere of a vertex x in G1, agrees with the Green function value g(x,x),the diagonal element of the inverse of (1+A'), where A' is the adjacency matrix of G'. By unimodularity, det(1+A') is the product of parities (-1)^dim(x) of simplices in G, the Fredholm matrix 1+A' is in GL(n,Z), where n is the number of simplices in G. Read More

Leader election is a basic symmetry breaking problem in distributed computing. All nodes of a network have to agree on a single node, called the leader. If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. Read More

A binary triangle of size $n$ is a triangle of zeroes and ones, with $n$ rows, built with the same local rule as the standard Pascal triangle modulo $2$. A binary triangle is said to be balanced if the absolute difference between the numbers of zeroes and ones that constitute this triangle is at most $1$. In this paper, the existence of balanced binary triangles of size $n$, for all positive integers $n$, is shown. Read More

In this paper, we give a new framework for the stochastic shortest path problem in finite state and action spaces. Our framework generalizes both the frameworks proposed by Bertsekas and Tsitsikli and by Bertsekas and Yu. We prove that the problem is well-defined and (weakly) polynomial when (i) there is a way to reach the target state from any initial state and (ii) there is no transition cycle of negative costs (a generalization of negative cost cycles). Read More

In this article we study the minimum number $\kappa$ of additional automata that a Boolean automata network (BAN) associated with a given block-sequential update schedule needs in order to simulate a given BAN with a parallel update schedule. We introduce a graph that we call $\mathsf{NECC}$ graph built from the BAN and the update schedule. We show the relation between $\kappa$ and the chromatic number of the $\mathsf{NECC}$ graph. Read More

Affine $$\lambda$$-terms are $$\lambda$$-terms in which each bound variable occurs at most once and linear $$\lambda$$-terms are $$\lambda$$-terms in which each bound variables occurs once. and only once. In this paper we count the number of closed affine $$\lambda$$-terms of size $n$, closed linear $$\lambda$$-terms of size $n$, affine $$\beta$$-normal forms of size $n$ and linear $$\beta$$-normal forms of ise $n$, for different ways of measuring the size of $$\lambda$$-terms. Read More

A polynomial $p\in\mathbb{R}[z_1,\dots,z_n]$ is real stable if it has no roots in the upper-half complex plane. Gurvits's permanent inequality gives a lower bound on the coefficient of the $z_1z_2\dots z_n$ monomial of a real stable polynomial $p$ with nonnegative coefficients. This fundamental inequality has been used to attack several counting and optimization problems. Read More

Since planar triangle-free graphs are 3-colourable, such a graph with n vertices has an independent set of size at least n/3. We prove that unless the graph contains a certain obstruction, its independence number is at least n/(3-epsilon) for some fixed epsilon>0. We also provide a reduction rule for this obstruction, which enables us to transform any plane triangle-free graph G into a plane triangle-free graph G' such that alpha(G')-|G'|/3=alpha(G)-|G|/3 and |G'|<=(alpha(G)-|G|/3)/epsilon. Read More

Locally recoverable codes (LRC) have recently been a subject of intense research due to the theoretical appeal and their applications in distributed storage systems. In an LRC, any erased symbol of a codeword can be recovered by accessing only few other symbols. For LRC codes over small alphabet (such as binary), the optimal rate-distance trade-off is unknown. Read More

We show that the vertices and edges of a $d$-dimensional grid graph $G=(V,E)$ ($d\geqslant 2$) can be labeled with the integers from $\{1,\ldots,\lvert V\rvert\}$ and $\{1,\ldots,\lvert E\rvert\}$, respectively, in such a way that for every subgraph $H$ isomorphic to a $d$-cube the sum of all the labels of $H$ is the same. As a consequence, for every $d\geqslant 2$, every $d$-dimensional grid graph is $Q_d$-supermagic where $Q_d$ is the $d$-cube. Read More

The Lov\'{a}sz Local Lemma (LLL) shows that, if a set of collection of "bad" events $\mathcal B$ in a probability space are not too likely and not too interdependent, then there is a positive probability that no bad-events in $\mathcal B$ occur. Moser & Tardos (2010) gave sequential and parallel algorithms which transformed most applications of the variable-assignment LLL into efficient (parallel and sequential) algorithms. There has been limited success in developing parallel algorithms for more generalized forms of the LLL. Read More

It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P, Q is the sum of the extension complexities of P and Q. We give an affirmative answer to this question for the case that one of the two polytopes is a pyramid. Read More

We study the {\em maximum duo-preservation string mapping} ({\sc Max-Duo}) problem, which is the complement of the well studied {\em minimum common string partition} ({\sc MCSP}) problem. Both problems have applications in many fields including text compression and bioinformatics. Motivated by an earlier local search algorithm, we present an improved approximation and show that its performance ratio is no greater than ${35}/{12} < 2. Read More

In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best known lower bound is the trival (dimension) bound, $\Omega(n^2)$, the best known upper bound is the extended formulation by Wong (1980) of size $O(n^3)$ (also Martin, 1991). In this note we give a nondeterministic communication protocol with cost $\log_2(n^2\log n)+O(1)$ for the support of the spanning tree slack matrix. Read More

A $k$-subcoloring of a graph is a partition of the vertex set into at most $k$ cluster graphs, that is, graphs with no induced $P_3$. 2-subcoloring is known to be NP-complete for comparability graphs and three subclasses of planar graphs, namely triangle-free planar graphs with maximum degree 4, planar perfect graphs with maximum degree 4, and planar graphs with girth 5. We show that 2-subcoloring is also NP-complete for planar comparability graphs with maximum degree 4. Read More

Comparing alternatives in pairs is a well-known method of ranking creation. Experts are asked to perform a series of binary comparisons and then, using mathematical methods, the final ranking is prepared. As experts conduct the individual assessments, they may not always be consistent. Read More

The repetition threshold is the smallest real number $\alpha$ such that there exists an infinite word over a $k$-letter alphabet that avoids repetition of exponent strictly greater than $\alpha$. This notion can be generalized to graph classes. In this paper, we completely determine the repetition thresholds for caterpillars and caterpillars of maximum degree $3$. Read More

The discriminator of an integer sequence s = (s(i))_{i>=0}, introduced by Arnold, Benkoski, and McCabe in 1985, is the function D_s(n) that sends n to the least integer m such that the numbers s(0), s(1), ... Read More

We determine the value of some search games where our goal is to find all of some hidden treasures using queries of bounded size. The answer to a query is either empty, in which case we lose, or a location, which contains a treasure. We prove that if we need to find $d$ treasures at $n$ possible locations with queries of size at most $k$, then our chance of winning is $\frac{k^d}{\binom nd}$ if each treasure is at a different location and $\frac{k^d}{\binom{n+d-1}d}$ if each location might hide several treasures for large enough $n$. Read More

A hereditary class $\mathcal{G}$ of graphs is $\chi$-bounded if there is a $\chi$-binding function, say $f$ such that $\chi(G) \leq f(\omega(G))$, for every $G \in \cal{G}$, where $\chi(G)$ ($\omega(G)$) denote the chromatic (clique) number of $G$. It is known that for every $2K_2$-free graph $G$, $\chi(G) \leq \binom{\omega(G)+1}{2}$, and the class of ($2K_2, 3K_1$)-free graphs does not admit a linear $\chi$-binding function. In this paper, we are interested in classes of $2K_2$-free graphs that admit a linear $\chi$-binding function. Read More

We consider the distributed version of the Multiple Knapsack Problem (MKP), where $m$ items are to be distributed amongst $n$ processors, each with a knapsack. We propose different distributed approximation algorithms with a tradeoff between time and message complexities. The algorithms are based on the greedy approach of assigning the best item to the knapsack with the largest capacity. Read More

We consider the previously defined notion of finite-state independence and we focus specifically on normal words. We characterize finite-state independence of normal words in three different ways, using three different kinds of finite automata running on infinite words (B\"uchi automata): finite automata with two input tapes, selectors and shufflers. We give an algorithm to construct a pair of finite-state independent normal words. Read More

We solve the following problem: Can an undirected weighted graph G be parti- tioned into two non-empty induced subgraphs satisfying minimum constraints for the sum of edge weights at vertices of each subgraph? We show that this is possible for all constraints a(x), b(x) satisfying d_G(x) >= a(x) + b(x) + 2W_G(x), for every vertex x, where d_G(x), W_G(x) are, respectively, the sum and maximum of incident edge weights. Read More

Estimates of population size for hidden and hard-to-reach individuals are of particular interest to health officials when health problems are concentrated in such populations. Efforts to derive these estimates are often frustrated by a range of factors including social stigma or an association with illegal activities that ordinarily preclude conventional survey strategies. This paper builds on and extends prior work that proposed a method to meet these challenges. Read More

The celebrated theorem of Robertson and Seymour states that in the family of minor-closed graph classes, there is a unique minimal class of graphs of unbounded tree-width, namely, the class of planar graphs. In the case of tree-width, the restriction to minor-closed classes is justified by the fact that the tree-width of a graph is never smaller than the tree-width of any of its minors. This, however, is not the case with respect to clique-width, as the clique-width of a graph can be (much) smaller than the clique-width of its minor. Read More

Let $n\geq k\geq 2$ be two integers and $S$ a subset of $\{0,1,\dots,k-1\}$. The graph $J_{S}(n,k)$ has as vertices the $k$-subsets of the $n$-set $[n]=\{1,\dots,n\}$ and two $k$-subsets $A$ and $B$ are adjacent if $|A\cap B|\in S$. In this paper, we use Godsil-McKay switching to prove that for $k\geq 2, S=\{0,1,\dots,k-1\}$, the graphs $J_S(4k+1,2k)$ are not determined by spectrum and the graphs $J_{S\cup\{k\}}(n,2k+1)$ are not determined by spectrum for any $n\geq 4k+2$. Read More

Generalized Fibonacci-like sequences appear in finite difference approximations of the Partial Differential Equations based upon replacing partial differential equations by finite difference equations. This paper studies properties of the generalized Fibonacci-like sequence F_(n+2)=A+BF_(n+1)+CF_n. It is shown that this sequence is periodic with the period T>2 if C=-1,|B|<2. Read More

Zero forcing is an iterative graph coloring process where at each discrete time step, a colored vertex with a single uncolored neighbor forces that neighbor to become colored. The zero forcing number of a graph is the cardinality of the smallest set of initially colored vertices which forces the entire graph to eventually become colored. Connected forcing is a variant of zero forcing in which the initially colored set of vertices induces a connected subgraph; the analogous parameter of interest is the connected forcing number. Read More