waashk/dblp huggingface dataset:
probe threshold and probe trivially perfect graphs. an undirected graph g=(v,e) is a probec graph if its vertex set can be partitioned into two sets, n (nonprobes) and p (probes) where n is independent and there exists e^'@?nxn such that g^'=(v,e@?e^') is a c graph. in this article we investigate probe threshold and probe trivially perfect graphs and characterise them in terms of certain 2-sat formulas and in other ways. for the case when the partition into probes and nonprobes is given, we give characterisations by forbidden induced subgraphs, linear recognition algorithms (in the case of probe threshold graphs it is based on the degree sequence of the graph), and linear algorithms to find a set e^' of minimum size. furthermore, we give linear time recognition algorithms for both classes and a characterisation by forbidden subgraphs for probe threshold graphs when the partition (p,n) is not given.
ptas for connected vertex cover in unit disk graphs. this paper gives the first polynomial time approximation scheme for the connected vertex cover problem in unit disk graphs.
scale free interval graphs. scale free graphs have attracted attention by their non-uniform structure that can be used as a model for various social and physical networks. in this paper, we propose a natural and simple random model for generating scale free interval graphs. the model generates a set of intervals randomly under a certain distribution, which defines a random interval graph. the main advantage of the model is its simpleness. the structure/properties of generated graphs are analyzable by relatively simple probabilistic and/or combinatorial arguments, which is different from many other models. based on such arguments, we show for our random interval graph that its degree distribution follows a power law, and that it has a large average clustering coefficient.
periodic scheduling with obligatory vacations. we consider a problem of repeatedly scheduling n jobs on m parallel machines. each job is associated with a profit that is gained each time the job is completed, and the goal is to maximize the average profit per time unit. once the processing of a job is completed, it goes on vacation and returns to the system, ready to be processed again, only after its vacation is over. this problem has many applications: in production planning, machine maintenance, video-on-demand and database query processing, among others. we show that the problem is np-hard already for jobs with unit processing times and unit profits, and develop approximation algorithms as well as optimal algorithms for certain subclasses of instances. we first show that a 5/3-approximation algorithm can be obtained for instances with unit processing times, using known results for windows scheduling. we then present a preemptive greedy algorithm, which yields a ratio of e/(e-1) to the optimal for general instances, with arbitrary processing times and arbitrary profits. for the special case where all jobs have the same (unit) processing times and the same (unit) profits, we present a 1.39-approximation algorithm. for this case we also show that, when the load generated by an instance is sufficiently large (in terms of n and m), any algorithm which uses no intended idle times yields an optimal schedule.
finding paths between graph colourings: pspace-completeness and superpolynomial distances. suppose we are given a graph g together with two proper vertex k-colourings of g, @a and @b. how easily can we decide whether it is possible to transform @a into @b by recolouring vertices of g one at a time, making sure we always have a proper k-colouring of g? this decision problem is trivial for k=2, and decidable in polynomial time for k=3. here we prove it is pspace-complete for all k>=4. in particular, we prove that the problem remains pspace-complete for bipartite graphs, as well as for: (i) planar graphs and 4@?k@?6, and (ii) bipartite planar graphs and k=4. moreover, the values of k in (i) and (ii) are tight, in the sense that for larger values of k, it is always possible to recolour @a to @b. we also exhibit, for every k>=4, a class of graphs {g"n","k:n@?n^*}, together with two k-colourings for each g"n","k, such that the minimum number of recolouring steps required to transform the first colouring into the second is superpolynomial in the size of the graph: the minimum number of steps is @w(2^n), whereas the size of g"n is o(n^2). this is in stark contrast to the k=3 case, where it is known that the minimum number of recolouring steps is at most quadratic in the number of vertices. we also show that a class of bipartite graphs can be constructed with this property, and that: (i) for 4@?k@?6 planar graphs and (ii) for k=4 bipartite planar graphs can be constructed with this property. this provides a remarkable correspondence between the tractability of the problem and its underlying structure.
robustness of temporal logic specifications for continuous-time signals. in this paper, we consider the robust interpretation of metric temporal logic (mtl) formulas over signals that take values in metric spaces. for such signals, which are generated by systems whose states are equipped with non-trivial metrics, for example continuous or hybrid, robustness is not only natural, but also a critical measure of system performance. thus, we propose multi-valued semantics for mtl formulas, which capture not only the usual boolean satisfiability of the formula, but also topological information regarding the distance, @e, from unsatisfiability. we prove that any other signal that remains @e-close to the initial one also satisfies the same mtl specification under the usual boolean semantics. finally, our framework is applied to the problem of testing formulas of two fragments of mtl, namely metric interval temporal logic (mitl) and closed metric temporal logic (clmtl), over continuous-time signals using only discrete-time analysis. the motivating idea behind our approach is that if the continuous-time signal fulfills certain conditions and the discrete-time signal robustly satisfies the temporal logic specification, then the corresponding continuous-time signal should also satisfy the same temporal logic specification.
a parameterized view on matroid optimization problems. matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. however, several natural matroid problems, such as 3-matroid intersection, are np-hard. here we investigate these problems from the parameterized complexity point of view: instead of the trivial n^o^(^k^) time brute force algorithm for finding a k-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)@?n^o^(^1^)) running time. the main result is that if the ground set of a represented linear matroid is partitioned into blocks of size @?, then we can determine in randomized time f(k,@?)@?n^o^(^1^) whether there is an independent set that is the union of k blocks. as a consequence, algorithms with similar running time are obtained for other problems such as finding a k-element set in the intersection of @? matroids, or finding k terminals in a network such that each of them can be connected simultaneously to the source by @? disjoint paths.
a new approach to the periodicity lemma on strings with holes. we first give an elementary proof of the periodicity lemma for strings containing one hole (variously called a ''wild card'', a ''don't-care'' or an ''indeterminate letter'' in the literature). the proof is modelled on euclid's algorithm for the greatest common divisor and is simpler than the original proof given in [j. berstel, l. boasson, partial words and a theorem of fine and wilf, theoret. comput. sci. 218 (1999) 135-141]. we then study the two-hole case, where our result agrees with the one given in [f. blanchet-sadri, robert a. hegstrom, partial words and a theorem of fine and wilf revisited, theoret. comput. sci. 270 (1-2) (2002) 401-419] but is more easily proved and enables us to identify a maximum-length prefix or suffix of the string to which the periodicity lemma does apply. finally, we extend our result to three or more holes using elementary methods, and state a version of the periodicity lemma that applies to all strings with or without holes. we describe an algorithm that, given the locations of the holes in a string, computes maximum-length substrings to which the periodicity lemma applies, in time proportional to the number of holes. our approach is quite different from that used by blanchet-sadri and hegstrom, and also simpler.
semisimple algebras of almost minimal rank over the reals. a famous lower bound for the bilinear complexity of the multiplication in associative algebras is the alder-strassen bound. algebras for which this bound is tight are called algebras of minimal rank. after 25 years of research, these algebras are now well understood. here we start the investigation of the algebras for which the alder-strassen bound is off by one. as a first result, we completely characterize the semisimple algebras over r whose bilinear complexity is by one larger than the alder-strassen bound. furthermore, we characterize all algebras a (with radical) of minimal rank plus one over r for which a/rada has minimal rank plus one. the other possibility is that a/rada has minimal rank. for this case, we only present a partial result.
claw finding algorithms using quantum walk. the claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. given two functions, f and g, with domain sizes n and m(n@?m), respectively, and the same range, the goal of the problem is to find x and y such that f(x)=g(y). this problem has been considered in both quantum and classical settings in terms of query complexity. this paper describes an optimal algorithm that uses quantum walk to solve this problem. our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. it can also be generalized to find a claw of k functions for any constant integer k>1, where the domain sizes of the functions may be different.
the parikh counting functions of sparse context-free languages are quasi-polynomials. let l be a sparse context-free language over an alphabet of t letters and let f"l:n^t->n be its parikh counting function. we prove the following two results: 1.there exists a partition of n^t into a finite family of polyhedra such that the function f"l is a quasi-polynomial on each polyhedron of the partition. 2.there exists a partition of n^t into a finite family of rational subsets such that the function f"l is a polynomial on each set of the partition.
the isolation game: a game of distances. we introduce a new multi-player geometric game, which we will refer to as the isolation game, and study its nash equilibria and best or better response dynamics. the isolation game is inspired by the voronoi game, competitive facility location, and geometric sampling. in the voronoi game studied by durr and thang, each player's objective is to maximize the area of her voronoi region. in contrast, in the isolation game, each player's objective is to position herself as far away from other players as possible in a bounded space. even though this game has a simple definition, we show that its game-theoretic behaviors are quite rich and complex. we consider various measures of farness from one player to a group of players and analyze their impacts to the existence of nash equilibria and to the convergence of the best or better response dynamics: we prove that it is np-hard to decide whether a nash equilibrium exists, using either a very simple farness measure in an asymmetric space or a slightly more sophisticated farness measure in a symmetric space. complementing these hardness results, we establish existence theorems for several special families of farness measures in symmetric spaces: we prove that, for isolation games where each player wants to maximize her distance to her mth nearest neighbor, for any m, equilibria always exist. moreover, there is always a better response sequence starting from any configuration that leads to a nash equilibrium. we show that when m=1 the game is a potential game, no better response sequence has a cycle, but when m>1 the games are not potential. more generally, we study farness functions that give different weights to a player's distances to others based on the distance rankings, and obtain both existence and hardness results when the weights are monotonically increasing or decreasing. finally, we present results on the hardness of computing best responses when the space has a compact representation as a hypercube.
distance paired-domination problems on subclasses of chordal graphs. let g=(v,e) be a graph without isolated vertices. for a positive integer k, a set s@?v is a k-distance paired-dominating set if each vertex in v-s is within distance k of a vertex in s and the subgraph induced by s contains a perfect matching. in this paper, we present two linear time algorithms to find a minimum cardinality k-distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. in addition, we present a characterization of trees with unique minimum k-distance paired-dominating set.
repetitions in strings: algorithms and combinatorics. the article is an overview of basic issues related to repetitions in strings, concentrating on algorithmic and combinatorial aspects. this area is important both from theoretical and practical points of view. repetitions are highly periodic factors (substrings) in strings and are related to periodicities, regularities, and compression. the repetitive structure of strings leads to higher compression rates, and conversely, some compression techniques are at the core of fast algorithms for detecting repetitions. there are several types of repetitions in strings: squares, cubes, and maximal repetitions also called runs. for these repetitions, we distinguish between the factors (sometimes qualified as distinct) and their occurrences (also called positioned factors). the combinatorics of repetitions is a very intricate area, full of open problems. for example we know that the number of (distinct) primitively-rooted squares in a string of length n is no more than 2n-@q(logn), conjecture to be n, and that their number of occurrences can be @q(nlogn). similarly we know that there are at most 1.029n and at least 0.944n maximal repetitions and the conjecture is again that the exact bound is n. we know almost everything about the repetitions in sturmian words, but despite the simplicity of these words, the results are nontrivial. one of the main motivations for writing this text is the development during the last couple of years of new techniques and results about repetitions. we report both the progress which has been achieved and which we expect to happen.
minimum leaf out-branching and related problems. given a digraph d, the minimum leaf out-branching problem (minlob) is the problem of finding in d an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. we prove that minlob is polynomial-time solvable for acyclic digraphs. in general, minlob is np-hard and we consider three parameterizations of minlob. we prove that two of them are np-complete for every value of the parameter, but the third one is fixed-parameter tractable (fpt). the fpt parameterization is as follows: given a digraph d of order n and a positive integral parameter k, check whether d contains an out-branching with at most n-k leaves (and find such an out-branching if it exists). we find a problem kernel of order o(k^2) and construct an algorithm of running time o(2^o^(^k^l^o^g^k^)+n^6), which is an 'additive' fpt algorithm. we also consider transformations from two related problems, the minimum path covering and the maximum internal out-tree problems into minlob, which imply that some parameterizations of the two problems are fpt as well.
on the directional dynamics of additive cellular automata. we continue the study of cellular automata (ca) directional dynamics, i.e. , the behavior of the joint action of ca and shift maps. this notion has been investigated for general ca in the case of expansive dynamics by boyle and lind; and by sablik for sensitivity and equicontinuity. in this paper we give a detailed classification for the class of additive ca providing non-trivial examples for some classes of sablik's classification. moreover, we extend the directional dynamics studies by considering also factor languages and attractors.
simplicial powers of graphs. in a graph, a vertex is simplicial if its neighborhood is a clique. for an integer k>=1, a graph g=(v"g,e"g) is the k-simplicial power of a graph h=(v"h,e"h) (h a root graph of g) if v"g is the set of all simplicial vertices of h, and for all distinct vertices x and y in v"g, xy@?e"g if and only if the distance in h between x and y is at most k. this concept generalizes k-leaf powers introduced by nishimura, ragde and thilikos which were motivated by the search for underlying phylogenetic trees; k-leaf powers are the k-simplicial powers of trees. recently, a lot of work has been done on k-leaf powers and their roots as well as on their variants phylogenetic roots and steiner roots. for k@?5, k-leaf powers can be recognized in linear time, and for k@?4, structural characterizations are known. for k>=6, the recognition and characterization problems of k-leaf powers are still open. since trees and block graphs (i.e., connected graphs whose blocks are cliques) have very similar metric properties, it is natural to study k-simplicial powers of block graphs. we show that leaf powers of trees and simplicial powers of block graphs are closely related, and we study simplicial powers of other graph classes containing all trees such as ptolemaic graphs and strongly chordal graphs.
large independent sets in random regular graphs. we present algorithmic lower bounds on the size s"d of the largest independent sets of vertices in random d-regular graphs, for each fixed d>=3. for instance, for d=3 we prove that, for graphs on n vertices, s"d>=0.43475n with probability approaching one as n tends to infinity.
parameterized complexity of candidate control in elections and related digraph problems. there are different ways for an external agent to influence the outcome of an election. we concentrate on ''control'' by adding or deleting candidates. our main focus is to investigate the parameterized complexity of various control problems for different voting systems. to this end, we introduce natural digraph problems that may be of independent interest. they help in determining the parameterized complexity of control for different voting systems including llull, copeland, and plurality voting. devising several parameterized reductions, we provide an overview of the parameterized complexity of the digraph and control problems with respect to natural parameters such as adding/deleting only a bounded number of candidates or having only few voters.
scheduling multiprocessor uet tasks of two sizes. in this paper we study task scheduling problems on m identical parallel processors, where each task has unit execution time, and needs either a single processor, or q processors concurrently, and it has a release date and a due date. under the assumption that the release dates and due dates of the q-processor tasks are agreeable, we describe a polynomial time algorithm for minimising the number of tardy tasks. in addition, we apply this result for minimising the maximum lateness, and the maximum tardiness. we also discuss the combinatorial background of the polynomial time solvability of all these problems under the 'agreeable' assumption.
a characterization of regular circular languages generated by marked splicing systems. splicing systems are generative devices of formal languages, introduced by head in 1987 to model biological phenomena on linear and circular dna molecules. a splicing system is defined by giving an initial set i and a set r of rules. some unanswered questions are related to the computational power of circular splicing systems. in particular, a still open question is to find a characterization of circular languages generated by finite circular splicing systems (i.e., circular splicing systems with both i and r finite sets). in this paper we introduce a special class of the latter systems named marked systems. we prove that a marked system s generates a regular circular language if and only if s satisfies a special (decidable) property. as a consequence, we are able to characterize the structure of these regular circular languages.
disjoint directed and undirected paths and cycles in digraphs. we show that the following problem is np-complete: given a digraph d and distinct vertices s,t of d, decide whether the underlying graph of d contains two internally disjoint (s,t)-paths p and q such that p is a directed (s,t)-path in d. using this result we characterize those mixed linkage problems which are polynomially solvable (assuming p
direct chosen-ciphertext secure identity-based key encapsulation without random oracles. we describe a practical identity-based encryption scheme that is secure in the standard model against chosen-ciphertext attacks. our construction applies ''direct chosen-ciphertext techniques'' to waters' chosen-plaintext secure scheme and is not based on hierarchical identity-based encryption. furthermore, we give an improved concrete security analysis for waters' scheme. as a result, one can instantiate the scheme in smaller groups, resulting in efficiency improvements.
maximum weight bipartite matching in matrix multiplication time. in this paper we consider the problem of finding maximum weight matchings in bipartite graphs with nonnegative integer weights. the presented algorithm for this problem works in o@?(wn^@w) time, where @w is the matrix multiplication exponent, and w is the highest edge weight in the graph. as a consequence of this result we obtain o@?(wn^@w) time algorithms for computing: minimum weight bipartite vertex cover, single source shortest paths and minimum weight vertex disjoint s-t paths. all of the presented algorithms are randomized and with small probability can return suboptimal solutions.
termination of narrowing revisited. this paper describes several classes of term rewriting systems (trs's), where narrowing has a finite search space and is still (strongly) complete as a mechanism for solving reachability goals. these classes do not assume confluence of the trs. we also ascertain purely syntactic criteria that suffice to ensure the termination of narrowing, and include several subclasses of popular trs's such as right-linear trs's, almost orthogonal trs's, topmost trs's, and left-flat trs's. our results improve and/or generalize previous criteria in the literature regarding narrowing termination.
maximal and minimal representations of gapped and non-gapped motifs of a string. the problems of finding maximal and minimal equivalent representations for gapped and non-gapped motifs as well as finding motifs that characterize a fixed set of occurrence locations for a given string are studied. we apply two equivalence relations on representations. the first one is the well-known occurrence-equivalence of motifs. the second equivalence is introduced for patterns of occurrence locations, to characterize such patterns by motifs. for both equivalences, quadratic-time algorithms are given for finding a maximal representative of an equivalence class. finding a minimal representative is shown to be np-complete in both cases. for non-gapped motifs suffix-tree-based linear-time algorithms are given for finding maximal and minimal representatives. maximal (minimal) gapped motifs are composed of blocks that are maximal (minimal) non-gapped motifs, maximal and minimal non-gapped motifs thus making up a small basis for all motifs. the implied bound on the number of gapped motifs that have a fixed number of non-gapped blocks is also given.