Search

In this paper, we are interested in algorithms that take in input an arbitrary graph G , and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of G which fulfil a given property Π. All over this paper, we study several different properties Π , and the notion of subgraph under consideration (induced or not) will vary from a result to another. More precisely, we present efficient algorithms to list all maximal split subgraphs, maximal induced cographs and maximal threshold graphs of a given input graph. All the algorithms presented here run in polynomial delay, and moreover for split graphs it only requires polynomial space. In order to develop an algorithm for maximal split (edge-)subgraphs, we establish a bijection between the maximal split subgraphs and the maximal stable sets of an auxiliary graph. For cographs and threshold graphs, the algorithms rely on a framework recently introduced by Conte & Uno (2019) called Proximity Search. Finally we consider the extension problem, which consists in deciding if there exists a maximal induced subgraph satisfying a property Π that contains a set of prescribed vertices and that avoids another set of vertices. We show that this problem is NP-complete for every non-trivial hereditary property Π. We extend the hardness result to some specific edge version of the extension problem. [ABSTRACT FROM AUTHOR]

A k -class domination coloring (k -cd-coloring) is a partition of the vertex set of a graph G into k independent sets V 1 , ... , V k , where each V i is dominated by some vertex u i of G. The least integer k such that G admits a k -cd-coloring is called the cd-chromatic number, χ c d (G) , of G. A subset S of the vertex set of a graph G is called a subclique in G if d G (x , y) ≠ 2 for every x , y ∈ S. The cardinality of a maximum subclique in G is called the subclique number, ω s (G) , of G. In this paper, we present algorithms to compute an optimal cd-coloring and a maximum subclique of (i) trees with time complexity O (n) and (ii) co-bipartite graphs with time complexity O (n 2. 5). This improves O (n 3) algorithms by Shalu et al. (2017, 2020). In addition, we prove tight upper bounds for the subclique number of the class of (i) P 5 -free graphs and (ii) double-split graphs. [ABSTRACT FROM AUTHOR]

The concept of jump system, introduced by Bouchet and Cunningham (1995), is a set of integer points satisfying a certain exchange property. We consider the minimization of a separable convex function on a jump system. It is known that the problem can be solved by a greedy algorithm. In this paper, we are interested in whether the greedy algorithm has the geodesic property, which means that the trajectory of the solutions generated by the algorithm is a geodesic from the initial solution to a nearest optimal solution. We show that a special implementation of the greedy algorithm enjoys the geodesic property, while the original algorithm does not. As a corollary to this, we present a new greedy algorithm for linear optimization on a delta-matroid and show that the algorithm has the geodesic property. [ABSTRACT FROM AUTHOR]

As is known, the problem of finding a three-dimensional stable matching with cyclic preferences (3DSM-CYC) always has a solution, if the number of objects of each type (i.e., the problem size n) does not exceed 5. According to the conjecture proposed by Eriksson et al. (2006), this is true for any n. However, Lam and Plaxton (2019) have proposed an algorithm for constructing preference lists in 3DSM-CYC which has allowed them to disprove the mentioned conjecture. The size of the initially constructed counterexample equals 90; however, according to the results obtained by us recently for the problem with incomplete preference lists, one can use the same construction for getting a counterexample of size 45. The main contribution of this paper consists of reducing the size of the counterexample to n = 20. We summarize results of the application of the technique developed by us for constructing counterexamples for 3DSM-CYC. In the final section of the paper we discuss a new variant of 3DSM, whose solution always exists and can be found within the same time as that required for solving 2DSM. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , an L (2 , 1) -labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u , v) , | ℓ (u) − ℓ (v) | ≥ 2 if u and v are adjacent, and ℓ (u) ≠ ℓ (v) if u and v are at distance 2. The L (2 , 1) -labeling problem is to minimize the range of ℓ (i.e., max u ∈ V (ℓ (u)) − min u ∈ V (ℓ (u)) + 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L (2 , 1) -labeling of unit disk graphs. • An 8-approximation algorithm of L(2,1)-labeling for unit disk graphs with geometric representations is presented. • The previously known bound is 10.67. • The presented algorithm gives a simple periodic labeling based on a new way of partitioning the plane into squares. [ABSTRACT FROM AUTHOR]

This paper focuses on the computation of a rule in minimum cost spanning tree problems with groups, which coincides with the Owen value of the cooperative game for the irreducible cost matrix. To this aim, two polynomial-time algorithms are provided. The first of them is based on the steps of Kruskal algorithm whereas the other is based on a painting procedure. [ABSTRACT FROM AUTHOR]

In a graph, G = (V , E) without an isolated vertex, a dominating set D ⊆ V , is called a semitotal dominating set if for every vertex u ∈ D there is another vertex v ∈ D such that distance between u and v is at most two in G. Given a graph G = (V , E) without an isolated vertex, the Minimum Semitotal Domination problem is to find a minimum cardinality semitotal dominating set of G. The semitotal domination number , denoted by γ t 2 (G) , is the minimum cardinality of a semitotal dominating set of G. It is known that the decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. Galby et al. (2020) proved that the problem can be solved in polynomial time for bounded MIM-width graphs, which include many well known graph classes, but left the complexity of the problem in strongly chordal graphs unresolved. Henning and Pandey (2019) also asked to resolve the complexity status of the problem in strongly chordal graphs. In this paper, we resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem. [ABSTRACT FROM AUTHOR]

Zou et al. (2019) proposed an algorithm for calculating a minimum secure dominating set of a proper interval graph. However, we find a counterexample for which the algorithm outputs an incorrect subset of vertices. In this paper, we provide a modified algorithm and the proofs for the correctness. [ABSTRACT FROM AUTHOR]

We consider competitive algorithms for adaptive group testing problems. In the first part of the paper, we develop an algorithm with competitive constant c < 1. 452 thus improving the up to now best known algorithms with constants 1. 5 + ϵ from 2003. In the second part, we prove the first nontrivial lower bound for competitive constants, namely that c is always larger than 1.31. [ABSTRACT FROM AUTHOR]

The problems of recognizing series–parallel graphs, outerplanar graphs, and generalized series–parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the algorithms are certifying. A certifying algorithm generates, in addition to its answer, a certificate that can be used by a checker (a separate algorithm) to verify the correctness of the answer. The certificate is positive if the answer is 'yes', and is negative if the answer is 'no'. In this paper, an O (| E | + | V |) -time certifying algorithm that simultaneously determines if a graph G = (V , E) is series–parallel, outerplanar, or generalized series–parallel is presented. The positive certificates are a construction sequence for constructing G if G is series–parallel, a generalized construction sequence for constructing G if G is generalized series–parallel but not series–parallel, and the edge set of the exterior boundary of an outerplanar embedding of G if G is outerplanar. The negative certificates are forbidden subgraphs or forbidden structures of G. All these certificates are generated by making only one pass over G after a preprocessing step decomposing G into its biconnected components. [ABSTRACT FROM AUTHOR]

An added edge to a graph is called an inset edge. Predicting k inset edges, which minimize the average distance of a graph, is known to be NP-Hard. However, when k = 1 , the complexity of the problem is polynomial. In this paper, some tools for a precise analysis of the effect of inset edges on the tree's average distance are established. Using the tools, one can avoid using the distance matrix for better performance of algorithms. Here, some applications of the tools and a tight bound for the change of average distance when an inset edge is added to a tree are presented. [ABSTRACT FROM AUTHOR]

Carsten Thomassen and I proved that in any graph G , the number of cycles containing a specified edge as well as all the vertices of odd degree is odd if and only if G is eulerian. Where all vertices have even degree this is a theorem of Shunichi Toida and where all vertices have odd degree it is Andrew Thomason's extension of Smith's Theorem. Our proof was not algorithmic. In this paper, I extend Thomason's algorithm to one which, in a non-eulerian graph, finds a second cycle containing a specified edge and all the odd-degree vertices. Kenneth Berman extended Thomason's Theorem to spanning trees: he proved that if T is a spanning tree such that the degree of every vertex in G − E (T) is odd, then there is an even number of spanning trees of G with the same degree as T at each vertex. In this paper, I give a common generalization of all of these theorems to a parity theorem about "good" trees in general graphs. My proof provides an algorithm for finding a second "good" tree. [ABSTRACT FROM AUTHOR]

In this paper, we propose several algorithms for determining an optimal length tree-like refutation of linear feasibility in systems of Unit Two Variable Per Inequality (UTVPI) constraints. Given an infeasible UTVPI constraint system (UCS), a refutation certifies its infeasibility. The problem of finding refutations in a UCS finds applications in domains such as program verification and operations research. In general, there exist several types of refutations of feasibility in constraint systems. In this paper, we focus on a specific type of refutation called a tree-like refutation. Tree-like refutations are complete , in the sense that if a system of linear constraints is infeasible, then it must have a tree-like refutation. Associated with a refutation is its length, which equals the total number of constraints (accounting for the reuse of constraints) that are used to establish the infeasibility of the corresponding linear constraint system. Our goal in this paper is to find an optimal length tree-like refutation (OTLR) of an infeasible UCS. We describe two deterministic algorithms that find an OTLR of a UCS. If m is the number of constraints, n is the number of variables in the system, and k is the length of an OTLR, then our two algorithms run in O (n 3 ⋅ log k) time and O (m ⋅ n ⋅ k) time respectively. We also propose a true-biased, randomized algorithm for this problem. This algorithm runs in O (m ⋅ n ⋅ log n) time, and returns the length of an OTLR with probability (1 − 1 e). We extend our work to weighted UTVPI constraint systems (WUCS), where a positive weight is associated with each UTVPI constraint. The weight of a tree-like refutation is defined as the sum of the weights of the constraints used by the refutation. The problem of finding a minimum weight refutation in a WUCS is called the weighted optimal length tree-like refutation (WOTLR) problem and is known to be NP-hard. We propose a pseudo-polynomial time algorithm for the WOTLR problem and convert it into a fully polynomial time approximation scheme (FPTAS). [ABSTRACT FROM AUTHOR]

In this paper we study the parameterized complexity for the Maximum Happy Set problem (MaxHS): For an undirected graph G = (V , E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S ; otherwise unhappy. Given an undirected graph G = (V , E) and an integer k , the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard with respect to k even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by tree-width, by clique-width plus k , by neighborhood diversity, or by cluster deletion number. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of determining all optimal integer solutions of a linear integer network flow problem, which we call the all optimal integer flow (AOF) problem. We derive an O (F (m + n) + m n + M) time algorithm to determine all F many optimal integer flows in a directed network with n nodes and m arcs, where M is the best time needed to find one minimum cost flow. We remark that stopping Hamacher's well-known method for the determination of the K best integer flows (Hamacher, 1995) at the first sub-optimal flow results in an algorithm with a running time of O (F m (n log n + m) + M) for solving the AOF problem. Our improvement is essentially made possible by replacing the shortest path sub-problem with a more efficient way to determine a so-called proper zero cost cycle using a modified depth-first search technique. As a byproduct, our analysis yields an enhanced algorithm to determine the K best integer flows that runs in O (K n 3 + M). Besides, we give lower and upper bounds for the number of all optimal integer and feasible integer solutions. Our bounds are based on the fact that any optimal solution can be obtained by an initial optimal tree solution plus a conical combination of incidence vectors of all induced cycles with bounded coefficients. [ABSTRACT FROM AUTHOR]

In this paper, we study the complexity of the edge monitoring problem. A vertex v monitors an edge e if both endpoints together with v form a triangle in the graph. Given a graph G = (V , E) and a weight function on edges c where c (e) is the number of monitors that needs the edge e , the problem is to seek a minimum subset of monitors S such that every edge e in the graph is monitored by at least c (e) vertices in S. Therefore, we study the edge monitoring problem on several graph classes such as complete graphs, block graphs, cographs, split graphs, interval graphs and planar graphs. We also generalize the problem by adding weights on vertices. [ABSTRACT FROM AUTHOR]

In this paper, we design the first streaming algorithms for the problem of multitasking scheduling on parallel machines with shared processing. In one pass, our streaming approximation schemes can provide an approximate value of the optimal makespan. If the jobs can be read in two passes, the algorithm can find the schedule with the approximate value. This work not only provides an algorithmic big data solution for the studied problem, but also gives an insight into the design of streaming algorithms for other problems in the area of scheduling. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G is a set S ⊆ V (G) such that every vertex in G is either in S or adjacent to a vertex in S. A dominating set S is a connected dominating set if the subgraph of G induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number , denoted by γ c (G). Zhuang showed that γ c (G) of a maximal outerplanar graph G is bounded by min { ⌊ n + k 2 ⌋ − 2 , ⌊ 2 (n − k) 3 ⌋ } (Zhuang, 2020), where k is the number of 2-degree vertices in G. In this paper, we give an algorithm for finding a connected dominating set of maximal outerplanar graphs and get an upper bound γ c (G) ≤ ⌊ n − k + x 2 ⌋ , where x is a counter in the algorithm and x ≤ k − 2. As a corollary, the result that γ c (G) ≤ ⌊ n − 2 2 ⌋ for a maximal outerplanar G is gotten directly. This results is better than the above known bound for 3 < k < n + 6 4 . In addition, we complement some analysis with simulations to evaluate the advantages of our results. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) and an integer k ≥ 1 , a k - hop dominating set D of G is a subset of V , such that, for every vertex v ∈ V , there exists a node u ∈ D whose distance from v is at most k. A k -hop dominating set of minimum cardinality is called a minimum k -hop dominating set. In this paper, we present a linear-time algorithm that finds a minimum k -hop dominating set in cactus graphs , which improves the O (n 3) -time algorithm of Borradaile and Le (2017). To achieve this, we show that the k -hop dominating set problem for unicyclic graphs reduces to the piercing circular arcs problem , and show a linear-time algorithm for piercing sorted circular arcs, which improves the best known O (n log n) -time algorithm. [ABSTRACT FROM AUTHOR]

In this paper we consider the so-called Multi-returning secretary problem, a version of the Secretary problem in which each candidate has m identical copies. The case m = 2 has already been completely solved by several authors using different methods, but the case m > 2 had not been satisfactorily solved yet. Here, under the conjecture of certain (very likely true) uniform convergence results, we provide an efficient algorithm to compute the optimal threshold and the probability of success for every m. Moreover, we give a method to determine their asymptotic values based on the solution of a system of m ODEs. [ABSTRACT FROM AUTHOR]

Conflict-free q -colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the Minimum Conflict-free q-Colouring problem. Given a graph G and a fixed constant q , Minimum Conflict-free q-Colouring is to find a conflict-free q -colouring of G that minimizes the number of coloured vertices. We study the parameterized complexity of the Minimum Conflict-free q-Colouring problem when parameterized by structural parameters like treewidth and vertex cover of G. We give an FPT algorithm for Minimum Conflict-free q-Colouring parameterized by treewidth and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH). Using standard kernelization lower bound techniques, it is easy to see that Minimum Conflict-free q-Colouring parameterized by treewidth does not admit polynomial kernels. We extend this result for a larger parameter namely the vertex cover of G , when q > 1. [ABSTRACT FROM AUTHOR]

In this paper, we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some Cartesian products. One of our main results is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by Imrich and Peterin (2018). We also study the chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with underlying graph of the form P n □ P m , of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles. [ABSTRACT FROM AUTHOR]

A set S ⊂ V is a co-secure dominating set of a graph G = (V , E) if S is a dominating set, and for each u ∈ S there exists a vertex v ∈ V ∖ S such that u v ∈ E and (S ∖ { u }) ∪ { v } is a dominating set. Note that | V | > 1. The minimum cardinality of a co-secure dominating set in G is the co-secure domination number of G. In this paper, we propose a linear-time algorithm for finding the co-secure domination number of proper interval graphs. [ABSTRACT FROM AUTHOR]

Fault diagnosis plays an important role in maintaining the reliability of interconnection networks. Let v be a given node in an interconnection network G. v is conditionally locally t -diagnosable in G if the fault or fault-free status of node v can be identified correctly when the number of faults presented does not exceed t and every node has at least one healthy neighboring node. The conditional local diagnosis can be regarded as a local strategy toward the conditional diagnosis of networks, which puts more emphasis on identifying the status of a particular processor. In this paper, we first show a sufficient condition for a regular network to be conditionally locally t -diagnosable at a given node under the MM* model. As its applications, we derive the conditional diagnosability of hierarchical star network H S n etc. We also design an algorithm under the MM* model to identify the fault or fault-free status of a given processor in a regular network. According to our result, an α -regular network with a balanced three-tiered tree T (v ; α , α − 1 , β) rooted at v is conditionally locally (2 α + β − 3) -diagnosable at node v and the time complexity of our algorithm to diagnose v is o (α 2 β 2). As an application, we show our algorithm can identify the status of each node of star graph S n if the fault node number does not exceed 3 n − 9. Compared with existing algorithms, our algorithm allows more faults to arise in a network. [ABSTRACT FROM AUTHOR]

A graph G is a B 0 -VPG graph if one can associate a horizontal or vertical path on a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect in at least one grid-point. A graph G is a contact B 0 -VPG graph if it is a B 0 -VPG graph admitting a representation with no one-point paths, no two paths crossing, and no two paths sharing an edge of the grid. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B 0 -VPG graphs within four special graph classes: chordal graphs, tree-cographs, P 4 -tidy graphs and P 5 -free graphs. Moreover, we present a polynomial-time algorithm for recognising chordal contact B 0 -VPG graphs. [ABSTRACT FROM AUTHOR]

Given a real number α ∈ (0 , 1) , we define the Webster sequence of density α to be W α = (⌈ (n − 1 / 2) / α ⌉) n ∈ N , where ⌈ x ⌉ is the ceiling function. It is known that if α and β are irrational with α + β = 1 , then W α and W β partition N. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of N into sequences W α , W β , W γ with α , β , γ irrational. In this paper, we consider the question of how close one can come to a three-part partition of N into Webster sequences with prescribed densities α , β , γ. We show that if α , β , γ are irrational with α + β + γ = 1 , there exists a partition of N into sequences of densities α , β , γ , in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the n th element of each sequence in O (1) time and the second algorithm gives the assignment of the m th positive integer to a sequence in O (1) time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems. [ABSTRACT FROM AUTHOR]

In this paper we present efficient algorithms to compute the radius, diameter, incenter, circumcenter, width and k dimensional enclosing cylinder for convex polyhedral and convex polyhedral offset distance functions in plane and in ℜ d for several types of inputs. We get optimal algorithms when the time complexities are linear. Let the size of input (convex polyhedron P /set S of points/convex polyhedra) be n / N , respectively, size of distance function convex polygon/polyhedron Q be m and size of constraint convex polyhedral region R be r in plane or ℜ d. The radius, incenter and circumcenter of the convex polygon P in ℜ 2 can be optimally computed in linear time, i.e. O (n + m) and in time O (n + m + r) , if the incenter or circumcenter is additionally constrained in a convex polygon/polyhedron R. In ℜ d , the radius, incenter and circumcenter of a convex polyhedron as well as of a set of convex polyhedra, unconstrained or constrained, can be computed in O (N m) and O (N m + r) time respectively, for convex constraint polyhedral region R. We also compute the minimum stabbing sphere for a set of convex polyhedra, unconstrained or constrained, for the above mentioned distance functions in O (N m) -time or O (N m + r) -time respectively for convex constraint polyhedral region R in ℜ d. The diameter of a convex polygon in plane can be computed in O (n + m) time and the diameter of a convex polyhedron in ℜ d can be computed in O (n m) time. The width of a convex polyhedron can be computed in O (n + m) time and O (n 2 m) time, for ℜ 2 and ℜ d , respectively. The diameter and width of a set of convex polyhedra can be computed in O (N m) -time and (N 2 m) , respectively, in any dimensions. We also show how the k dimensional minimum enclosing/stabbing cylinder for the convex polyhedron P can be computed in O (n d − k + 2 m 2) in ℜ d and in O (n d m (n + m)) in ℜ d for k = 1. The k dimensional minimum enclosing/stabbing cylinder for the set of convex polyhedra S in ℜ d can be computed in O (N d − k + 2 m 2) -time. The diameter and width problems can also be solved for a set of points in ℜ d , either in time O (n m) or in time O (m T (n)) , where T (n) is the time complexity of the best convex hull computation algorithm for the given set of points. [ABSTRACT FROM AUTHOR]

In an undirected graph, a proper (k , i) -coloring is an assignment of a set of k colors to each vertex such that any two adjacent vertices have at most i common colors. The (k , i) -coloring problem is to compute the minimum number of colors required for a proper (k , i) -coloring. This is a generalization of the classical graph coloring problem. We design a parameterized algorithm for the (k , i) -coloring problem with the size of the feedback vertex set as a parameter. Our algorithm does not use tree-width machinery, thus answering a question of Majumdar, Neogi, Raman and Tale [CALDAM 2017]. We also give a faster exact algorithm for (k , k − 1) -coloring. From the hardness perspective, we show that the (k , i) -coloring problem is NP-complete for any fixed values i , k , whenever i < k , thereby settling a conjecture of Méndez-Díaz and Zabala (1999) and again asked by Majumdar, Neogi, Raman and Tale. The NP-completeness result improves the partial NP-completeness shown in the preliminary version of this paper published in CALDAM 2018. [ABSTRACT FROM AUTHOR]

Lattice problems are algorithmic problems for lattices, whose hardness assures the security of lattice-based cryptography. Given a basis of a lattice, the goal of lattice basis reduction is to seek a new basis of the same lattice whose basis vectors are relatively short and nearly orthogonal to each other. Such reduction algorithms give a fundamental tool to solve lattice problems such as the shortest and the closest vector problems. In this paper, we provide a new self-dual variant of the DeepBKZ reduction algorithm. Our variant dynamically switches performing primal and dual reductions for local blocks of an input basis to effectively reduce the whole basis. In particular, we introduce a parameter of free dimensions to determine the sizes of local blocks to be reduced. We also implement our self-dual DeepBKZ to report its experimental results for random lattice bases. [ABSTRACT FROM AUTHOR]

A dominating set D of a graph G is a set of vertices such that any vertex in G is in D or its neighbor is in D. Enumeration of minimal dominating sets in a graph is one of the central problems in enumeration study since enumeration of minimal dominating sets corresponds to the enumeration of minimal hypergraph transversals. The output-polynomial time enumeration of minimal hypergraph transversals is an interesting open problem. On the other hand, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a k -degenerate graph in O k time per solution using O n + m space, where n and m are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, H -minor free graphs with some fixed H. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine. [ABSTRACT FROM AUTHOR]

A proper coloring of a given graph is an assignment of a positive integer number (color) to each vertex such that two adjacent vertices receive different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the colors assigned to the vertices. We propose the first branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with an exponential number of variables which is tackled by column generation. We present extensive computational experiments, on synthetic and benchmark DIMACS graphs from the literature, to compare the performance of our newly developed branch-and-price algorithm against three compact IP formulations. On synthetic graphs, our algorithm outperforms the compact formulations in terms of: (i) number of solved instances, (i i) running times and (i i i) exit gaps obtained when optimality is not achieved. For the DIMACS instances, our algorithm is competitive with the best compact formulation and provides very strong dual bounds. [ABSTRACT FROM AUTHOR]

Azam et al. (2018) proposed a method to enumerate all pairwise compatibility graphs (PCGs) with a given number n of vertices. For a tuple (G , T , σ , λ) of a graph G with n vertices and a tree T with n leaves, a bijection σ between the vertices in G and the leaves in T , and a bi-partition λ of the set of non-adjacent vertex pairs in G , they formulated two linear programs, LP (G , T , σ , λ) and DLP (G , T , σ , λ) such that: exactly one of them is feasible; and G is a PCG if and only if LP (G , T , σ , λ) is feasible for some tuple (G , T , σ , λ). To reduce the number of graphs G with n vertices (resp., tuples) for which the LPs are solved, they excluded PCGs by heuristically generating PCGs (resp., some tuples that contain a sub-tuple (G ′ , T ′ , σ ′ , λ ′) for n = 4 whose LP (G ′ , T ′ , σ ′ , λ ′) is infeasible). This paper proposes two improvements in the method: derive a sufficient condition for a graph to be a PCG for a given tree in order to exclude more PCGs; and characterize all sub-tuples (G ′ , T ′ , σ ′ , λ ′) for n = 4 for which LP (G ′ , T ′ , σ ′ , λ ′) is infeasible, and enumerate tuples that contain no such sub-tuples by a branch-and-bound algorithm. Experimental results show that our method more efficiently enumerated all PCGs for n = 8. [ABSTRACT FROM AUTHOR]

Finding communities in the form of cohesive subgraphs is a fundamental problem in network analysis. In domains that model networks as undirected graphs, communities are generally associated with dense subgraphs, and many community models have been proposed. Maximal cliques are arguably the most widely studied among such models, with early works dating back to the '60s, and a continuous stream of research up to the present. In domains that model networks as directed graphs, several approaches for community detection have been proposed, but there seems to be no clear model of cohesive subgraph, i.e. , of what a community should look like. We extend the fundamental model of clique to directed graphs, adding the natural constraint of strong connectivity within the clique. We consider in this paper the problem of listing all maximal strongly connected cliques in a directed graph. We first investigate the combinatorial properties of strongly connected cliques and use them to prove that every n -vertex directed graph has at most 3 n / 3 maximal strongly connected cliques. We then exploit these properties to produce the first algorithms with polynomial delay for enumerating maximal strongly connected cliques: a first algorithm with polynomial delay and exponential space usage, and a second one, based on reverse-search, with higher (still polynomial) delay but which uses linear space. 1 1 An extended abstract based on the exponential space algorithm appeared in Conte et al. (2017) [14]. [ABSTRACT FROM AUTHOR]

Salsa and ChaCha are two of the most well-known stream ciphers in last two decades. These two ciphers came into the picture when a massively used cipher RC4 was going through severe cryptanalysis and a significant number of observed weaknesses of it showed the requirement of new stream ciphers in the market. Later, ChaCha was adopted by Google as their encryption algorithm, which further increased the importance of research work on these two ciphers. Salsa and ChaCha have gone through differential key recovery attack up to the 8-th and 7-th round respectively. Initially, this attack used an experimentally observed distinguisher by observing a single bit position up to the 4th round for Salsa and 3rd round for ChaCha. Later, Maitra (2016) improved the attack complexity by minimizing the propagation of the difference after the first round using properly chosen IV values. Also, using this distinguisher, Choudhuri et al. (FSE 2016) provided a technique to construct a distinguisher for the next round of both the ciphers by observing multiple bits. Among all these attacks which were mostly based on experimental observations, theoretical works did not get much importance for these two ciphers. In this paper, we aim to theoretically investigate the reason behind these experimentally observed distinguishers for these chosen IV distinguishers, where the difference propagation is minimized up to the first round. We provide a mathematical proof of the observed probabilities for the distinguishers of both the ciphers in the single and multiple bits. [ABSTRACT FROM AUTHOR]

In this paper, we study the dualization in distributive lattices, a generalization of the well-known hypergraph dualization problem. We in particular propose equivalent formulations of the problem in terms of graphs, hypergraphs, and posets. It is known that hypergraph dualization amounts to generate all minimal transversals of a hypergraph, or all minimal dominating sets of a graph. In this new framework, a poset on vertices is given together with the input (hyper)graph, and minimal "ideal solutions" are to be generated. This in particular allows us to study the complexity of the problem under various combined restrictions on graph classes and poset types, including bipartite, split, and co-bipartite graphs, and variants of neighborhood inclusion posets. For example, we show that while the enumeration of minimal dominating sets is possible with linear delay in split graphs, the problem, within the same class, gets as hard as for general graphs when generalized to this framework. More surprisingly, this result holds even when the poset is only comparing vertices with included neighborhoods in the graph. If both the poset and the graph class are sufficiently restricted, we show that the dualization is tractable relying on existing algorithms from the literature. [ABSTRACT FROM AUTHOR]

We prove a general result demonstrating the power of Lagrangian relaxation in solving constrained maximization problems with arbitrary objective functions. This yields a unified approach for solving a wide class of subset selection problems with linear constraints. Given a problem in this class and some small ε ∈ (0 , 1) , we show that if there exists an r -approximation algorithm for the Lagrangian relaxation of the problem, for some r ∈ (0 , 1) , then our technique achieves a ratio of r r + 1 − ε to the optimal, and this ratio is tight. Using the technique we obtain (re)approximation algorithms for natural (reoptimization) variants of classic subset selection problems, including real-time scheduling, the maximum generalized assignment problem (GAP) and maximum weight independent set. For all of the problems studied in this paper, the number of calls to the r -approximation algorithm, used by our algorithms, is linear in the input size and in log (1 ∕ ε) for inputs with a cardinality constraint, and polynomial in the input size and in log (1 ∕ ε) for inputs with an arbitrary linear constraint. [ABSTRACT FROM AUTHOR]