WALCOM: Algorithms and Computation

We show that in any digraph on an underlying connected graph with non-negative weights on its edges, there is a Majority Spanning Tree for which sum of weights of edges of a fundamental cutset, running along each edge of the spanning tree determining the cutset, is not less than sum of those running in opposite direction. Similarly, there is a Majority Cotree, each fundamental cycle of which has non-negative weight. We further prove simultaneous existence of majority spanning trees and majority cotrees in any non-negative weighted digraph. We have shown how these structures can be used to solved scheduling transports by minimizing sum of weighted connection times, ranking round-robin tournaments by minimizing number of upsets, in settling multiple debts and in construction of transport networks with unbalanced road capacity.

This paper considers a transportation problem which is different from the conventional model. Suppose we are given many storages (nodes) to store multiple kinds of commodities together with roads (edges) interconnecting them, which are specified as a weighted graph. Some storages have surplus and others have shortages. Problem is to determine whether there are transportations to eliminate all of shortages. For transportation we can use a vehicle with the loading capacity at each node. Each vehicle visits one of its neighbors with some commodities which are unloaded at the neighbor. Then, we load some other commodities there, and then bring them back to the original node. How to design such send-and-bring-back transportations to eliminate all shortages is the problem. When we define a single round of transportations to be a set of those transportations at all nodes, whether there is a single round of valid transportations that eliminate all of shortages is our concern. After proving NP-completeness of the problem we present a linear time algorithm for a special case where an input graph is a forest.

We consider the problem of computing the diameter of a unicycle graph (i.e., a graph with a unique cycle). We present an O(n) time algorithm for the problem, where n is the number of vertices of the graph. This improves the previous best \(O(n\log n)\) time solution [Oh and Ahn, ISAAC 2016]. Using this algorithm as a subroutine, we solve the problem of adding a shortcut to a tree so that the diameter of the new graph (which is a unicycle graph) is minimized; our algorithm takes \(O(n^2\log n)\) time and O(n) space. The previous best algorithms solve the problem in \(O(n^2\log ^3 n)\) time and O(n) space [Oh and Ahn, ISAAC 2016], or in \(O(n^2)\) time and \(O(n^2)\) space [Bilò, ISAAC 2018].

Temporal graphs equip their directed edges with a departure time and a duration, which allows to model a surprisingly high number of real-world problems. Recently, Wu et al. have shown that a fastest path in a temporal graph G from a given vertex s to a vertex z can be computed in near-linear time, where a fastest path is one that minimizes the arrival time at z minus the departure time at s.

Here, we consider the natural problem of computing a fastest path from s to z that is in addition short, i.e. minimizes the sum of durations of its edges; this maximizes the total amount of spare time at stops during the journey. Using a new dominance relation on paths in combination with lexicographic orders on the departure and arrival times of these paths, we derive a near-linear time algorithm for this problem with running time \(O(n + m \log p(G))\), where \(n := |V(G)|\), \(m := |E(G)|\) and p(G) is upper bounded by both the maximum in-degree and the maximum edge duration of G.

The dominance relation is interesting in its own right, and may be of use for several related problems like fastest paths with minimum fare, fastest paths with minimum number of stops, and other pareto-optimal path problems in temporal graphs.

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)\).

Assume that \(m \ge 1\) autonomous mobile agents and \(0 \le b \le m\) single-agent transportation devices (called bikes) are initially placed at the left endpoint 0 of the unit interval [0, 1]. The agents are identical in capability and can move at speed one. The bikes cannot move on their own, but any agent riding bike i can move at speed \(v_i > 1\). An agent may ride at most one bike at a time. The agents can cooperate by sharing the bikes; an agent can ride a bike for a time, then drop it to be used by another agent, and possibly switch to a different bike.

We study two problems. In the Bike Sharing problem, we require all agents and bikes starting at the left endpoint of the interval to reach the end of the interval as soon as possible. In the Relaxed Bike Sharing problem, we aim to minimize the arrival time of the agents; the bikes can be used to increase the average speed of the agents, but are not required to reach the end of the interval.

Our main result is the construction of a polynomial time algorithm for the Bike Sharing problem that creates an arrival-time optimal schedule for travellers and bikes to travel across the interval. For the Relaxed Bike Sharing problem, we give an algorithm that gives an optimal solution for the case when at most one of the bikes can be abandoned.

Consider a situation, known as Secret Santa, where n players wish to exchange gifts such that each player receives exactly one gift and no one receives a gift from oneself. Each player only wants to know in advance for whom he/she should purchase a gift. That is, the players want to generate a hidden uniformly distributed random derangement. (Note that a permutation without any fixed points is called a derangement.) To solve this problem, in 2015, Ishikawa et al. proposed a simple protocol with a deck of physical cards. In their protocol, players first prepare n piles of cards, each of which corresponds to a player, and shuffle the piles. Subsequently, the players verify whether the resulting piles have fixed points somehow: If there is no fixed point, the piles serve as a hidden random derangement; otherwise, the players restart the shuffle process. Such a restart occurs with a probability of approximately 0.6. In this study, we consider how to decrease the probability of the need to restart the shuffle based on the aforementioned protocol. Specifically, we prepare more piles of cards than the number n of players. This potentially helps us avoid repeating the shuffle, because we can remove fixed points even if they arise (as long as the number of remaining piles is at least n). Accordingly, we propose an efficient protocol that generates a uniformly distributed random derangement. The probability of the need to restart the shuffle can be reduced to approximately 0.1.

A group with n elements can be stored using \(\mathcal {O}(n^2)\) space via its Cayley table which can answer a group multiplication query in \(\mathcal {O}(1)\) time. Information theoretically it needs \(\varOmega (n\log n)\) bits or \(\varOmega (n)\) words in word-RAM model just to store a group (Farzan and Munro, ISSAC 2006).

For functions \(s,t:\mathbb {N}\longrightarrow \mathbb {R}_{\ge 0}\), we say that a data structure is an \((\mathcal {O}(s),\mathcal {O}(t))\)-data structure if it uses \(\mathcal {O}(s)\) space and answers a query in \(\mathcal {O}(t)\) time. Except for cyclic groups it was not known if we can design \((\mathcal {O}(n),\mathcal {O}(1))\)-data structure for interesting classes of groups.

In this paper, we show that there exist \((\mathcal {O}(n),\mathcal {O}(1))\)-data structures for several classes of groups and for any ring and thus achieve information theoretic lower bound asymptotically. More precisely, we show that there exist \((\mathcal {O}(n),\mathcal {O}(1))\)-data structures for the following algebraic structures with n elements:

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.

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.

We study the variations of the geometric Red-Blue Set Cover (RBSC) problem in the plane using various geometric objects. We show that the RBSC problem with intervals on the real line is polynomial-time solvable. The problem is \(\mathsf {NP}\)-hard for rectangles anchored on two parallel lines and rectangles intersecting a horizontal line. The problem admits a polynomial-time algorithm for axis-parallel lines. However, if the objects are horizontal lines and vertical segments, the problem becomes \(\mathsf {NP}\)-hard. Further, the problem is \(\mathsf {NP}\)-hard for axis-parallel unit segments.

We introduce a variation of the Red-Blue Set Cover problem with the set system, the Special-Red-Blue Set Cover problem, and show that the problem is \(\mathsf {APX}\)-hard. We then show that several geometric variations of the problem with: (i) axis-parallel rectangles containing the origin in the plane, (ii) axis-parallel strips, (iii) axis-parallel rectangles that are intersecting exactly zero or four times, (iv) axis-parallel line segments, and (v) downward shadows of line segments, are \(\mathsf {APX}\)-hard by providing encodings of these problems as the Special-Red-Blue Set Cover problem. This is on the same line of the work by Chan and Grant [6], who provided the \(\mathsf {APX}\)-hardness results of the geometric set cover problem for the above classes of objects.

For a graph class \(\mathcal {C}\), the \(\mathcal {C}\)-Edge-Deletion problem asks for a given graph G to delete the minimum number of edges from G in order to obtain a graph in \(\mathcal {C}\). We study the \(\mathcal {C}\)-Edge-Deletion problem for \(\mathcal {C}\) the class of interval graphs and other related graph classes. It follows from Courcelle’s Theorem that these problems are fixed parameter tractable when parameterized by treewidth. In this paper, we present concrete FPT algorithms for these problems. By giving explicit algorithms and analyzing these in detail, we obtain algorithms that are significantly faster than the algorithms obtained by using Courcelle’s theorem.

We consider the min-max r-gathering problem described as follows: We are given a set of users and facilities in a metric space. We open some of the facilities and assign each user to an opened facility such that each facility has at least r users. The goal is to minimize the maximum distance between the users and the assigned facility. We also consider the min-max r-gather clustering problem, which is a special case of the r-gathering problem in which the facilities are located everywhere. In this paper, we study the tractability and the hardness when the underlying metric space is a spider, which answers the open question posed by Ahmed et al. [WALCOM’19]. First, we show that the problems are NP-hard even if the underlying space is a spider. Then, we propose FPT algorithms parameterized by the degree d of the center. This improves the previous algorithms because they are parameterized by both r and d. Finally, we propose PTASes to the problems. These are best possible because there are no FPTASes unless P = NP.

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.

Our algorithm runs in \(\mathcal {O}(f(k)n\log {n})\) too, but with a much smaller dependence on k. In our case, \(f(k) = 2^{\mathcal {O}(k)}\). This algorithm is simple and fast, especially for small values of k. We should mention that Bodlaender et al. [2016] have an asymptotically faster algorithm running in time \(2^{O(k)} n\). It relies on a very sophisticated data structure and does not claim to be useful for small values of k.

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.

In this paper we consider msp-digraphs (short for minimal series-parallel digraphs), which can be defined from the single vertex graph by applying the parallel composition and series composition. In order to show several results for coloring msp-digraphs, we introduce the concept of oriented colorings excluding homomorphisms to digraphs H with short cycles. A g-oriented r-coloring of an oriented graph G is a homomorphism from G to some digraph H on r vertices of girth at least \(g+1\). The g-oriented chromatic number of G is the smallest integer r such that G allows a g-oriented r-coloring.

As our main result we show that for every msp-digraph the g-oriented chromatic number is at most \(2^{g+1}-1\). We use this bound together with the recursive structure of msp-digraphs to give a linear time solution for computing the g-oriented chromatic number of msp-digraphs. This implies that every msp-digraph has oriented chromatic number at most 7. Furthermore, we conclude that the chromatic number of the underlying undirected graphs of msp-digraphs can be bounded by 3. Both bounds are best possible and the exact chromatic numbers can be computed in linear time. Finally, we conclude that k-power digraphs of msp-digraphs have oriented chromatic number at most \(2^{2k+1}-1\).

We revisit the maximal clique enumeration algorithm cliques by Tomita et al. that appeared in Theoretical Computer Science 2006. It is known to work in \(O(3^{n/3})\)-time in the worst-case for an n-vertex graph. In this paper, we extend the time-complexity analysis with respect to the maximum size and the number of maximal cliques, and to its delay, solving issues that were left as open problems since the original paper. In particular, we prove that cliques does not have polynomial delay, unless \(P=NP\), and that this remains true for any possible pivoting strategy, for both cliques and Bron-Kerbosch. As these algorithms are widely used and regarded as fast “in practice”, we are interested in observing their practical behavior: we run an evaluation of cliques and three Bron-Kerbosch variants on over 130 real-world and synthetic graphs, and observe how their performance seems far from its theoretical worst-case behavior in terms of both total time and delay.

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.

A matching is compatible to two or more labeled point sets of size n with labels \(\{1,\dots ,n\}\) if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with \(\lfloor \sqrt{2n}\rfloor \) edges. More generally, for any \(\ell \) labeled point sets we construct compatible matchings of size \(\varOmega (n^{1/\ell })\). As a corresponding upper bound, we use probabilistic arguments to show that for any \(\ell \) given sets of n points there exists a labeling of each set such that the largest compatible matching has \(\mathcal {O}(n^{2/(\ell +1)})\) edges. Finally, we show that \(\varTheta (\log n)\) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.

We study upward planar straight-line embeddings (UPSE) of directed trees on given point sets. The given point set S has size at least the number of vertices in the tree. For the special case where the tree is a path P we show that: (a) If S is one-sided convex, the number of UPSE s equals the number of maximal monotone paths in P. (b) If S is in general position and P is composed by three maximal monotone paths, where the middle path is longer than the other two, then it always admits an UPSE on S. We show that the decision problem of whether there exists an UPSE of a directed tree with n vertices on a fixed point set S of n points is NP-complete, by relaxing the requirements of the previously known result which relied on the presence of cycles in the graph, but instead fixing position of a single vertex. Finally, by allowing extra points, we guarantee that each directed caterpillar on n vertices and with k switches in its backbone admits an UPSE on every set of \(n 2^{k-2}\) points.

Let G be a planar graph whose vertices are colored either red or blue and let S be a set of points having as many red (blue) points as the red (blue) vertices of G. A 2-colored point-set embedding of G on S is a planar drawing that maps each red (blue) vertex of G to a red (blue) point of S. We show that there exist properly 2-colored graphs (i.e., 2-colored graphs with no adjacent vertices having the same color) having treewidth two whose point-set embeddings may require linearly many bends on linearly many edges. For a contrast, we show that two bends per edge are sufficient for 2-colored point-set embedding of properly 2-colored outerplanar graphs. For separable point sets this bound reduces to one, which is worst-case optimal. If the 2-coloring of the outerplanar graph is not proper, three bends per edge are sufficient and one bend per edge (which is worst-case optimal) is sufficient for caterpillars.

Given a connected vertex-weighted graph G, the maximum weight internal spanning tree (MaxwIST) problem asks for a spanning tree of G that maximizes the total weight of internal nodes. This problem is NP-hard and APX-hard, with the currently best known approximation factor 1/2 (Chen et al., Algorithmica 2019). For the case of claw-free graphs, Chen et al. present an involved approximation algorithm with approximation factor 7/12. They asked whether it is possible to improve these ratios, in particular for claw-free graphs and cubic graphs.

For cubic graphs we present an algorithm that computes a spanning tree whose total weight of internal vertices is at least \(\frac{3}{4}-\frac{3}{n}\) times the total weight of all vertices, where n is the number of vertices of G. This ratio is almost tight for large values of n. For claw-free graphs of degree at least three, we present an algorithm that computes a spanning tree whose total internal weight is at least \(\frac{3}{5}-\frac{1}{n}\) times the total vertex weight. The degree constraint is necessary as this ratio may not be achievable if we allow vertices of degree less than three.

With the above ratios, we immediately obtain better approximation algorithms with factors \(\frac{3}{4}-\epsilon \) and \(\frac{3}{5}-\epsilon \) for the MaxwIST problem in cubic graphs and claw-free graphs having no degree-2 vertices, for any \(\epsilon >0\). The new algorithms are short (compared to that of Chen et al.) and fairly simple as they employ a variant of the depth-first search algorithm. Moreover, they take linear time while previous algorithms for similar problem instances are super-linear.

Consider an information diffusion process on a graph G that starts with \(k>0\) burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as k other unburnt vertices. The k-burning number of G is the minimum number of steps \(b_k(G)\) such that all the vertices can be burned within \(b_k(G)\) steps. Note that the last step may have smaller than k unburnt vertices available, where all of them are burned. The 1-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to k-burning number allows us to examine different worst-case contagion scenarios by varying the spread factor k.

In this paper we prove that computing k-burning number is APX-hard, for any fixed constant k. We then give an \(O((n+m)\log n)\)-time 3-approximation algorithm for computing k-burning number, for any \(k\ge 1\), where n and m are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem.

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.

Ripple Effect is a logic puzzle with an objective to fill numbers into a rectangular grid divided into rooms. Each room must contain consecutive integers starting from 1 to its size. Also, if two cells in the same row or column have the same number x, the space separating the two cells must be at least x cells. In this paper, we propose a physical protocol of zero-knowledge proof for Ripple Effect puzzle using a deck of cards, which allows a prover to physically show that he/she knows a solution without revealing it. In particular, we develop a physical protocol that, given a secret number x and a list of numbers, verifies that x does not appear among the first x numbers in the list without revealing x or any number in the list.

We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished cycles on the graph. We are tasked with rearranging the tokens from a given initial configuration to a final one by using cyclic shift operations along the distinguished cycles. We first investigate a large class of graphs, which generalizes several classic puzzles, and we give a characterization of which final configurations can be reached from a given initial configuration. Our proofs are constructive, and yield efficient methods for shifting tokens to reach the desired configurations. On the other hand, when the goal is to find a shortest sequence of shifting operations, we show that the problem is NP-hard, even for puzzles with tokens of only two different colors.