Search

We study approximation algorithms for graph pricing with vertex capacities yet without the traditional envy-free constraint. Specifically, we have a set of items V and a set of customers X where each customer \(i \in X\) has a budget \(b_i\) and is interested in a bundle of items \(S_i \subseteq V\) with \(|S_i| \le 2\). However, there is a limited supply of each item: we only have \(\mu _v\) copies of item v to sell for each \(v \in V\). We should assign a price p(v) to each \(v \in V\) and choose a subset \(Y \subseteq X\) of customers so that each \(i \in Y\) can afford their bundle (\(p(S_i) \le b_i\)) and at most \(\mu _v\) chosen customers have item v in their bundle for each item \(v \in V\). Each customer \(i \in Y\) pays \(p(S_i)\) for the bundle they purchased: our goal is to do this in a way that maximizes revenue. Such pricing problems have been studied from the perspective of envy-freeness where we also must ensure that \(p(S_i) \ge b_i\) for each \(i \notin Y\). However, the version where we simply allocate items to customers after setting prices and do not worry about the envy-free condition has received less attention.

We present a new approximation algorithm for the treewidth problem which constructs a corresponding tree decomposition as well. Our algorithm is a faster variation of Reed’s classical algorithm. For the benefit of the reader, and to be able to compare these two algorithms, we start with a detailed time analysis for Reed’s algorithm. We fill in many details that have been omitted in Reed’s paper. Computing tree decompositions parameterized by the treewidth k is fixed parameter tractable (FPT), meaning that there are algorithms running in time O(f(k)g(n)) where f is a computable function, g(n) is polynomial in n, and n is the number of vertices. An analysis of Reed’s algorithm shows \(f(k) = 2^{O(k \log k)}\) and \(g(n) = n \log n\) for a 5-approximation. Reed simply claims time \(O(n \log n)\) for bounded k for his constant factor approximation algorithm, but the bound of \(2^{\varOmega (k \log k)} n \log n\) is well known. From a practical point of view, we notice that the time of Reed’s algorithm also contains a term of \(O(k^2 2^{24k} n \log n)\), which for small k is much worse than the asymptotically leading term of \(2^{O(k \log k)} n \log n\). We analyze f(k) more precisely, because the purpose of this paper is to improve the running times for all reasonably small values of k.

A Robinson similarity matrix is a symmetric matrix where all entries in all rows and columns are increasing towards the diagonal. A Robinson matrix can be decomposed into the weighted sum of k adjacency matrices of a nested family of unit interval graphs. We study the problem of finding an embedding which gives a simultaneous unit interval embedding for all graphs in the family. This is called a uniform embedding. We give a necessary and sufficient condition for the existence of a uniform embedding, derived from paths in an associated graph. We also give an efficient combinatorial algorithm to find a uniform embedding or give proof that it does not exist, for the case where \(k=2\).

In this paper we study a variant of the classic d -Hitting Set problem with lower and upper capacity constraints, say A and B, respectively. The input to the problem consists of a universe U, a set family, \(\mathscr {S} \), of sets over U, where each set in the family is of size at most d, a non-negative integer k; and additionally two functions \(\alpha :\mathscr {S} \rightarrow \{1,\ldots ,A\}\) and \(\beta :\mathscr {S} \rightarrow \{1,\ldots ,B\}\). The goal is to decide if there exists a hitting set of size at most k such that for every set S in the family \(\mathscr {S} \), the solution contains at least \(\alpha (S)\) elements and at most \(\beta (S)\) elements from S. We call this the \((A, B)\)-Multi d-Hitting Set problem. We study the problem in the realm of parameterized complexity. We show that \((A, B)\)-Multi d-Hitting Set can be solved in \(\mathcal {O}^{\star }(d^{k}) \) time. For the special case when \(d=3\) and \(d=4\), we have an improved bound of \(\mathcal {O}^\star (2.2738^k)\) and \(\mathcal {O}^\star (3.562^{k})\), respectively. The former matches the running time of the classical 3-Hitting Set problem. Furthermore, we show that if we do not have an upper bound constraint and the lower bound constraint is same for all the sets in the family, say \(A>1\), then the problem can be solved even faster than d-Hitting Set.

This paper provides three nearly-optimal algorithms for scheduling t jobs in the \(\mathsf {CLIQUE}\) model. First, we present a deterministic scheduling algorithm that runs in \(O(\mathsf {Global}\mathsf {Congestion} + \mathsf {dilation})\) rounds for jobs that are sufficiently efficient in terms of their memory. The \(\mathsf {dilation}\) is the maximum round complexity of any of the given jobs, and the \(\mathsf {Global}\mathsf {Congestion}\) is the total number of messages in all jobs divided by the per-round bandwidth of \(n^2\) of the \(\mathsf {CLIQUE}\) model. Both are inherent lower bounds for any scheduling algorithm.

Let \( {\mathscr{C}} \) be a class of graphs closed under taking induced subgraphs. We say that \( {\mathscr{C}} \) has the clique-stable set separation property if there exists \( c \in {\mathbb{N}} \) such that for every graph \( G \in {\mathscr{C}} \) there is a collection \( {\mathscr{P}} \) of partitions (X, Y) of the vertex set of G with |\( {\mathscr{P}}\)| ≤ |V(G)|c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = \( \emptyset\), then there is (X, Y) ∊ \( {\mathscr{P}}\) with K ⊆ X and S ⊆ Y. In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. Goos in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families \( {\mathscr{S}}, {\mathscr{K}}\)of graphs and show that for every S ∊ \( {\mathscr{S}}\) and K ∊ \({\mathscr{K}}\), the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property.

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of computational complexity. Note that every n-vertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in \(\mathscr {O}(\log n)\) time. Thus, limiting the size of the vertex labels upper-bounds the space complexity of storing the graph.

Let p, t, q, n, m and r be positive integers, such that p is a prime number, \(q=p^t\), \(\gcd (q,n)=1\), \(m=\text{ ord}_n(q)\), and suppose that the prime factors of r divide n but not \((q^m-1)/n\), and that \(q^m \equiv 1 \pmod {4}\), if 4|r. Also let u such that \(u=\gcd (\frac{q^m-1}{q-1},\frac{q^m-1}{n})\). Assume that \(u=1\) or p is semiprimitive modulo u. Under these conditions, we are going to obtain the explicit factorization of the period polynomial of degree \(\gcd (\frac{q^{mr}-1}{q-1},\frac{q^{mr}-1}{nr})\) for the finite field \({\mathbb {F}}_{q^{mr}}\). In fact, we will see that such polynomial has always integer roots, meaning that the corresponding Gaussian periods are also integer numbers. As an application, we also determine the number of solutions of certain diagonal equations with constant exponent.

A surprising result of Bokal et al. proved that the exact minimum value of c such that c-crossing-critical graphs do not have bounded maximum degree is \(c=13\). The key to the result is an inductive construction of a family of 13-crossing-critical graphs with many vertices of arbitrarily high degrees. While the inductive part of the construction is rather easy, it all relies on the fact that a certain 17-vertex base graph has the crossing number 13, which was originally verified only by a machine-readable computer proof. We now provide a relatively short self-contained computer-free proof.

We investigate the problem of drawing two posets of the same ground set so that one is drawn from left to right and the other one is drawn from the bottom up. The input to this problem is a directed graph \(G = (V, E)\) and two sets X, Y with \(X \cup Y = E\), each of which can be interpreted as a partial order of V. The task is to find a planar drawing of G such that each directed edge in X is drawn as an x-monotone edge, and each directed edge in Y is drawn as a y-monotone edge. Such a drawing is called an xy-planar drawing.

We show that if \(A=\{a_1< a_2< \ldots < a_k\}\) is a set of real numbers such that the differences of the consecutive elements are distinct, then for and finite \(B \subset \mathbb {R}\), $$ |A+B|\gg |A|^{1/2}|B|. $$ The bound is tight up to the constant.

The Network Construction problem, studied by Angluin et al., Hodosa et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set V of vertices, construction costs for all possible edges between pairs of vertices from V, and a sequence \(S_1, S_2, \ldots \subseteq V\) of connectivity constraints, the objective is to find a set E of edges such that each \(S_i\) induces a connected subgraph of the graph (V, E) and the total cost of E is minimized. First, we study the online version where every constraint must be satisfied immediately after its arrival and edges that have already been added can never be removed. We give an \(O(B^2\log n)\)-competitive and \(O((B+\log r)\log n)\)-competitive polynomial-time algorithms along with an \(\varOmega (B)\)-competitive lower bound, where B is an upper bound on the size of constraints, while \(r,\ n\) denote the number of constraints and the number of vertices, respectively. In the cost-uniform case, we provide an \(\varOmega (\sqrt{B})\)-competitive lower bound and an \(O(\sqrt{n} (\log n + \log r))\)-competitive upper bound with high probability, when constraints are unbounded. All our randomized competitive bounds are against an adaptive adversary, except for the last one which is against an oblivious adversary. Next, we discuss a hybrid approximation method for the (offline) Network Construction problem combining an approximation algorithm of Hosoda et al. with one of Angluin et al. and an application of the hybrid method to bioinformatics. Finally, we consider a natural strengthening of the connectivity requirements in the Network Construction problem, where each constraint is supposed to induce a subgraph (of the constructed graph) of diameter at most d. Among other things, we provide a polynomial-time \((\left( {\begin{array}{c}B\\ 2\end{array}}\right) -B+2)\left( {\begin{array}{c}B\\ 2\end{array}}\right) \)-approximation algorithm for the Network Construction problem with the d-diameter requirements.

In this paper, we study the problem of computing the \(\mathcal {L}_{\infty }\)-norm of finite-dimensional linear time-invariant systems. This problem is first reduced to the computation of the maximal x-projection of the real solutions \((x, \, y)\) of a bivariate polynomial system \({\varSigma = \,}\{P,\frac{\partial P}{\partial y}\}\), with \(P\, \in \mathbb {Z}[x,y]\). Then, we use standard computer algebra methods to solve the problem. In this paper, we alternatively study a method based on rational univariate representations, a method based on root separation, and finally a method first based on the sign variation of the leading coefficients of the signed subresultant sequence and then based on the identification of an isolating interval for the maximal x-projection of the real solutions of \(\varSigma \).

We consider the problem of finding patrol schedules for k robots to visit a given set of n sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (when \(k=1\) and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of \(O(k^2 \log \frac{w_{\max }}{w_{\min }})\) to the optimal solution, where \(w_{\max }\) and \(w_{\min }\) are the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a 12-approximate solution, which runs in time \((n w_{\max }/w_{\min })^{O(k)}\).

Recently, a general framework for enumerating every non-isomorphic element in a graph class was given. Applying this framework, some graph classes have been enumerated using supercomputers, and their catalogs are provided on the web. Such graph classes include the classes of interval graphs, permutation graphs, and proper interval graphs. Last year, the enumeration algorithm for the class of Ptolemaic graphs that consists of graphs that satisfy Ptolemy inequality for the distance was investigated. They provided a polynomial time delay algorithm, but it is far from implementation. From the viewpoint of graph classes, the class is an intersection of the class of chordal graphs and the class of distance-hereditary graphs. In this paper, using the recent framework for enumerating every non-isomorphic element in a graph class, we give enumeration algorithms for the classes of distance-hereditary graphs and Ptolemaic graphs. For distance-hereditary graphs, its delay per graph is a bit slower than a previously known theoretical enumeration algorithm, however, ours is easy for implementation. In fact, although the previously known theoretical enumeration algorithm has never been implemented, we implemented our algorithm and obtained a catalog of distance-hereditary graphs of vertex numbers up to 14. We then modified the algorithm for distance-hereditary graphs to one for Ptolemaic graphs. Its delay can be the same as one for distance-hereditary graphs, which is much efficient than one proposed last year. We succeeded to enumerate Ptolemaic graphs of vertex numbers up to 15.

A vertex v in a graph G is called an absent vertex if it is not in any maximum independent set of G. Absent vertex discovery is useful in various scenarios. For example, if G depicts a wireless communication interference graph, the existence of absent vertices in G may indicate network throughput bottlenecks. However, finding all the absent vertices is hard since it is at least as difficult as finding all the maximum independent sets, which is NP-hard. This paper focuses on a method that finds the absent vertices incrementally, in the hope of finding many such vertices quickly in the early incremental stages. The method iteratively invokes two polynomial-time algorithms to find the ‘easy’ absent vertices, and then the expensive exact maximum independent set solver to find the ‘difficult’ ones. At each iteration, the Mirror theorem is used to find extra absent vertices, and then all the absent vertices found so far are removed from the graph before going into the next iteration, until all absent vertices are found. Experimental results show that the above method can find most absent vertices much earlier than the baseline brute-force method on several widely-used datasets, showing its effectiveness.

The two main concepts of Rigidity Theory are rigidity, where the framework has no continuous deformation, and global rigidity, where the given distance set determines the locations of the points up to isometry. We consider the following augmentation problem. Given a minimally rigid graph \(G=(V,E)\) in \(\mathbb {R}^2\), find a minimum cardinality edge set F such that the graph \(G'=(V,E+F)\) is globally rigid in \(\mathbb {R}^2\). We provide a min-max theorem and an \(O(|V|^2)\) time algorithm for this problem.

We prove that the distance-\(r\) dominating set, distance-\(r\) connected dominating set, distance-\(r\) vertex cover, and distance-\(r\) connected vertex cover problems admit constant factor approximations in the CONGEST model of distributed computing in a constant number of rounds on classes of sparse high-girth graphs. In this paper, sparse means bounded expansion, and high-girth means girth at least \(4r+2\). Our algorithm is quite simple; however, the proof of its approximation guarantee is non-trivial. To complement the algorithmic results, we show tightness of our approximation by providing a loosely matching lower bound on rings.

We study the d-Uniform Hypergraph Matching (d-UHM) problem: given an n-vertex hypergraph G where every hyperedge is of size d, find a maximum cardinality set of disjoint hyperedges. For \(d\ge 3\), the problem of finding the maximum matching is NP-complete, and was one of Karp’s 21 NP-complete problems. In this paper we are interested in the problem of finding matchings in hypergraphs in the massively parallel computation (MPC) model that is a common abstraction of MapReduce-style computation. In this model, we present the first three parallel algorithms for d-Uniform Hypergraph Matching, and we analyse them in terms of resources such as memory usage, rounds of communication needed, and approximation ratio. The highlights include

Standard grammatical evolution (GE) uses a one-point crossover (“ripple crossover”) that exchanges codons between two genotypes. The two resulting genotypes are then mapped to their respective phenotypes using a Backus-Naur form grammar. This article studies how different types of grammars affect the resulting individuals of a ripple crossover. We distinguish different grammars based on the expected number of non-terminals chosen when mapping genotype codons to phenotypes, \(B_{avg}\). The grammars only differ in \(B_{avg}\) but can express the same phenotypes. We perform crossover operations on the genotypes and find that grammars with \(B_{avg} > 1\) lead to high numbers of either very small trees or invalid individuals. Due to the re-sampling of the invalid individuals, the algorithmic runtime is higher compared to grammars with a small \(B_{avg}\), despite being able to express the same phenotypes. In grammars with \(B_{avg} \le 1\), the bias towards small trees is reduced and instead, the frequency of valid large trees is increased. Our results give insights on favorable grammar designs and underline the central role of grammar design in GE.

Using the Carlson–Simpson theorem, we give a new general condition for a structure in a finite binary relational language to have finite big Ramsey degrees.

Assume that we inspect a specimen represented as a collection of points. The points are typically organized on a grid structure in 2D- or 3D-space, and each point has an associated physical value. The goal of the inspection is to determine these values. Yet, measuring these values directly (by surgical probes) may damage the specimen or is simply impossible. The alternative is to employ aggregate measuring techniques (e.g., CT or MRI), whereby measurements are taken over subsets of points, and the exact values at each point are subsequently extracted by computational methods. In the Minimum Surgical Probing problem (MSP) the inspected specimen is represented by a graph G and a vector \(\ell \in \mathbb {R}^n\) that assigns a value \(\ell _i\) to each vertex i. An aggregate measurement (called probe) centered at vertex i captures its entire neighborhood, i.e., the outcome of a probe centered at i is \(\mathcal{P}_i = \sum _{j \in N(i) \cup \{i\}} \ell _j\) where N(i) is the open neighborhood of vertex i. Bar-Noy et al. [4] gave a criterion whether the vector \(\ell \) can be recovered from the collection of probes \(\mathcal{P}= \{\, \mathcal{P}_v \; | \; v \in V(G)\}\) alone. However, there are graphs where \(\mathcal{P}\) is inconclusive, i.e., there are several vectors \(\ell \) that are consistent with \(\mathcal{P}\). In these cases, we are allowed to use surgical probes. A surgical probe at vertex i returns \(\ell _i\). The objective of MSP is to recover \(\ell \) from \(\mathcal{P}\) and G using as few surgical probes as possible.

A rectangular dual of a graph g is a contact representation of g by axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. The partial representation extension problem for rectangular duals asks whether a given partial rectangular dual can be extended to a rectangular dual, that is, whether there exists a rectangular dual where some vertices are represented by prescribed rectangles. Combinatorially, a rectangular dual can be described by a regular edge labeling (rel), which determines the orientations of the rectangle contacts. We characterize the rels that admit an extension, which leads to a linear-time testing algorithm. In the affirmative, we can construct an extension in linear time.keywordsrectangular dualpartial representation extension.

We prove a complexity dichotomy theorem for a class of Holant problems on 3-regular bipartite graphs. Given an arbitrary nonnegative weighted symmetric constraint function \(f = [x_0, x_1, x_2, x_3]\), we prove that the bipartite Holant problem \({\text {Holant}}\left( f\mid (=_3)\right) \) is either computable in polynomial time or #P-hard. The dichotomy criterion on f is explicit.

A 1-bend boundary labelling problem consists of an axis-aligned rectangle B, n points (called sites) in the interior, and n points (called ports) on the labels along the boundary of B. The goal is to find a set of n axis-aligned curves (called leaders), each having at most one bend and connecting one site to one port, such that the leaders are pairwise disjoint. A 1-bend boundary labelling problem is k-sided (\(1\le k\le 4\)) if the ports appear on k different sides of B. Kindermann et al. [Algorithmica, 76(1): 225–258, 2016] showed that the 1-bend 4-sided and 3-sided boundary labelling problems can be solved in \(O(n^9)\) and \(O(n^4)\) time, respectively. Bose et al. [SWAT, 12:1–12:14, 2018] improved the former running time to \(O(n^6)\) by reducing the problem to computing maximum independent set in an outerstring graph. In this paper, we improve both previous results by giving new algorithms with running times \(O(n^5)\) and \(O(n^3\log n)\) to solve the 1-bend 4-sided and 3-sided boundary labelling problems, respectively.

A well-known conjecture by Erdős states that every triangle-free graph on n vertices can be made bipartite by removing at most \(n^2/25\) edges. This conjecture was known for graphs with edge density at least 0.4 and edge density at most 0.172. Here, we will extend the edge density for which this conjecture is true; we prove the conjecture for graphs with edge density at most 0.2486 and for graphs with edge density at least 0.3197. Further, we prove that every triangle-free graph can be made bipartite by removing at most \(n^2/23.5\) edges improving the previously best bound of \(n^2/18\).

We study when (dual) Vandermonde systems of the form \(\mathbf {V} _T^{{(\intercal )}} \cdot \mathbf {z} = s\cdot \mathbf {w}\) admit a solution \(\mathbf {z}\) over a ring \(\mathcal {R}\), where \(\mathbf {V} _T\) is the Vandermonde matrix defined by a set T and where the “slack” s is a measure of the quality of solutions. To this end, we propose the notion of (s, t)-subtractive sets over a ring \(\mathcal {R}\), with the property that if S is (s, t)-subtractive then the above (dual) Vandermonde systems defined by any t-subset \(T \subseteq S\) are solvable over \(\mathcal {R}\). The challenge is then to find large sets S while minimising (the norm of) s when given a ring \(\mathcal {R}\).

We give the first $2$-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than $2$ is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true twins, with a novel construction of a 'good' cost function on the vertices at distance at most $2$ from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem., Comment: 23 pages, 3 figures

We study a primitive vehicle routing-type problem in which a fleet of n unit speed robots start from a point within a non-obtuse triangle \(\Delta \), where \(n \in \{1,2,3\}\). The goal is to design robots’ trajectories so as to visit all edges of the triangle with the smallest visitation time makespan. We begin our study by introducing a framework for subdividing \(\Delta \) into regions with respect to the type of optimal trajectory that each point P admits, pertaining to the order that edges are visited and to how the cost of the minimum makespan \(R_n(P)\) is determined, for \(n\in \{1,2,3\}\). These subdivisions are the starting points for our main result, which is to study makespan trade-offs with respect to the size of the fleet. In particular, we define \(\mathscr {R}_{n,m} (\Delta )= \max _{P \in \Delta } R_n(P)/R_m(P)\), and we prove that, over all non-obtuse triangles \(\Delta \): (i) \(\mathscr {R}_{1,3}(\Delta )\) ranges from \(\sqrt{10}\) to 4, (ii) \(\mathscr {R}_{2,3}(\Delta )\) ranges from \(\sqrt{2}\) to 2, and (iii) \(\mathscr {R}_{1,2}(\Delta )\) ranges from 5/2 to 3. In every case, we pinpoint the starting points within every triangle \(\Delta \) that maximize \(\mathscr {R}_{n,m} (\Delta )\), as well as we identify the triangles that determine all \(\inf _\Delta \mathscr {R}_{n,m}(\Delta )\) and \(\sup _\Delta \mathscr {R}_{n,m}(\Delta )\) over the set of non-obtuse triangles.

An independent set S in a graph G is k-swap optimal if there is no independent set \(S'\) such that \(|S'|>|S|\) and \(|(S'\setminus S)\cup (S\setminus S')|\le k\). Motivated by applications in data reduction, we study whether we can determine efficiently if a given vertex v is contained in some k-swap optimal independent set or in all k-swap optimal independent sets. We show that these problems are NP-hard for constant values of k even on graphs with constant maximum degree. Moreover, we show that the problems are \(\mathrm {\Sigma ^{\text {P}}_{2}} \)-hard when k is not constant, even on graphs of constant maximum degree. We obtain similar hardness results for determining whether an edge is contained in a k-swap optimal max cut. Finally, we consider a certain type of edge-swap neighborhood for the Longest Path problem. We show that for a given edge we can decide in \(f(\varDelta +k)\cdot n^{\mathcal {O}(1)}\) time whether it is in some k-optimal path.

In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It was proved by Hasemann, Hirvonen, Rybicki and Suomela (2016) that for every real $\alpha>1$ and integer $\Delta$, a fractional coloring of total weight at most $\alpha(\Delta+1)$ can be obtained deterministically in a single round in graphs of maximum degree $\Delta$, in the LOCAL model of computation. However, a major issue of this result is that the output of each vertex has unbounded size. Here we prove that even if we impose the more realistic assumption that the output of each vertex has constant size, we can find fractional colorings of total weight arbitrarily close to known tight bounds for the fractional chromatic number in several cases of interest. More precisely, we show that for any fixed $\epsilon > 0$ and $\Delta$, a fractional coloring of total weight at most $\Delta+\epsilon$ can be found in $O(\log^*n)$ rounds in graphs of maximum degree $\Delta$ with no $K_{\Delta+1}$, while finding a fractional coloring of total weight at most $\Delta$ in this case requires $\Omega(\log \log n)$ rounds for randomized algorithms and $\Omega( \log n)$ rounds for deterministic algorithms. We also show how to obtain fractional colorings of total weight at most $2+\epsilon$ in grids of any fixed dimension, for any $\epsilon>0$, in $O(\log^*n)$ rounds. Finally, we prove that in sparse graphs of large girth from any proper minor-closed family we can find a fractional coloring of total weight at most $2+\epsilon$, for any $\epsilon>0$, in $O(\log n)$ rounds., Comment: 16 pages, 2 figures. Full version of a paper accepted at SIROCCO 2021

Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk graph $G$ with at most $4\omega(G)$ colors, where $\omega(G)$ is the clique number of $G$. This improves upon a classical 3-approximation algorithm for this problem, for all unit-disk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unit-disk graph $G$ with at most $5.68\omega(G)+1$ colors in $O(\log^* n)$ rounds. This algorithm is based on a study of the local structure of unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph $G$ has average degree at most $4\omega(G)$, which would imply the existence of a $O(\log n)$ round algorithm coloring any unit-disk graph $G$ with (approximately) $4\omega(G)$ colors in the LOCAL model. We provide partial results towards this conjecture using Fourier-analytical tools., Comment: 25 pages, corrects a mistake in the proceedings version of the paper. A preliminary version of this work appeared in the proceedings of the 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2021)

For \(n\ge s> r\ge 1\) and \(k\ge 2\), write \(n \rightarrow (s)_{k}^r\) if every k-colouring of all r-subsets of an n-element set has a monochromatic subset of size s. Improving upon previous results by Axenovich et al. (Discrete Mathematics, 2014) and Erdős et al. (Combinatorial set theory, 1984) we show that $$ \text {if } r \ge 3 \text { and } n \nrightarrow (s)_k^r \text { then } 2^n \nrightarrow (s+1)_{k+3}^{r+1}. $$ This yields an improvement for some of the known lower bounds on multicolour hypergraph Ramsey numbers.

Graph routing problem (GRP) and its generalizations have been extensively studied because of their broad applications in the real world. In this paper, we study a variant of GRP called the general cluster routing problem (GCRP). Let \(G=\left( V,\,E\right) \) be a complete undirected graph with edge weight \(c\left( e\right) \) satisfying the triangle inequality. The vertex set is partitioned into a family of clusters \(C_{1},...,C_{m}\). We are given a required vertex subset \(\overline{V} \subseteq V\) and a required edge subset \(\overline{E} \subseteq E\). The aim is to compute a minimum cost tour that visits each vertex in \(\overline{V}\) exactly once and traverses each edge in \(\overline{E}\) at least once, while the vertices and edges of each cluster are visited consecutively. When the starting and ending vertices of each cluster are specified, we devise an approximation algorithm via incorporating Christofides’ algorithm with minimum weight bipartite matching, achieving an approximation ratio that equals the best approximation ratio of path TSP. Then for the case there are no specified starting and ending vertices for each cluster, we propose a more complicated algorithm with a compromised ratio of 2.67 by employing directed spanning tree against the designated auxiliary graph. Both approximation ratios improve the state-of-art approximation ratio that are respectively 2.4 and 3.25.

Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices \((u,v),|f (u) - f (v)| \ge p\) if u and v are adjacent, and \(f(u) \ne f(v)\) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e.,\(\max _{u\in V}(f(u)) - \min _{u\in V}(f(u))+1\)). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

In this paper we consider the multi-budget maximum weighted coverage problem, a generalization of the classical maximum coverage problem, where we are given k budgets, a set X of elements, and a set \(\mathcal {S}\) of bins where any \(S \in \mathcal {S}\) is a subset of elements of X. Each bin S has its own cost, and each element its own weight. An outcome is a vector \(O=(O_1, \dots , O_k)\) where each budget \(b_i\), for \(i=1,\dots , k\), can be used to buy a subset of bins \(O_i \subseteq \mathcal {S}\) of overall cost at most \(b_i\). The objective is to maximize the total weight which is defined as the sum of the weights of the elements bought with the budgets.

Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k-Partition with slack s, denoted (k, s)-BCP, is a partition of V(G) into k nonempty subsets, of sizes \(n_1,\ldots , n_k\) with \(|n_i-n/k|\le s\), each of which induces a connected subgraph (when \(s=0\), the k parts are perfectly balanced, and we call it k-BCP for short).

We consider minimum-cardinality Manhattan connected sets with arbitrary demands: Given a collection of points P in the plane, together with a subset of pairs of points in P (which we call demands), find a minimum-cardinality superset of P such that every demand pair is connected by a path whose length is the \(\ell _1\)-distance of the pair. This problem is a variant of three well-studied problems that have arisen in computational geometry, data structures, and network design: (i) It is a node-cost variant of the classical Manhattan network problem, (ii) it is an extension of the binary search tree problem to arbitrary demands, and (iii) it is a special case of the directed Steiner forest problem. Since the problem inherits basic structural properties from the context of binary search trees, an \(O(\mathrm {log}\;n)\)-approximation is trivial. We show that the problem is NP-hard and present an \(O(\sqrt{\mathrm {log}\;n})\)-approximation algorithm. Moreover, we provide an \(O(\mathrm {log}\;\mathrm {log}\;n)\)-approximation algorithm for complete k-partite demands as well as improved results for unit-disk demands and several generalizations. Our results crucially rely on a new lower bound on the optimal cost that could potentially be useful in the context of BSTs.

Given a class of graphs \(\mathcal {G}\) and a graph \(G = (V,E)\), the aim of the \(\mathcal {G}\) -completion problem is to find a set of at most k non-edges whose addition in G results in a graph that belongs to \(\mathcal {G}\). Completion to chordal or to natural subclasses of chordal graphs cover a broad range of classical NP-Complete problems, that have been extensively studied. When \(\mathcal {G}\) coincides with the class of chordal graphs, the problem is the well-known Minimum Fill-In problem. Other notable examples include completion to proper interval, threshold or trivially perfect graphs. Aforementioned problems are known to admit polynomial kernels, and it has been conjectured that completion to subclasses of chordal graphs further characterized by a finite number of forbidden induced subgraphs admits polynomial kernels. We investigate this line of research by considering completion to an important subclass of chordal graphs, namely chordal distance-hereditary graphs. Chordal distance-hereditary graphs are a natural generalization of trivially perfect graphs and have been extensively studied from the structural viewpoint. However, to the best of our knowledge, completion to chordal distance-hereditary graphs has not received attention so far. We thus initiate the first algorithmic study of this problem, and prove its NP-Completeness and that it admits a kernel with \(O(k^4)\) vertices. To that aim, we rely on several known characterizations of chordal distance-hereditary graphs. In particular, such graphs admit a tree-like decomposition, so-called clique laminar tree. Unlike all aforementioned subclasses of chordal graphs, this decomposition does not correspond to a partition of the vertex set at hand. To circumvent this, we propose an approach based on the notion of clique (minimal) separator decomposition and a new characterization of chordal distance-hereditary graphs that might be of independent interest.

Let \(\varSigma \) and \(\varPi \) be disjoint alphabets, respectively called the static alphabet and the parameterized alphabet. Two strings x and y over \(\varSigma \cup \varPi \) of equal length are said to parameterized match (p-match) if there exists a renaming bijection f on \(\varSigma \) and \(\varPi \) which is identity on \(\varSigma \) and maps the characters of x to those of y so that the two strings become identical. The indexing version of the problem of finding p-matching occurrences of a given pattern in the text is a well-studied topic in string matching. In this paper, we present a state-of-the-art indexing structure for p-matching called the parameterized suffix tray of an input text T, denoted by \(\mathsf {PSTray}(T)\). We show that \(\mathsf {PSTray}(T)\) occupies O(n) space and supports pattern matching queries in \(O(m + \log (\sigma +\pi ) + occ )\) time, where n is the length of t, m is the length of a query pattern P, \(\pi \) is the number of distinct symbols of \(|\varPi |\) in T, \(\sigma \) is the number of distinct symbols of \(|\varSigma |\) in T and \( occ \) is the number of p-matching occurrences of P in T. We also present how to build \(\mathsf {PSTray}(T)\) in O(n) time from the parameterized suffix tree of T.

We consider the graph k-partitioning problem under the min-max objective, termed as \(\textsc {Minmax}\;k\text {-}\textsc {cut}\). The input here is a graph \(G=(V,E)\) with non-negative edge weights \(w:E\rightarrow \mathbb {R}_+\) and an integer \(k\ge 2\) and the goal is to partition the vertices into k non-empty parts \(V_1, \ldots , V_k\) so as to minimize \(\max _{i=1}^k w(\delta (V_i))\). Although minimizing the sum objective \(\sum _{i=1}^k w(\delta (V_i))\), termed as \(\textsc {Minsum}\;k\text {-}\textsc {cut}\), has been studied extensively in the literature, very little is known about minimizing the max objective. We initiate the study of \(\textsc {Minmax}\;k\text {-}\textsc {cut}\) by showing that it is NP-hard and W[1]-hard when parameterized by k, and design a parameterized approximation scheme when parameterized by k. The main ingredient of our parameterized approximation scheme is an exact algorithm for \(\textsc {Minmax}\;k\text {-}\textsc {cut}\) that runs in time \((\lambda k)^{O(k^2)}n^{O(1)}\), where \(\lambda \) is the value of the optimum and n is the number of vertices. Our algorithmic technique builds on the technique of Lokshtanov, Saurabh, and Surianarayanan (FOCS, 2020) who showed a similar result for \(\textsc {Minsum}\;k\text {-}\textsc {cut}\). Our algorithmic techniques are more general and can be used to obtain parameterized approximation schemes for minimizing \(\ell _p\)-norm measures of k-partitioning for every \(p\ge 1\).

An oriented r-coloring of an oriented graph G corresponds to an oriented graph H on r vertices, such that there exists a homomorphism from G to H. The problem of deciding whether an acyclic digraph allows an oriented 4-coloring is already NP-hard. The oriented chromatic number of an oriented graph G is the smallest integer r such that G allows an oriented r-coloring.

We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain R of normalized dimensions of 1 and \(\rho \ge 1\), and distances are measured according to the Manhattan metric. We show that the family of balanced configurations (in which the Voronoi cells of individual facilities are equalized with respect to geometric properties) is richer in this metric than for Euclidean distances. Our main result considers the One-Round Voronoi Game with Manhattan distances, in which first player White and then player Black each place n points in R; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if \(\rho \ge n\); for all other cases, we present a winning strategy for Black.

We consider the multi-broadcast problem in arbitrary connected radio networks consisting of n nodes. There are k designated source nodes for some fixed \(k \in \{1,\ldots ,n\}\), and each source node has a piece of information that it wants to share with all nodes in the network. We set out to determine the shortest possible labels so that multi-broadcast can be solved deterministically in the labeled radio network by some deterministic distributed algorithm. First, we show that every radio network G with maximum degree \(\varDelta \) can be labeled using \(O(\min \{\log k,\log \varDelta \})\)-bit labels in such a way that multi-broadcast with k sources can be accomplished. This bound is tight for certain network topologies (e.g., complete graphs), but there are networks where significantly shorter labels are sufficient, e.g., we show how to construct a tree with maximum degree \(\varTheta (\sqrt{n})\) in which gossiping (i.e., multi-broadcast with n sources) can be solved after labeling each node with O(1) bits. For all trees, we provide a labeling scheme and algorithm that will solve gossiping, and, we prove an impossibility result that demonstrates that our labeling scheme is optimal for gossiping in each tree. In particular, we prove that \(\varTheta (\log D(G))\)-bit labels are necessary and sufficient in each tree G, where D(G) denotes the distinguishing number of G.

The Maximal Independent Set problem is a well-studied problem in the distributed community. We study Maximum and Maximal Independent Set problems on two geometric intersection graphs; interval graphs and axis-parallel segment intersection graphs, and present deterministic distributed algorithms in the local communication model. We compute the maximum independent set on interval graphs in O(k) rounds and O(n) messages, where k is the size of the maximum independent set and n is the number of nodes in the graph. We provide a matching lower bound of \(\varOmega (k)\) on the number of rounds whereas \(\varOmega (n)\) is a trivial lower bound on message complexity. Thus our algorithm is both time and message optimal. We also study the maximal independent set problem in bi-interval graphs, a special case of the interval graphs where the intervals have two different lengths. We prove that a maximal independent set can be computed in bi-interval graphs in constant rounds that is \(\frac{1}{6}\)-approximation. For axis-parallel segment intersection graphs, we design an algorithm that finds a maximal independent set in O(D) rounds, where D is the diameter of the graph. We further show that this independent set is a \(\frac{1}{2}\)-approximation. The results in this paper extend the results of Molla et al. [J. Parallel Distrib. Comput. 2019].

We study the lifted multicut problem restricted to trees, which is np-hard in general and solvable in polynomial time for paths. In particular, we characterize facets of the lifted multicut polytope for trees defined by the inequalities of a canonical relaxation. Moreover, we present an additional class of inequalities associated with paths that are facet-defining. Taken together, our facets yield a complete totally dual integral description of the lifted multicut polytope for paths. This description establishes a connection to the combinatorial properties of alternative formulations such as sequential set partitioning.

This paper addresses the minmax regret 1-sink location problem on dynamic flow path networks with parametric weights. We are given a dynamic flow network consisting of an undirected path with positive edge lengths, positive edge capacities, and nonnegative vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. We consider the problem of locating a sink in the network, to which all the people evacuate from the vertices as quickly as possible. In our model, each weight is represented by a linear function in a common parameter t, and the decision maker who determines the location of a sink does not know the value of t. We formulate the sink location problem under such uncertainty as the minmax regret problem. Given t and a sink location x, the cost of x under t is the sum of arrival times at x for all the people determined by t. The regret for x under t is the gap between the cost of x under t and the optimal cost under t. The task of the problem is formulated as the one to find a sink location that minimizes the maximum regret over all t. For the problem, we propose an \(O(n^4 2^{\alpha (n)} \alpha (n) \log n)\) time algorithm where n is the number of vertices in the network and \(\alpha (\cdot )\) is the inverse Ackermann function. Also for the special case in which every edge has the same capacity, we show that the complexity can be reduced to \(O(n^3 2^{\alpha (n)} \alpha (n) \log n)\).

We introduce a C∗-algebra \({\mathcal A}_V\) of a variety V over the number field K and a C∗-algebra \({\mathcal A}_G\) of a reductive group G over the ring of adeles of K. Using Pimsner’s Theorem, we construct an embedding \({\mathcal A}_V\hookrightarrow {\mathcal A}_G\), where V is a G-coherent variety, e.g. the Shimura variety of G. The embedding is an analog of the Langlands reciprocity for C∗-algebras. It follows from the K-theory of the inclusion \({\mathcal A}_V\subset {\mathcal A}_G\) that the Hasse-Weil L-function of V is a product of the automorphic L-functions corresponding to irreducible representations of the group G.

The Commutative Supersingular Isogeny Diffie-Hellman key exchange (CSIDH) uses supersingular elliptic curves of Montgomery form over \(\mathbb {F}_p\) with \(p\equiv 3\) \((\mathrm{mod}\) 8), while CSURF considered those of Montgomery\(^-\) form with \(p\equiv 7\) \((\mathrm{mod}\) 8). The two protocols both have ratio (1:1) between the coefficients and the \(\mathbb {F}_p\)-isomorphism classes. Castryck and Decru showed that the ratio became (2:1) when Montgomery supersingular curves with endomorphism ring \(\mathbb {Z}[(1+\sqrt{-p})/2]\) and \(p\equiv 7\) \((\mathrm{mod}\) 8) were considered. The fact that the coefficients are not unique for each \(\mathbb {F}_p\)-isomorphism class is the major obstacle to use this case in the scheme.

The notion of first order convergence of graphs unifies the notions of convergence for sparse and dense graphs. Nesetřil and Ossona de Mendez [J. Symbolic Logic 84 (2019), 452–472] proved that every first order convergent sequence of graphs from a nowhere-dense class of graphs has a modeling limit and conjectured the existence of such modeling limits with an additional property, the strong finitary mass transport principle. The existence of modeling limits satisfying the strong finitary mass transport principle was proved for first order convergent sequences of trees by Nesetřil and Ossona de Mendez [Electron. J. Combin. 23 (2016), P2.52] and for first order sequences of graphs with bounded path-width by Gajarský et al. [Random Structures Algorithms 50 (2017), 612–635]. We establish the existence of modeling limits satisfying the strong finitary mass transport principle for first order convergent sequences of graphs with bounded tree-width.