Search

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with $n$ nodes and $m$ edges, outputs a classical description of an $\epsilon$-spectral sparsifier in sublinear time $\tilde{O}(\sqrt{mn}/\epsilon)$. This contrasts with the optimal classical complexity $\tilde{O}(m)$. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for $k$-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut., Comment: v2: several small improvements to the text. An extended abstract will appear in FOCS'20; v3: corrected a minor mistake in Appendix A; v4: final version as published in SICOMP

We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min–avg minimizes the average tour cost and min–max minimizes the maximum tour cost over all days. For min–max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min–avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

Given a set $P$ of $n$ points in $\mathbb{R}^2$ and an input line $\gamma$ in $\mathbb{R}^2$, we present an algorithm that runs in optimal $\Theta(n\log n)$ time and $\Theta(n)$ space to solve a restricted version of the $1$-Steiner tree problem. Our algorithm returns a minimum-weight tree interconnecting $P$ using at most one Steiner point $s \in \gamma$, where edges are weighted by the Euclidean distance between their endpoints. We then extend the result to $j$ input lines. Following this, we show how the algorithm of Brazil et al. ("Generalised k-Steiner Tree Problems in Normed Planes", arXiv:1111.1464) that solves the $k$-Steiner tree problem in $\mathbb{R}^2$ in $O(n^{2k})$ time can be adapted to our setting. For $k>1$, restricting the (at most) $k$ Steiner points to lie on an input line, the runtime becomes $O(n^{k})$. Next we show how the results of Brazil et al. ("Generalised k-Steiner Tree Problems in Normed Planes", arXiv:1111.1464) allow us to maintain the same time and space bounds while extending to some non-Euclidean norms and different tree cost functions. Lastly, we extend the result to $j$ input curves., Comment: 31 pages (26 of content), 4 figures (last one as 3 subfigures). Minor corrections since publication: notably our analysis of the Brazil et al. k-steiner tree algorithm in section 4.1 (results unchanged), and a correction to some corollary statements to correct the space usage. Also added short discussion of how the algorithm still works when the MST of the input point set is not unique

A graph database is a digraph whose arcs are labeled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose edges are labeled with regular expressions over the alphabet. RGPs model navigational queries for graph databases called conjunctive regular path queries (CRPQs). A match of a CRPQ in the database is witnessed by a special navigational homomorphism of the corresponding RGP to the database. We study the complexity of deciding the existence of a homomorphism between two RGPs. Such homomorphisms model a strong type of containment between the two corresponding CRPQs. We show that this problem can be solved by an EXPTIME algorithm (while general query containmement in this context is EXPSPACE-complete). We also study the problem for restricted RGPs over a unary alphabet, that arise from some applications like XPath or SPARQL. For this case, homomorphism-based CRPQ containment is in NP. We prove that certain interesting cases are in fact polynomial-time solvable., 15 pages. Short version appeared in the proceedings of the 15th Conference on Computability in Europe (CIE 2019)

We quantise Whitney’s construction to prove the existence of a triangulation for any$$C^2$$C2manifold, so that we get an algorithm with explicit bounds. We also give a new elementary proof, which is completely geometric.

In the $\varepsilon$-Consensus-Halving problem, a fundamental problem in fair division, there are $n$ agents with valuations over the interval $[0,1]$, and the goal is to divide the interval into pieces and assign a label "$+$" or "$-$" to each piece, such that every agent values the total amount of "$+$" and the total amount of "$-$" almost equally. The problem was recently proven by Filos-Ratsikas and Goldberg [2019] to be the first "natural" complete problem for the computational class PPA, answering a decade-old open question. In this paper, we examine the extent to which the problem becomes easy to solve, if one restricts the class of valuation functions. To this end, we provide the following contributions. First, we obtain a strengthening of the PPA-hardness result of [Filos-Ratsikas and Goldberg, 2019], to the case when agents have piecewise uniform valuations with only two blocks. We obtain this result via a new reduction, which is in fact conceptually much simpler than the corresponding one in [Filos-Ratsikas and Goldberg, 2019]. Then, we consider the case of single-block (uniform) valuations and provide a parameterized polynomial time algorithm for solving $\varepsilon$-Consensus-Halving for any $\varepsilon$, as well as a polynomial-time algorithm for $\varepsilon=1/2$. Finally, an important application of our new techniques is the first hardness result for a generalization of Consensus-Halving, the Consensus-$1/k$-Division problem [Simmons and Su, 2003]. In particular, we prove that $\varepsilon$-Consensus-$1/3$-Division is PPAD-hard., Journal version. Preliminary version appeared at EC '20

Metaheuristics are found to be efficient in different applications where the use of exact algorithms becomes short-handed. In the last decade, many of these algorithms have been introduced and used in a wide range of applications. Nevertheless, most of those approaches share similar components leading to a concern related to their novelty or contribution. Thus, in this paper, a pool template is proposed and used to categorize algorithm components permitting to analyze them in a structured way. We exemplify its use by means of continuous optimization metaheuristics, and provide some measures and methodology to identify their similarities and novelties. Finally, a discussion at a component level is provided in order to point out possible design differences and commonalities.

We show that there is a measure-preserving system $(X,\mathscr{B}, \mu, T)$ together with functions $F_0, F_1, F_2 \in L^{\infty}(\mu)$ such that the correlation sequence $C_{F_0, F_1, F_2}(n) = \int_X F_0 \cdot T^n F_1 \cdot T^{2n} F_2 d\mu$ is not an approximate integral combination of $2$-step nilsequences., Comment: 14 pages

We consider a swarm of mobile robots evolving in a bidimensional Euclidean space. We study a variant of the crash-tolerant gathering problem: if no robot crashes, robots have to meet at the same arbitrary location, not known beforehand, in finite time; if one or several robots crash at the same location, the remaining correct robots gather at the crash location to rescue them. Motivated by impossibility results in the semi-synchronous setting, we present the first solution to the problem for the fully synchronous setting that operates in the vanilla Look-Compute-Move model with no additional hypotheses: robots are oblivious, disoriented, have no multiplicity detection capacity, and may start from arbitrary positions (including those with multiplicity points). We furthermore show that robots gather in a time that is proportional to the initial maximum distance between robots., Comment: arXiv admin note: substantial text overlap with arXiv:2010.04400

Some real life processes, including molecular ones, are context-sensitive, in the sense that their outcome depends on side conditions that are most of the times difficult, or impossible, to express fully in advance. In this paper, we survey and discuss a logical account of context-sensitiveness in molecular processes, based on a kind of non-classical logic. This account also allows us to revisit the relationship between logic and philosophy of science (and philosophy of biology, in particular).

International audience; A temporal graph G is a sequence of static graphs indexed by a set of integers representing time instants. Given ∆ an integer, a ∆-module is a set of vertices A having the same neighbourhood outside of A for ∆ consecutive instants. We address specific cases of ∆-module enumeration, when |A| = 2 or when ∆ = ∞. Our main parameter for time complexity analysis is the history length τ = max{t : G t ∈ G not empty } − min{t : G t ∈ G not empty }. Using red-black tree data structure, we give solutions to above enumeration problems in time logarithmic in τ. For the general ∆-module enumeration problem, we give a pre-processing using overlapping properties of minimal ∆modules. Numerical analysis of our implementation on graphs collected from real world data scales up to a history length of 10 8 time instants 1. Keywords graph theory • historical data • modular decomposition • temporal graph Supported by Courtanet-Sorbonne Université convention C19.0665 and ANRT grant 2019.0485.

Knaster-Tarski’s theorem, characterising the greatest fix- point of a monotone function over a complete lattice as the largest post-fixpoint, naturally leads to the so-called coinduction proof principle for showing that some element is below the greatest fixpoint (e.g., for providing bisimilarity witnesses). The dual principle, used for showing that an element is above the least fixpoint, is related to inductive invariants. In this paper we provide proof rules which are similar in spirit but for showing that an element is above the greatest fixpoint or, dually, below the least fixpoint. The theory is developed for non-expansive monotone functions on suitable lattices of the form$$\mathbb {M}^Y$$MY, whereYis a finite set and$$\mathbb {M}$$Man MV-algebra, and it is based on the construction of (finitary) approximations of the original functions. We show that our theory applies to a wide range of examples, including termination probabilities, behavioural distances for probabilistic automata and bisimilarity. Moreover it allows us to determine original algorithms for solving simple stochastic games.

In the context of constant--dimension subspace codes, an important problem is to determine the largest possible size $A_q(n, d; k)$ of codes whose codewords are $k$-subspaces of $\mathbb{F}_q^n$ with minimum subspace distance $d$. Here in order to obtain improved constructions, we investigate several approaches to combine subspace codes. This allow us to present improvements on the lower bounds for constant--dimension subspace codes for many parameters, including $A_q(10, 4; 5)$, $A_q(12, 4; 4)$, $A_q(12, 6, 6)$ and $A_q(16, 4; 4)$., 17 pages; construction for A_(10,4;5) was flawed

Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: operators of a network and users of the network. Operators of the network post a price so as to attract users and maximize profit; users of the network select routes based on these prices and congestion from other users. Motivated by the fact that equilibrium in these games may not exist, may not be unique, and may induce an inefficient network performance, our main result is to observe that a simple regulation on the network owners’ market solves these three issues. Specifically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge, then the game among the link operators has a unique and strong Nash equilibrium and the users’ game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls and investigate the efficiency of great tolls with respect to the users’ surplus. We derive a bicriteria bound that compares the users’ surplus under great tolls with the users’ surplus under optimal tolls. Finally, we consider two different extensions of the model. First, we assume that operators face operating costs that depend on the amount of flow on the link, for which we prove existence of great tolls. Second, we allow operators to own more than one link. In this case, we prove that, when operators own complementary links (i.e., links for which an increase in toll value may only increase the flow on the other owned links), any toll vector that induces the optimal flow and that is upper bounded by the marginal tolls is a great set of tolls, and furthermore, we show that, when all links in the network are complementary, then the aforementioned toll vector is also a strong cap equilibrium.

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of $n$ disjoint growing squares. Our data structure uses $O(n (\log n \log\log n)^2)$ space, supports queries in worst case $O(\log^3 n)$ time, and updates in $O(\log^7 n)$ amortized time. This leads to an $O(n\alpha(n)\log^7 n)$ time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best $O(n^2)$ time algorithms., Comment: 14 pages, 7 figures

Approximate Matrix Multiplication (AMM) has emerged as a useful and computationally inexpensive substitute for actual multiplication of large matrices. Randomized as well as deterministic solutions to AMM were provided in the past. The latest work provides a deterministic algorithm that solves AMM more accurately than the other works. It is a streaming algorithm that is both fast and accurate. But, it is less robust to noise and is also liable to have less than optimal performance in the presence of concept drift in the input matrices. We propose an algorithm that is more accurate, robust to noise, invariant to concept drift in the data, while having almost the same running time as the state-of-the-art algorithm. We also prove that theoretical guarantees exist for the proposed algorithm. An empirical performance improvement of up to 90 % is obtained over the previous algorithm. We also propose a general framework for parallelizing the proposed algorithm. The two parallelized versions of the algorithm achieve up to 1.9 x and 3.6 x speedups over the original version of the proposed algorithm.

The directed power graph $$\vec {\mathcal {G}}( G)$$ of a group G is the simple digraph with vertex set G in which $$x\rightarrow y$$ if y is a power of x, and the power graph is the underlying simple graph $$\mathcal {G}( G)$$ . In this paper, three versions of the definition of the power graph are discussed, and it is proved that the power graph by any of the three versions of the definition determines the other two up to isomorphism. It is also proved that if G is a torsion-free group of nilpotency class 2 and if H is a group such that $$\mathcal {G}( H)\cong \mathcal {G}( G)$$ , then G and H have isomorphic directed power graphs, which was an open problem proposed by Cameron, Guerra and Jurina [9].

We study the probabilistic properties of reliable networks of minimum costs in d -dimensional Euclidean space, with reliability in terms of k -edge-connectivity in graphs. We show that this problem fits into Yukich’s framework for Euclidean functionals for arbitrary k , dimension d and distant-power gradient p with p d . With this framework, several theorems on convergence and concentration of the value of optimal solutions follow. These results are then extended to optimal k -edge-connected power assignment graphs, where we assign transmit power to nodes, and two nodes are connected if they both have sufficient transmit power. This variant models wireless networks. Finally, we devise a partitioning heuristic to find approximate solutions quickly, and we analyze its performance in the framework of smoothed analysis.

Random intersection graphs model networks with communities, assuming an underlying bipartite structure of groups and individuals, where these groups may overlap. Group memberships are generated through the bipartite configuration model. Conditionally on the group memberships, the classical random intersection graph is obtained by connecting individuals when they are together in at least one group. We generalize this definition, allowing for arbitrary community structures within the groups. In our new model, groups might overlap and they have their own internal structure described by a graph, the classical setting corresponding to groups being complete graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, derive the asymptotic degree distribution and the local clustering coefficient. These proofs rely on local weak convergence, which also implies that subgraph counts converge. We further exploit the connection to the bipartite configuration model, for which we also prove local weak convergence, and which is interesting in its own right., Comment: 34 pages, 12 figures

Given a complete graph with an even number of vertices, and with each edge colored with one of two colors (say red or blue), an equitable Hamiltonian cycle is a Hamiltonian cycle that can be decomposed into two perfect matchings such that both perfect matchings have the same number of red edges. We show that, for any coloring of the edges, in any complete graph on at least 6 vertices, an equitable Hamiltonian cycle exists.

In 2003 Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A $k$-assignment, $L$, for a graph $G$ assigns a list, $L(v)$, of $k$ available colors to each $v \in V(G)$, and an equitable $L$-coloring of $G$ is a proper coloring, $f$, of $G$ such that $f(v) \in L(v)$ for each $v \in V(G)$ and each color class of $f$ has size at most $\lceil |V(G)|/k \rceil$. In 2018, Kaul, Mudrock, and Pelsmajer subsequently introduced the List Equitable Total Coloring Conjecture which states that if $T$ is a total graph of some simple graph, then $T$ is equitably $k$-choosable for each $k \geq \max \{\chi_\ell(T), \Delta(T)/2 + 2 \}$ where $\Delta(T)$ is the maximum degree of a vertex in $T$ and $\chi_\ell(T)$ is the list chromatic number of $T$. In this paper we verify the List Equitable Total Coloring Conjecture for subdivisions of stars and the generalized theta graph., Comment: 16 pages

We take an elementary and systematic approach to the problem of extending the Tutte polynomial to the setting of embedded graphs. Four notions of embedded graphs arise naturally when considering deletion and contraction operations on graphs on surfaces. We give a description of each class in terms of coloured ribbon graphs. We then identify a universal deletion-contraction invariant (i.e., a `Tutte polynomial') for each class. We relate these to graph polynomials in the literature, including the Bollob\'as--Riordan, Krushkal, and Las Vergnas polynomials, and give state-sum formulations, duality relations, deleton-contraction relations, and quasi-tree expansions for each of them., Comment: This is the authors accepted manuscript / version of record with an unfortunate typo corrected on p24

We look at nondeterministic finite automata augmented with multiple reversal-bounded counters where, during an accepting computation, the behavior of the counters is specified by some fixed pattern. These patterns can serve as a useful "bridge" to other important automata and grammar models in the theoretical computer science literature, thereby helping in their study. Various pattern behaviors are considered, together with characterizations and comparisons. For example, one such pattern defines exactly the smallest full trio containing all the bounded semilinear languages. Another pattern defines the smallest full trio containing all the bounded context-free languages. The "bridging" to other families is then applied, e.g. to certain Turing machine restrictions, as well as other families. Certain general decidability properties are also studied using this framework., 28 pages, 1 figure

Meta-heuristics are powerful tools for solving optimization problems whose structural properties are unknown or cannot be exploited algorithmically. We propose such a meta-heuristic for a large class of optimization problems over discrete domains based on the particle swarm optimization (PSO) paradigm. We provide a comprehensive formal analysis of the performance of this algorithm on certain “easy” reference problems in a black-box setting, namely the sorting problem and the problem OneMax. In our analysis we use a Markov model of the proposed algorithm to obtain upper and lower bounds on its expected optimization time. Our bounds are essentially tight with respect to the Markov model. We show that for a suitable choice of algorithm parameters the expected optimization time is comparable to that of known algorithms and, furthermore, for other parameter regimes, the algorithm behaves less greedy and more explorative, which can be desirable in practice in order to escape local optima. Our analysis provides a precise insight on the tradeoff between optimization time and exploration. To obtain our results we introduce the notion of indistinguishability of states of a Markov chain and provide bounds on the solution of a recurrence equation with non-constant coefficients by integration.

This archive contains the raw evaluation results and scripts associated with the experiments described in the article "Making Higher-Order Superposition Work" by Vukmirović, Bentkamp, Blanchette, Cruanes, Nummelin and Tourret available at: https://matryoshka-project.github.io/pubs/mhosw_article.pdf The problems we used for the evaluation are in problems/ subdirectory, divided in categories sh and tptp as in the article. In the results/ directory there are two subdirectories, sh and tptp, one for each benchmark category. Both subdirectories contain files named fD.csv where D is a number from 1 to 10. The files contain experiment results for the figure labelled with the number D, and the benchmark category corresponding to the parent directory. In the result files, the columns give the results of the experiment run for a given prover configuration (e.g., CPU time, reported status, memory usage, etc.). Each row corresponds to one problem file, whose name is given in the "prob_name" column. The "i_solver" column corresponds to a prover, whereas the "i_configuration" column corresponds to a configuration, where i is a natural number identifying a combination of prover and configuration. Files ending with "summary.csv" contain concise summaries of evaluation runs for a corresponding results file. Columns of these files are of the form "{solver}_{configuration}", and rows contain different statistics described in the "summary" column. The names of the solvers and configurations used in result files are self-explanatory (for DCS, DCI and IC configurations presence of av in the name of the configuration denotes that Avatar is enabled). In some cases, for uniformity, configurations are used in multiple figures. We used the following versions of higher-order provers: CVC4 1.9 ([git cascJ10 db26022c]), Leo-III 1.5.6, Satallax 3.5, Vampire 4.5.1 (commit 68d3e7314), E 2.7 (603992156b943171002cacca72aa3f2d0a211ee3). The "zipperposition/" directory contains the scripts that can be used to run the provided Zipperposition binary (compiled for Linux) on a given problem using a given configuration. To run Zipperposition on a single problem using some configuration, use the scripts with the name "run_*", where * stands for the configuration used in the evaluation. The configuration names match those used in the result files. Except for "run_coop" and "run_uncoop", scripts accept three arguments: 1) path to the problem 2) CPU timeout 3) path to the temporary directory for files used to communicate with Ehoh. "run_coop" and "run_uncoop" expect only the first two arguments For example, to run problem with the path ~/problem.p using configuration which enables PEHO priority function for up to 15 seconds execute ./run_prio_peho ~/problem.p 15 /tmp Working installation of Python 3 and bash is required. Source code for Zipperposition can be obtained from the wip-merge-hlbe branch of Zipperposition git repository: git@github.com:sneeuwballen/zipperposition.git. The binary stored under scripts/ directory corresponds to compiled sources tagged with commit hash 8d205ecf8869c76dcfdf0c1faa98b002226780a1. Compilation instructions are as in README.md file contained in the git repository. As noted in footnote 2, three tables have been evaluated using a faulty version of Ehoh prover. Reevaluation is being performed, and it is expected that the evaluation results will stay mostly the same, up to the noise in the evaluation environment. "eprover-ho" binary provided in this archive is the corrected version of the one used to evaluate tables 7, 8 and 9.

We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes. Baker's approach gives a PTAS on planar graphs, excluded-minor classes, and beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and \v{Z}ivn\'y [SODA'21] showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionally-treewidth-fragile classes, which is the most general "sparsity" condition for which a PTAS is known. We extend these results to general-valued CSPs, which include "crisp" (or "strict") constraints that have to be satisfied by every feasible assignment. The only condition on the crisp constraints is that their domain contains an element which is at least as feasible as all the others (but possibly less valuable). For minimisation general-valued CSPs with crisp constraints, we present a PTAS for all Baker graph classes -- a definition by Dvo\v{r}\'ak [SODA'20] which encompasses all classes where Baker's technique is known to work, except possibly for fractionally-treewidth-fragile classes. While this is standard for problems satisfying a certain monotonicity condition on crisp constraints, we show this can be relaxed to diagonalisability -- a property of relational structures connected to logics, statistical physics, and random CSPs., Comment: Full version of a LICS 2021 paper

We consider the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an $\varepsilon$-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete. We also provide an efficient algorithm for solving a special case of the problem, for a fixed number of bidders and available bids., Journal version. Preliminary version appeared at EC '21

Let $ G $ be a simple graph with edge set $ E(G) $. The modified Sombor index is defined as $ ^{m}SO(G) = \sum\limits_{uv\in E(G)}\frac{1}{\sqrt{d_{u}^{2}~~+~~d_{v}^{2}}} $, where $ d_{u} $ (resp. $ d_{v} $) denotes the degree of vertex $ u $ (resp. $ v $). In this paper, we determine some bounds for the modified Sombor indices of graphs with given some parameters (e.g., maximum degree $ \Delta $, minimum degree $ \delta $, diameter $ d $, girth $ g $) and the Nordhaus-Gaddum-type results. We also obtain the relationship between modified Sombor index and some other indices. At last, we obtain some bounds for the modified spectral radius and energy.

This paper presents a sequential network‐flow graph‐based method for a steady‐state power flow solution in hybrid multi‐terminal power systems. The proposed method is a unique and novel one, which differs from other established methods that involve the use of modified versions of classical power flow methods. The proposed method formulates a power flow problem as a maximum network‐flow problem and solves it using a push‐relabel max‐flow algorithm. The solution procedure solves AC and DC parts sequentially, while accounting for voltage source converter losses using a generalised converter model. The proposed flow‐Augmenting method solves the power flow problem using matrix vector multiplication in its most abstract form, and it is independent of system parameters and network configuration. The proposed formulation is computationally efficient, as it is based on matrix vector multiplication, and is scalable, because the formulation works as a graph‐based method, which, inherently, allows for parallel computation for added computational speed. Further, unlike previously reported methods, the proposed method does not rely on Jacobian matrix formulation or any matrix inversion. This proves to be a strong advantage for the proposed method, as a significant reduction in computational time is observed, as a result. The proposed method is validated on 5‐bus hybrid system and CIGRE B4 DC system.

A wordxthat is absent from a wordyis calledminimalif all its proper factors occur iny. Given a collection ofkwordsy1, … ,ykover an alphabetΣ, we are asked to compute the set$\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$M{y1,…,yk}ℓof minimal absent words of length at mostℓof the collection {y1, … ,yk}. The set$\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$M{y1,…,yk}ℓcontains all the wordsxsuch thatxis absent from all the words of the collection while there existi,j, such that the maximal proper suffix ofxis a factor ofyiand the maximal proper prefix ofxis a factor ofyj. In data compression, this corresponds to computing the antidictionary ofkdocuments. In bioinformatics, it corresponds to computing words that are absent from a genome ofkchromosomes. Indeed, the set$\mathrm {M}^{\ell }_{y}$Myℓof minimal absent words of a wordyis equal to$\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$M{y1,…,yk}ℓfor any decomposition ofyinto a collection of wordsy1, … ,yksuch that there is an overlap of length at leastℓ− 1 between any two consecutive words in the collection. This computation generally requiresΩ(n) space forn= |y| using any of the plenty available$\mathcal {O}(n)$O(n)-time algorithms. This is because anΩ(n)-sized text index is constructed overywhich can be impractical for largen. We do the identical computation incrementally using output-sensitive space. This goal is reasonable when$\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| =o(n)$∥M{y1,…,yN}ℓ∥=o(n), for allN∈ [1,k], where ∥S∥ denotes the sum of the lengths of words in setS. For instance, in the human genome,n≈ 3 × 109but$\| \mathrm {M}^{12}_{\{y_1,\ldots ,y_k\}}\| \approx 10^{6}$∥M{y1,…,yk}12∥≈106. We consider a constant-sized alphabet for stating our results. We show thatall$\mathrm {M}^{\ell }_{y_{1}},\ldots ,\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$My1ℓ,…,M{y1,…,yk}ℓcan be computed in$\mathcal {O}(kn+{\sum }^{k}_{N=1}\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| )$O(kn+∑N=1k∥M{y1,…,yN}ℓ∥)total time using$\mathcal {O}(\textsc {MaxIn}+\textsc {MaxOut})$O(MaxIn+MaxOut)space, where MaxIn is the length of the longest word in {y1, … ,yk} and$\textsc {MaxOut}=\max \limits \{\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| :N\in [1,k]\}$MaxOut=max{∥M{y1,…,yN}ℓ∥:N∈[1,k]}. Proof-of-concept experimental results are also provided confirming our theoretical findings and justifying our contribution.

Fully homomorphic encryption (FHE) allows to compute any function on encrypted values. However, in practice, there is no universal FHE scheme that is effi-cient in all possible use cases. In this work, we show that FHE schemes suitable for arithmetic circuits (e.g. BGV or BFV) have a similar performance as FHE schemes for non-arithmetic circuits (TFHE) in basic comparison tasks such as less-than, maximum and minimum operations. Our implementation of the less-than function in the HElib library is up to 3 times faster than the prior work based on BGV/BFV. It allows to compare a pair of 64-bit integers in 11 milliseconds, sort 64 32-bit integers in 19 seconds and find the minimum of 64 32-bit integers in 9.5 seconds on an average laptop without multi-threading.

In this article, we introduce and study the intersection graph of graded ideals of a graded ring. The intersection graph of $ G- $graded ideals of a graded ring $ R $, denoted by $ Gr_G(R) $, is undirected simple graph defined on the set of nontrivial graded left ideals of $ R $, such that two left ideals are adjacent if their intersection is not trivial. We study properties for these graphs such as connectivity, regularity, completeness, domination numbers, and girth. We also present several results on the intersection graphs related to faithful grading, strong grading, and graded idealization.

The notions ofos{o}_{s}-convergence andS∗{S}^{\ast }-doubly quasicontinuous posets are introduced, which can be viewed as common generalizations of Birkhoff’s order-convergence andS∗{S}^{\ast }-doubly continuous posets, respectively. We first consider the relationship betweenos{o}_{s}-convergence and B-topology and show that the topology induced byos{o}_{s}-convergence according to the standard topological approach is the B-topology precisely. Then, the topological characterization for theS∗{S}^{\ast }-doubly quasicontinuity is presented. It is proved that a poset isS∗{S}^{\ast }-doubly quasicontinuous iff the poset equipped with the B-topology is locally hyperclosed iff the lattice of all B-open subsets of the poset is hypercontinuous. Finally, the order theoretical condition for theos{o}_{s}-convergence being topological is given and the complete regularity of B-topology onS∗{S}^{\ast }-doubly quasicontinuous posets is explored.

We give a computational interpretation to an abstract formulation of Krull's theorem, by analysing its classical proof based on Zorn's lemma. Our approach is inspired by proof theory, and uses a form of update recursion to replace the existence of maximal ideals. Our main result allows us to derive, in a uniform way, algorithms which compute witnesses for existential theorems in countable abstract algebra. We give a number of concrete examples of this phenomenon, including the prime ideal theorem and Krull's theorem on valuation rings.

The main purpose of this article is to initiate a systematic study of Semihypergroups, first introduced by C. Dunkl [4], I. Jewett [13] and R. Spector [20] independently around 1972. We introduce and study several natural algebraic and analytic structures on semihypergroups, which are well-known in the case of topological groups and semigroups. In particular, we first study almost periodic and weakly almost periodic function spaces (basic properties, their relation to the compactness of the underlying space, introversion and Arens product on their duals among others). We then introduce homomorphisms and ideals, and thereby examine their behaviour (basic properties, structure of the kernel and relation of amenability to minimal ideals) in order to gain insight into the structure of a Semihypergroup itself. In the process, we further investigate where and why this theory deviates from the classical theory of semigroups., 26 Pages, comments are welcome

A correspondence is established between one-variable fragments of (first-order) intermediate logics defined over a fixed countable linear frame and Godel modal logics defined over many-valued equivalence relations with values in a closed subset of the real unit interval. It is also shown that each of these logics can be interpreted in the one-variable fragment of the corresponding constant domain intermediate logic, which is equivalent to a Godel modal logic defined over (crisp) equivalence relations. Although the latter modal logics in general lack the finite model property with respect to their frame semantics, an alternative semantics is defined that has this property and used to establish co-NP-completeness results for the one-variable fragments of the corresponding intermediate logics both with and without constant domains.

In this work, we investigate how the choice of the key-expansion algorithm and its interaction with the round function affect the resistance of Simon-like ciphers against rotational-XOR cryptanalysis. We observe that, among the key-expansion algorithms we consider, Simon is most resistant, while Simeck is much less so. Implications on lightweight ciphers design are discussed and open questions are proposed.

The Swing Lemma, proved by G. Gratzer in 2015, describes how a congruence spreads from a prime interval to another in a slim (having no $$\mathsf {M}_{3}$$ sublattice), planar, semimodular lattice. We generalize the Swing Lemma to planar semimodular lattices.

International journal on software tools for technology transfer (2021). doi:10.1007/s10009-021-00633-z, Published by Springer, Berlin; Heidelberg [u.a.]

An antimagic labeling a connected graph $G$ is a bijection from the set of edges $E(G)$ to $\{1,2,\dots,|E(G)|\}$ such that all vertex sums are pairwise distinct, where the vertex sum at vertex $v$ is the sum of the labels assigned to edges incident to $v$. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than $K_2$ is antimagic; however, the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Discrete Math. 331 (2014) 9--14]., Comment: 7 pages, 4 figures

A recent result of G. Cz\'edli relates the ordered set of principal congruences of a bounded lattice $L$ with the ordered set of principal congruences of a~bounded sublattice $K$ of $L$. In this note, I sketch a new proof.

The notion of comparison between system runs is fundamental in formal verification. This concept is implicitly present in the verification of qualitative systems, and is more pronounced in the verification of quantitative systems. In this work, we identify a novel mode of comparison in quantitative systems: the online comparison of the aggregate values of two sequences of quantitative weights. This notion is embodied by comparator automata (comparators, in short), a new class of automata that read two infinite sequences of weights synchronously and relate their aggregate values. We show that aggregate functions that can be represented with B\"uchi automaton result in comparators that are finite-state and accept by the B\"uchi condition as well. Such $\omega$-regular comparators further lead to generic algorithms for a number of well-studied problems, including the quantitative inclusion and winning strategies in quantitative graph games with incomplete information, as well as related non-decision problems, such as obtaining a finite representation of all counterexamples in the quantitative inclusion problem. We study comparators for two aggregate functions: discounted-sum and limit-average. We prove that the discounted-sum comparator is $\omega$-regular iff the discount-factor is an integer. Not every aggregate function, however, has an $\omega$-regular comparator. Specifically, we show that the language of sequence-pairs for which limit-average aggregates exist is neither $\omega$-regular nor $\omega$-context-free. Given this result, we introduce the notion of prefix-average as a relaxation of limit-average aggregation, and show that it admits $\omega$-context-free comparators i.e. comparator automata expressed by B\"uchi pushdown automata.

Introduction. Optimization placement problems are NP-hard. In most cases related to cutting and packing problems, heuristic approaches are used. The development of analytical methods for mathematical modeling of the problems is of paramount important for expanding the class of placement problems that can be solved optimally using state of the art NLP-solvers. The problem of placing two irregular two-dimensional objects in a convex polygonal region of the minimum size, which is a convex polygonal hull of the minimum area or perimeter, is considered. Continuous rotations and translations of non-overlapping objects are allowed. To solve the problem of optimal compaction of a pair of objects, two algorithms are proposed. The first is a sequentially search for local extrema on all feasible subdomains using a solution tree. The second algorithm searches for a locally optimal extremum on a single subdomain using a "good" feasible starting point. Purpose of the paper. Show how to construct a minimal convex polygonal hull for two continuously moving irregular objects bounded by circular arcs and line segments. Results. A mathematical model is constructed in the form of a nonlinear programming problem using the phi-function technique. Two algorithms are proposed for solving the problem of placing a pair of objects in order to minimize the area and perimeter of the enclosing polygonal area. The results of computational experiments are presented. Conclusions. The construction of a minimal convex polygonal hull for a pair of two-dimensional objects having an arbitrary spatial shape and allowing continuous rotations and translations makes it possible to speed up the process of finding feasible solutions for the problem of placing a large number of objects with complex geometry. Keywords: convex polygonal hull, irregular objects, phi-function technique, nonlinear optimization.

The present paper proposes a novel way to unify Rough Set Theory and Formal Concept Analysis. Our method stems from results and insights developed in the algebraic theory of modal logic, and is based on the idea that Pawlak's original approximation spaces can be seen as special instances of enriched formal contexts, i.e. relational structures based on formal; contexts from Formal Concept Analysis.

Let S = (G, σ) be a signed graph of order n and size m and let x1, x2, ..., xn be the eigenvalues of S. The energy of S is defined as ɛ ( S ) = ∑ j = 1 n | x j | \varepsilon \left( S \right) = \sum\limits_{j = 1}^n {\left| {{x_j}} \right|} . A connected signed graph is said to be bicyclic if m=n + 1. In this paper, we determine the bicyclic signed graphs with first 20 minimal energies for all n ≥ 30 and with first 16 minimal energies for all 17 ≤ n ≤ 29.

Recently, cryptographic literature has seen new block cipher designs such as PRESENT, GIFT or SKINNY that aim to be more lightweight than the current standard, i.e., AES. Even though AES family of block ciphers were designed two decades ago, they still remain as the de facto encryption standard, with AES-128 being the most widely deployed variant. In this work, we revisit the combined one-in-all implementation of the AES family, namely both encryption and decryption of each AES-128/192/256 as a single ASIC circuit. A preliminary version appeared in Africacrypt 2019 by Balli and Banik, where the authors design a byte-serial circuit with such functionality. We improve on their work by reducing the size of the compact circuit to 2268 GE through 1-bit-serial implementation, which achieves 38% reduction in area. We also report stand-alone bit-serial versions of the circuit, targeting only a subset of modes and versions, e.g., AES-192 and AES-256. Our results imply that, in terms of area, AES-192 and AES-256 can easily compete with the larger members of recently designed SKINNY family, e.g., SKINNY-128-256, SKINNY-128-384. Thus, our implementations can be used interchangeably inside authenticated encryption candidates such as SKINNY-AEAD/-HASH, ForkAE or Romulus in place of SKINNY.

In 2011, Factor and Merz [Discrete Appl. Math. 159 (2011), 100–103] defined the ( 1 , 2 ) \left(1,2) -step competition graph of a digraph. Given a digraph D = ( V , A ) D=\left(V,A) , the ( 1 , 2 ) \left(1,2) -step competition graph of D, denoted C 1 , 2 ( D ) {C}_{1,2}\left(D) , is a graph on V ( D ) V\left(D) , where x y ∈ E ( C 1 , 2 ( D ) ) xy\in E\left({C}_{1,2}\left(D)) if and only if there exists a vertex z ≠ x , y z\ne x,y such that either d D − y ( x , z ) = 1 {d}_{D-y}\left(x,z)=1 and d D − x ( y , z ) ≤ 2 {d}_{D-x}(y,z)\le 2 or d D − x ( y , z ) = 1 {d}_{D-x}(y,z)=1 and d D − y ( x , z ) ≤ 2 {d}_{D-y}\left(x,z)\le 2 . They also characterized the (1, 2)-step competition graphs of tournaments and extended some results to the ( i , j ) \left(i,j) -step competition graphs of tournaments. In this paper, the definition of the (1, 2)-step competition graph of a digraph is generalized to a hypertournament and the (1, 2)-step competition graph of a k-hypertournament is characterized. Also, the results are extended to ( i , j ) \left(i,j) -step competition graphs of k-hypertournaments.

In the study of chemical graph theory, an enormous number of research analyses have confirmed that the characteristics of chemicals have a nearby connection with their atomic structure. Topological indices were the critical tools for the analysis of these chemical substances to consider the essential topology of chemical structures. Topological descriptors are the significant numerical quantities or invariant in the fields of chemical graph theory. In this study, we have studied the crystal structure of copper oxide ( Cu 2 O {{\rm{Cu}}}_{2}{\rm{O}} ) chemical graph, and further, we have calculated the ev-degree- and ve-degree-based topological indices of copper oxide chemical graph. This kind of study may be useful for understanding the atomic mechanisms of corrosion and stress–corrosion cracking of copper.

Finitely many agents have preferences on a finite set of alternatives, single-peaked with respect to a connected graph with these alternatives as vertices. A probabilistic rule assigns to each preference profile a probability distribution over the alternatives. First, all unanimous and strategy-proof probabilistic rules are characterized when the graph is a tree. These rules are uniquely determined by their outcomes at those preference profiles at which all peaks are on leaves of the tree and, thus, extend the known case of a line graph. Second, it is shown that every unanimous and strategy-proof probabilistic rule is random dictatorial if and only if the graph has no leaves. Finally, the two results are combined to obtain a general characterization for every connected graph by using its block tree representation.

In 2018, Bai, Fujita and Zhang [Discrete Math. 341 (2018), no. 6, 1523–1533] introduced the concept of a kernel by rainbow paths (for short, RP-kernel) of an arc-coloured digraph D D , which is a subset S S of vertices of D D such that ( a a ) there exists no rainbow path for any pair of distinct vertices of S S , and ( b b ) every vertex outside S S can reach S S by a rainbow path in D D . They showed that it is NP-hard to recognize whether an arc-coloured digraph has an RP-kernel and it is NP-complete to decide whether an arc-coloured tournament has an RP-kernel. In this paper, we give the sufficient conditions for the existence of an RP-kernel in arc-coloured unicyclic digraphs, semicomplete digraphs, quasi-transitive digraphs and bipartite tournaments, and prove that these arc-coloured digraphs have RP-kernels if certain “short” cycles and certain “small” induced subdigraphs are rainbow.