Search

Summary: Fault‐tolerance and self‐organization are critical properties in modern distributed systems. Self‐stabilization is a class of fault‐tolerant distributed algorithms which has the ability to recover from any kind and any finite number of transient faults and topology changes. In this article, we propose a self‐stabilizing distributed algorithm for the 1‐MIS problem under the unfair central daemon assuming the distance‐3 model. Here, in the distance‐3 model, each process can refer to the values of local variables of processes within three hops. Intuitively speaking, the 1‐MIS problem is a variant of the maximal independent set (MIS) problem with improved local optimizations. The time complexity (convergence time) of our algorithm is O(n)$$ O(n) $$ steps and the space complexity is O(logn)$$ O\left(\log n\right) $$ bits, where n$$ n $$ is the number of processes. Finally, we extend the notion of 1‐MIS to p$$ p $$‐MIS for each nonnegative integer p$$ p $$, and compare the set sizes of p$$ p $$‐MIS (p=0,1,2,...$$ p=0,1,2,\dots $$) and the maximum independent set. [ABSTRACT FROM AUTHOR]

We study the approximability of the maximum size independent set (MIS) problem in bounded degree graphs. This is one of the most classic and widely studied NP-hard optimization problems. It is known for its inherent hardness of approximation. We focus on the well known minimum-degree greedy algorithm for this problem. This algorithm iteratively chooses a minimum degree vertex in the graph, adds it to the solution and removes its neighbors, until the remaining graph is empty. The approximation ratios of this algorithm have been widely studied, where it is augmented with an advice that tells the greedy algorithm which minimum degree vertex to choose if it is not unique. Our main contribution is a new mathematical theory for the design of such greedy algorithms for MIS with efficiently computable advice and for the analysis of their approximation ratios. Using this theory we obtain the ultimate approximation ratio of 5/4 for greedy algorithms on graphs with maximum degree 3, which completely solves an open problem from the paper by Halldórsson and Yoshihara (in: Staples, Eades, Katoh, Moffat (eds) Algorithms and computations—ISAAC '95, in 2026 LNCS, Springer, Berlin, Heidelberg, 1995). Our algorithm is the fastest currently known algorithm for MIS with this approximation ratio on such graphs. We also obtain a simple and short proof of the (Δ + 2) / 3 -approximation ratio of any greedy algorithms on graphs with maximum degree Δ , the result proved previously by Halldórsson and Radhakrishnan (Nord J Comput 1:475–492, 1994). We almost match this ratio by showing a lower bound of (Δ + 1) / 3 on the ratio of a greedy algorithm that can use an advice. We apply our new algorithm to the minimum vertex cover problem on graphs with maximum degree 3 to obtain a substantially faster 6/5-approximation algorithm than the one currently known. We complement our algorithmic, upper bound results with lower bound results, which show that the problem of designing good advice for greedy algorithms for MIS is computationally hard and even hard to approximate on various classes of graphs. These results significantly improve on the previously known hardness results. Moreover, these results suggest that obtaining the upper bound results on the design and analysis of the greedy advice is non-trivial. [ABSTRACT FROM AUTHOR]

Parameterized complexity, introduced to efficiently solve NP‐hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity (nd$$ \mathsf{nd} $$) for several graph theoretic problems in P$$ P $$: Maximumb$$ b $$‐Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular‐width (mw$$ \mathsf{mw} $$) and consequently—as nd$$ \mathsf{nd} $$ is a special case of mw$$ \mathsf{mw} $$—by nd$$ \mathsf{nd} $$. However, the proposed novel algorithms allow for improving the computational complexity from time O(f(mw)·n+m)$$ O\left(f\left(\mathsf{mw}\right)\cdotp n+m\right) $$—where n$$ n $$ and m$$ m $$ denote, respectively, the number of vertices and edges in the input graph—to time O(g(nd)+n+m)$$ O\left(g\left(\mathsf{nd}\right)+n+m\right) $$ which is only additive in the size of the input. Then we consider some classical NP‐hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter. [ABSTRACT FROM AUTHOR]

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored \(n\) -vertex undirected graph, vertices \(s\) and \(t\) , and an integer \(k\) , finds an \((s,t)\) -path containing at least \(k\) different colors in time \(2^{k}n^{\mathcal{O}(1)}\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman on finding a path through \(k\) specified vertices. It also implies the first \(2^{k}n^{\mathcal{O}(1)}\) time algorithm for finding an \((s,t)\) -path of length at least \(k\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\) -vertex undirected graph \(G\) , a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\) , a positive integer weight function on the vertices of \(G\) , two sets of vertices \(S,T\subseteq V(G)\) , and integers \(p,k,w\) , and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\) , while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^{2}\log(q+k))}n^{\mathcal{O}(1)}w\) time randomized algorithm for this problem. [ABSTRACT FROM AUTHOR]

Interval scheduling is a basic algorithmic problem and a classical task in combinatorial optimization. We develop techniques for partitioning and grouping jobs based on their starting/ending times, enabling us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in a dynamic setting produces several new results. For (1 + ε) -approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with O (log n ε) update and O (log n) query worst-case time. Our techniques are also applicable in a setting where jobs have weights. We design a fully dynamic deterministic algorithm whose worst-case update and query times are poly (log n , 1 ε) . This is the first algorithm that maintains a (1 + ε) -approximation of the maximum independent set of a collection of weighted intervals in poly (log n , 1 ε) time updates/queries. This is an exponential improvement in 1 / ε over the running time of an algorithm of Henzinger, Neumann, and Wiese [SoCG, 2020]. Our approach also removes all dependence on the values of the jobs' starting/ending times and weights. [ABSTRACT FROM AUTHOR]

A graph is quasi-triangulated if each of its induced subgraphs has a vertex that is either simplicial (its neighbours form a clique) or co-simplicial (its non-neighbours form an independent set) in the induced subgraph. The problem of characterizing quasi-triangulated graphs by minimal forbidden induced subgraphs is open. We show that a graph is quasi-triangulated if it does not contain as induced subgraph any of the graphs C 5 , P 5 , P 3 + P 3 , fence , or their complements. The fence is obtained from a P 4 by substituting two adjacent vertices for each end-vertex of the P 4 and two non-adjacent vertices for each interior vertex of the P 4. We also provide an efficient algorithm to recognize the subclass Q T k , for fixed k ≥ 0 , of quasi-triangulated graphs studied in the literature. [ABSTRACT FROM AUTHOR]

In the well known planted clique problem, a clique (or alternatively, an independent set) of size k is planted at random in an Erdos-Renyi random G(n, p) graph, and the goal is to design an algorithm that finds the maximum clique (or independent set) in the resulting graph. We introduce a variation on this problem, where instead of planting the clique at random, the clique is planted by an adversary who attempts to make it difficult to find the maximum clique in the resulting graph. We show that for the standard setting of the parameters of the problem, namely, a clique of size k = n planted in a random G (n , 1 2) graph, the known polynomial time algorithms can be extended (in a non-trivial way) to work also in the adversarial setting. In contrast, we show that for other natural settings of the parameters, such as planting an independent set of size k = n 2 in a G(n, p) graph with p = n - 1 2 , there is no polynomial time algorithm that finds an independent set of size k, unless NP has randomized polynomial time algorithms. [ABSTRACT FROM AUTHOR]

With the exponential growth of devices, particularly Internet of things (IoT) devices, connecting to wireless networks, existing networks face significant challenges. Spectral efficiency is crucial for uplink, which is the dominant form of asymmetrical network in today's communication landscape, in large-scale connectivity scenarios. In this paper, an uplink transmission scenario is considered and user equipment (UE) aggregation is employed, wherein some users act as cooperative nodes (CNs), and help to forward received data from other users requiring coverage extension, reliability improvement, and data–rate enhancement. Non–orthogonal multiple access (NOMA) technology is introduced to improve spectral efficiency. To reduce the interference impact to guarantee the data rate, one UE can be assisted by multiple CNs, and these CNs and corresponding assisted UEs are clustered into joint transmission pairs (JTPs). Interference-free transmission can be achieved within each JTP by utilizing different successive interference cancellation (SIC) decoding orders. To explore SIC gains and maximize data rates in NOMA–based UE aggregation, we propose a primary user CN–based channel–sorting algorithm for JTP construction and apply a whale optimization algorithm for JTP power allocation. Additionally, a conflict graph is established among feasible JTPs, and a greedy strategy is employed to find the maximum weighted independent set (MWIS) of the conflict graph for subchannel allocation. Simulation results demonstrate that our joint collaborative NOMA (JC–NOMA) design with two–hop multi–path UE aggregation significantly improves spectral efficiency and capacity under limited spectral resources. [ABSTRACT FROM AUTHOR]

The Micali–Vazirani (MV) algorithm for finding a maximum cardinality matching in general graphs, which was published in 1980, remains to this day the most efficient known algorithm for the problem. The current paper gives the first complete and correct proof of this algorithm. The MV algorithm resorts to finding minimum-length augmenting paths. However, such paths fail to satisfy an elementary property, called breadth first search honesty in this paper. In the absence of this property, an exponential time algorithm appears to be called for—just for finding one such path. On the other hand, the MV algorithm accomplishes this and additional tasks in linear time. The saving grace is the various "footholds" offered by the underlying structure, which the algorithm uses in order to perform its key tasks efficiently. The theory expounded in this paper elucidates this rich structure and yields a proof of correctness of the algorithm. It may also be of independent interest as a set of well-knit graph-theoretic facts. Funding: This work was supported in part by the National Science Foundation [Grant CCF-2230414]. [ABSTRACT FROM AUTHOR]

This article looks at the well‐known shortest independent loop set algorithm, which is used to identify an independent loop set in system dynamics models. It addresses the cases where the algorithm fails to find a complete set due to its limitation to geodetic cycles and introduces a modification that has the potential to identify a complete independent loop set in every case while maintaining the efficiency of the original algorithm. The modified algorithm uses second‐shortest paths to complete the loop set. Special attention is given to the creation of the second‐shortest path matrix required for the modified algorithm, and to the application of the algorithm to a model where the independent loop set created by the shortest independent loop set algorithm was previously shown to be incomplete. © 2024 System Dynamics Society. [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 Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to test whether there exists a subset S ⊆ V (G) of size at most k such that G - S is a forest. After a long line of improvement, recently, Li and Nederlof [TALG, 2022] designed a randomized algorithm for the problem running in time O ⋆ (2. 7 k) ∗ . In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in G - S has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and non-negative integers k , ℓ ∈ N , and the objective is to test whether there exists a vertex subset S of size at most k, such that G - S is ℓ edges away from a forest. In this paper, using the methodology of Li and Nederlof [TALG, 2022], we obtain the current fastest algorithms for all these problems. In particular we obtain the following randomized algorithms. Independent Feedback Vertex Set can be solved in time O ⋆ (2. 7 k) . Pseudo Forest Deletion can be solved in time O ⋆ (2. 85 k) . Almost Forest Deletion can be solved in time O ⋆ (min { 2. 85 k · 8. 54 ℓ , 2. 7 k · 36. 61 ℓ , 3 k · 1. 78 ℓ }) . [ABSTRACT FROM AUTHOR]

In 2018, J. M. Gómez et al. showed that the problem of finding the packing number ρ(F2(Pn)) of the 2-token graph F2(Pn) of the path Pn of length n ≥ 2 is equivalent to determining the maximum size of a binary code S' of constant weight w = 2 that can correct a single adjacent transposition. By determining the exact value of ρ(F2(Pn)), they proved a conjecture of Rob Pratt. In this paper, we study a related problem, which consists of determining the packing number ρ(F3(Pn)) of the graph F3(Pn). This problem corresponds to the Sloane's problem of finding the maximum size of S' of constant weight w = 3 that can correct a single adjacent transposition. Since the maximum packing set problem is computationally equivalent to the maximum independent set problem, which is an NP-hard problem, then no polynomial time algorithms are expected to be found. Nevertheless, we compute the exact value of ρ(F3(Pn)) for n ≤ 12, and we also present some algorithms that produce a lower bound for ρ(F3(Pn)) with 13 ≤ n ≤ 44. Finally, we establish an upper bound for ρ(F3(Pn)) with n ≥ 13. [ABSTRACT FROM AUTHOR]

This study devises self-stabilizing algorithms that leverage the expression distance-2 paradigm to compute (i) a maximal distance-2 independent set, wherein selected nodes maintain a separation exceeding two edges, ensuring non-adjacency; and (ii) a minimal dominating set, wherein each external node has at least one node as a neighbor in the dominating set. The efficacy and convergence of the algorithms are established through rigorous proofs within the framework of the expression model. Extensive simulation tests validate the algorithms' proficiency in selecting a minimal subset of nodes across expansive network topologies. These algorithms find practical applications in network operations, particularly in ad hoc and wireless sensor networks for the selection of cluster heads that facilitate critical services. Moreover, the self-stabilizing property of the algorithms guarantees the robust reconfiguration of cluster heads post-failure, thereby preserving network functionality amidst disruptions. [ABSTRACT FROM AUTHOR]

Spectral independence is a recently developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using Lp-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, and Yin, FOCS'13). The non-linearity of Lp-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the Lp-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G (n, d/n), where the previously known algorithms run in time nO(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime. [ABSTRACT FROM AUTHOR]

In the paper, we consider a generalization of the classical assignment problem, which is called the constrained assignment problem with bounds and penalties (CA-BP). Specifically, given a set of machines and a set of independent jobs, each machine has a lower and upper bound on the number of jobs that can be executed, and each job must be either executed on some machine with a given processing time or rejected with a penalty that we must pay for. No job can be executed on more than one machine. We aim to find an assignment scheme for these jobs that satisfies the constraints mentioned above. The objective is to minimize the total processing time of executed jobs as well as the penalties from rejected jobs. The CA-BP is related to some practical applications such as edge computing, which involves selecting tasks and processing them on the edge servers of an internet network. As a result, a motivation of this study is to improve the efficiency of internet networks by limiting the lower bound of the number of objects processed by each edge server. Our main contribution is modifying the previous network flow algorithms to satisfy the lower capacity constraints, for which we design two exact combinatorial algorithms to solve the CA-BP. Our methodologies and results bring novel perspectives into other research areas related to the assignment problem. [ABSTRACT FROM AUTHOR]

In this paper, we focus on Hitting-Set , a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity , we estimate the number of queries to the oracle based on the parameter k , the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d -partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al. (SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1 , ... , A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i , where i ∈ { 1 , 2 , ... , d }. For d = 2 , the GPIS oracle is nothing but BIS oracle. We show that d - Hitting-Set , the hitting set problem for d -uniform hypergraphs, can be solved using O ˜ d (k d log ⁡ n) GPIS queries. Additionally, we also showed that d - Decision-Hitting-Set , the decision version of d - Hitting-Set can be solved with O ˜ d (min ⁡ { k d log ⁡ n , k 2 d 2 }) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d - Decision-Hitting-Set requires Ω (( k + d d )) GPIS queries. [ABSTRACT FROM AUTHOR]

We consider the fair allocation of indivisible items to several agents with additional conflict constraints. These are represented by a conflict graph where each item corresponds to a vertex of the graph and edges in the graph represent incompatible pairs of items which should not be allocated to the same agent. This setting combines the issues of Partition and Independent Set and can be seen as a partial coloring of the conflict graph. In the resulting optimization problem, each agent has its own valuation function for the profits of the items. We aim at maximizing the lowest total profit obtained by any of the agents. In a previous paper, this problem was shown to be strongly NP-hard for several well-known graph classes, e.g., bipartite graphs and their line graphs. On the other hand, it was shown that pseudo-polynomial time algorithms exist for the classes of chordal graphs, cocomparability graphs, biconvex bipartite graphs, and graphs of bounded treewidth. In this contribution, we extend this line of research by developing pseudo-polynomial time algorithms that solve the problem for the class of convex bipartite conflict graphs, graphs of bounded clique-width, and graphs of bounded tree-independence number. The algorithms are based on dynamic programming and also permit fully polynomial-time approximation schemes (FPTAS). [ABSTRACT FROM AUTHOR]

Quantum approximate optimization algorithm (QAOA) is a promising variational quantum algorithm for combinatorial optimization problems. However, the implementation of QAOA is limited due to the requirement that the problems be mapped to Ising Hamiltonians and the nonconvex optimization landscapes. Although the Ising Hamiltonians for many NP hard problems have been obtained, a general method to obtain the Ising Hamiltonians for constrained combinatorial optimization problems (CCOPs) has not yet been investigated. In this paper, a general method is introduced to obtain the Ising Hamiltonians for CCOPs and the Metropolis‐Hastings warm‐starting algorithm for QAOA is presented which can provably converge to the global optimal solutions. The effectiveness of this method is demonstrated by tackling the minimum weight vertex cover (MWVC) problem, the minimum vertex cover (MVC) problem, and the maximal independent set problem as examples. The Ising Hamiltonian for the MWVC problem is obtained first time by using this method. The advantages of the Metropolis‐Hastings warm‐starting algorithm presented here is numerically analyzed through solving 30 randomly generated MVC cases with 1‐depth QAOA. [ABSTRACT FROM AUTHOR]

We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques from the viewpoint of polynomial-time solvability. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. Furthermore, we show that the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs. [ABSTRACT FROM AUTHOR]

Aftershocks of earthquakes can destroy many urban infrastructures and exacerbate the damage already inflicted upon weak structures. Therefore, it is important to have a method to forecast the probability of occurrence of stronger earthquakes in order to mitigate their effects. In this work, we applied the NESTORE machine learning approach to Greek seismicity from 1995 to 2022 to forecast the probability of a strong aftershock. Depending on the magnitude difference between the mainshock and the strongest aftershock, NESTORE classifies clusters into two types, Type A and Type B. Type A clusters are the most dangerous clusters, characterized by a smaller difference. The algorithm requires region-dependent training as input and evaluates performance on an independent test set. In our tests, we obtained the best results 6 h after the mainshock, as we correctly forecasted 92% of clusters corresponding to 100% of Type A clusters and more than 90% of Type B clusters. These results were also obtained thanks to an accurate analysis of cluster detection in a large part of Greece. The successful overall results show that the algorithm can be applied in this area. The approach is particularly attractive for seismic risk mitigation due to the short time required for forecasting. [ABSTRACT FROM AUTHOR]

Given a dataset V of points from some metric space, a popular robust formulation of the k-center clustering problem requires to select k points (centers) of V which minimize the maximum distance of any point of V from its closest center, excluding the z most distant points (outliers) from the computation of the maximum. In this paper, we focus on an important constrained variant of the robust k-center problem, namely, the Robust Matroid Center (RMC) problem, where the set of returned centers are constrained to be an independent set of a matroid of rank k built on V. Instantiating the problem with the partition matroid yields a formulation of the fair k-center problem, which has attracted the interest of the ML community in recent years. In this paper, we target accurate solutions of the RMC problem under general matroids, when confronted with large inputs. Specifically, we devise a coreset-based algorithm affording efficient sequential, distributed (MapReduce) and streaming implementations. For any fixed ε > 0 , the algorithm returns solutions featuring a (3 + ε) -approximation ratio, which is a mere additive term ε away from the 3-approximations achievable by the best known polynomial-time sequential algorithms. Moreover, the algorithm obliviously adapts to the intrinsic complexity of the dataset, captured by its doubling dimension D. For wide ranges of k , z , ε , D , our MapReduce/streaming implementations require two rounds/one pass and substantially sublinear local/working memory. The theoretical results are complemented by an extensive set of experiments on real-world datasets, which provide clear evidence of the accuracy and efficiency of our algorithms and of their improved performance with respect to previous solutions. [ABSTRACT FROM AUTHOR]

A (2, 1)-colouring of a graph is a partition of its vertex set into two independent sets and a clique (any of which may be empty). We present forbidden induced subgraph characterizations for some hereditary graph classes obtained from (2, 1)-colouring by adding restrictions between its parts (e.g., there are no edges between the clique and one of the independent sets). The obtained characterizations yield certifying algorithms to recognize these graph classes, which run in time O (| V | + | E |). All the algorithms presented are straightforward to implement using basic data structures. [ABSTRACT FROM AUTHOR]

This paper studies two scheduling problems involving two agents A and B , where each agent has an independent set of jobs and all jobs are to be processed preemptively on uniform parallel machines. The aims of the two problems are to minimize the objective function value of agent A with the makespan of agent B not exceeding a threshold T. In the first problem, there are m machines and the objective function of agent A is the makespan. In the second problem, there are two machines and the objective function of agent A is the total completion time. For each of the two problems, we propose an optimal algorithm and obtain some extended results. [ABSTRACT FROM AUTHOR]

Self-stabilization is a promising paradigm for designing highly adaptive distributed systems. However, it cannot be realized when the communication between processes is unreliable with some constant probability. To circumvent such impossibility, this paper adopts the concept of loose-stabilization for the first time, which is a practical alternative of self-stabilization, and proposes three systematic approaches to realize loose-stabilization in the atomic-state model with probabilistically erroneous communications , namely, the redundant-state approach, the step-up approach, and the repetition approach. Further, we apply these approaches to design three corresponding loosely-stabilizing algorithms for the maximal independent set problem. • Self-stabilization solutions are precluded for most of non-trivial problems in probabilistic error models. • Loose-stabilization is a relaxed variant of self-stabilization and practically equivalent to it. • Loose-stabilization can circumvent the impossibilities of self-stabilization in probabilistic error models. • Adopt the concept of loose-stabilization in the atomic-state model for the first time. • Three loose-stabilizing algorithms for maximal independent set problem. [ABSTRACT FROM AUTHOR]

• C -probe graphs are graphs having stable sets N for which edges can be added to obtain a supergraph in C. • A graph G is an (r , ℓ) -graph if V (G) can be partitioned into r independent sets and ℓ cliques. • A graph G is well-covered if every maximal independent set is also maximum. • This paper studies the complexity of recognizing probe graphs for the class of (r , ℓ) -well-covered graphs. Let C be a class of graphs. A graph G = (V , E) is C -probe if V (G) can be partitioned into two sets: non-probes N and probes P , where N is an independent set and new edges may be added between some non-probe vertices such that the resulting graph is in the class C. In this case, we say that (N , P) is a C - probe partition of G. In the Unpartitioned Probe problem for a graph class C we are given a graph G and asked whether G has a C -probe partition, i.e., such a problem consist of recognizing the class of C -probe graphs. A graph G = (V , E) is an (r , ℓ) -graph when V can be partitioned into (S 1 , S 2 , ... , S r , K 1 , K 2 , ... , K ℓ) such that S 1 , S 2 , ... , S r are independent sets, and K 1 , K 2 , ... , K ℓ are cliques. A graph G is well-covered if every maximal independent set is also maximum, and it is (r , ℓ) -well-covered if it is well-covered as well as an (r , ℓ) -graph. In this paper, we study the complexity of the Unpartitioned Probe problem for the class of (r , ℓ) -well-covered graphs. We classify all but the (2 , 0) and (1 , 2) cases. [ABSTRACT FROM AUTHOR]

In this paper, we present an approximation algorithm for the maximum independent set (MIS) problem over the class of B 1 -VPG graphs when the input is specified by a B 1 -VPG representation. We obtain a 6 (log n) 2 -approximation algorithm running in O (n (log n) 3) time. This is an improvement over the previously best n -approximation algorithm [J. Fox and J. Pach, Computing the independence number of intersection graphs, in Proc. Twenty-Second Annual ACM-SIAM Symp. Discrete Algorithms (SODA 2011), 2011, pp. 1161–1165, doi:10.1137/1.9781611973082.87] (for some fixed > 0) designed for some subclasses of string graphs, on B 1 -VPG graphs. [ABSTRACT FROM AUTHOR]

The aim of this paper is to develop a new de-neutrosophication technique for single-valued triangular neutrosophic (SVTrN) numbers using the method based on probability density function of the corresponding truth, an indeterminacy and falsity membership functions. Using the proposed ranking technique a methodology for solving neutrosophic linear programming problems involves SVTrN numbers. The method solution process for each objective is solved by independent to the set of individual value of the objectives decision maker's. Then using the concept for comparison of SVTrN numbers, by the aid of the Mellin's transform, we converted neutrosophic numbers into crisp numbers. Finally, the computational results and performance analysis of the proposed algorithm are presented. [ABSTRACT FROM AUTHOR]

We study the greedy independent set algorithm on sparse Erdős–Rényi random graphs G(n,c/n). A large deviation principle was recently established by Bermolen et al. in 2020, however, the proof and rate function are somewhat involved. Upper bounds for the rate function were obtained earlier by Pittel in 1982. Using discrete calculus, we identify the optimal trajectory realizing a given large deviation and obtain the rate function in a simple closed form. In particular, we show that Pittel's bounds are sharp. The proof is brief and elementary. We think the methods presented here will be useful in analyzing the tail behavior of other random processes. [ABSTRACT FROM AUTHOR]

In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. "Classroom" is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part article comprising a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. This article presents the first part of the survey outlining the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part of the survey, we will present a set of techniques to prove upper bounds for dynamic graph problems. In the third part of the survey, we will present a set of techniques to prove lower bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of lower bounds and upper bounds results for their dynamic graph counterparts. Along with theoretical advances, the techniques used in dynamic graphs need attention from an implementation perspective. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey. The survey can also be used to understand the first algorithms for several recent dynamic graph algorithms. [ABSTRACT FROM AUTHOR]

Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithmÕs performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins. [ABSTRACT FROM AUTHOR]

Token Sliding Optimization asks whether there exists a sequence of at most ℓ steps that transforms independent set S into T , where at each step a token slides to an unoccupied neighboring vertex (while maintaining independence). In Token Jumping Optimization , we are instead allowed to jump from a vertex to any unoccupied vertex. Both problems are known to be FPT when parameterized by ℓ on nowhere dense graphs. In this work, we show that both problems are FPT for parameter k + ℓ + d on d -degenerate graphs as well as for parameter | M | + ℓ + Δ on graphs having a modulator M to maximum degree Δ. We complement these results by showing that for parameter ℓ both problems become hard already on 2-degenerate graphs. Finally, we show that using such families one can obtain a unified algorithm for the standard Token Jumping problem parameterized by k on degenerate and nowhere dense graphs. [ABSTRACT FROM AUTHOR]

In dynamical systems, fractals and their features have been proven for a wide range of applications in graphical structures. In particular, self-similar graphs as well as graph polynomials play a vital role. This paper explores the characteristics of the polynomials for the family of well-known self-similar graphs, namely Sierpinski triangle graph of the nth\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n^{\text {th}}$$\end{document} iteration, and proposes an algorithm to compute the multivariate independence polynomials of these graphs. We employ iterative patterns from the Sierpinski triangle graph, and we implement our approach to explicitly compute the independent sets to formulate multivariate independence polynomials for iterative values of n. In addition, the inverse of these polynomials have been computed using SAGE software. [ABSTRACT FROM AUTHOR]

A graph vertex-subset problem defines which subsets of the vertices of an input graph are feasible solutions. We view a feasible solution as a set of tokens placed on the vertices of the graph. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k , whether it is possible to transform one into the other by a sequence of token slides (along edges of the graph) or token jumps (between arbitrary vertices of the graph) such that each intermediate set remains a feasible solution of size k. Many algorithmic questions present themselves in the form of reconfiguration problems: Given the description of an initial system state and the description of a target state, is it possible to transform the system from its initial state into the target one while preserving certain properties of the system in the process? Such questions have received a substantial amount of attention under the so-called combinatorial reconfiguration framework. We consider reconfiguration variants of three fundamental underlying graph vertex-subset problems, namely Independent Set , Dominating Set , and Connected Dominating Set. We survey both older and more recent work on the parameterized complexity of all three problems when parameterized by the number of tokens k. The emphasis will be on positive results and the most common techniques for the design of fixed-parameter tractable algorithms. [ABSTRACT FROM AUTHOR]

For a graph G = (V,E), a Roman {2}-dominating function (R2DF) f: V = {0, 1, 2} has the property that for every vertex v = V with f(v) = 0, either there exists a neighbor u = N(v), with f(u) = 2, or at least two neighbors x, y = N(v) having f(x) = f(y) = 1. The weight of an R2DF f is the sum f(V) = P v2V f(v), and the minimum weight of an R2DF on G is the Roman {2}-domination number {R2}(G). An R2DF is independent if the set of vertices having positive function values is an independent set. The independent Roman {2}-domination number i{R2}(G) is the minimum weight of an independent Roman {2}-dominating function on G. In this paper, we show that the decision problem associated with {R2}(G) is NP- complete even when restricted to split graphs. We design a linear time algorithm for computing the value of i{R2}(T) in any tree T, which answers an open problem raised by Rahmouni and Chellali [Independent Roman {2}- domination in graphs, Discrete Appl. Math. 236 (2018) 408-414]. Moreover, we present a linear time algorithm for computing the value of {R2}(G) in any block graph G, which is a generalization of trees. [ABSTRACT FROM AUTHOR]

Biological sequence families contain many sequences that are very similar to each other because they are related by evolution, so the strategy for splitting data into separate training and test sets is a nontrivial choice in benchmarking sequence analysis methods. A random split is insufficient because it will yield test sequences that are closely related or even identical to training sequences. Adapting ideas from independent set graph algorithms, we describe two new methods for splitting sequence data into dissimilar training and test sets. These algorithms input a sequence family and produce a split in which each test sequence is less than p% identical to any individual training sequence. These algorithms successfully split more families than a previous approach, enabling construction of more diverse benchmark datasets. Author summary: Typically, machine learning and statistical inference models are trained on a "training" dataset and evaluated on an separate "test" set. This ensures that the reported performance accurately reflects how well the method would do on previously unseen data. Biological sequences (such as protein or RNA) within a particular family are related by evolution and therefore may be very similar to each other. In this case, applying a standard approach of randomly splitting the data into training and test sets could yield test sequences that are nearly identical to some sequence in the training set, and the resultant benchmark may overstate the model's performance. This motivates the design of strategies for dividing sequence families into dissimilar training and test sets. To this end, we used ideas from computer science involving graph algorithms to design two new methods for splitting sequence data into dissimilar training and test sets. These algorithms can successfully produce dissimilar training and test sets for more protein families than a previous approach, allowing us to include more families in benchmark datasets for biological sequence analysis tasks. [ABSTRACT FROM AUTHOR]

In d - Scattered Set we are given an (edge-weighted) graph and are asked to select at least k vertices, so that the distance between any pair is at least d , thus generalizing Independent Set. We provide upper and lower bounds on the complexity of this problem with respect to various standard graph parameters. In particular, we show the following: • For any d ≥ 2 , an O ∗ (d tw) -time algorithm, where tw is the treewidth of the input graph and a tight SETH-based lower bound matching this algorithm's performance. These generalize known results for Independent Set. • d - Scattered Set is W[1]-hard parameterized by vertex cover (for edge-weighted graphs), or feedback vertex set (for unweighted graphs), even if k is an additional parameter. • A single-exponential algorithm parameterized by vertex cover for unweighted graphs, complementing the above-mentioned hardness. • A 2 O (td 2) -time algorithm parameterized by tree-depth (td), as well as a matching ETH-based lower bound, both for unweighted graphs. We complement these mostly negative results by providing an FPT approximation scheme parameterized by treewidth. In particular, we give an algorithm which, for any error parameter ε > 0 , runs in time O ∗ ( (tw / ε) O (tw) ) and returns a d / (1 + ε) -scattered set of size k , if a d -scattered set of the same size exists. [ABSTRACT FROM AUTHOR]

An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are known for the existence of an IT in a given graph and vertex partition, which have been used over the years to solve many combinatorial problems. Some of these IT existence theorems have algorithmic proofs, but there remains a gap between the best existential bounds and the bounds obtainable by efficient algorithms. Recently, Graf and Haxell (2018) described a new (deterministic) algorithm that asymptotically closes this gap, but there are limitations on its applicability. In this article, we develop a randomized algorithm that is much more widely applicable, and demonstrate its use by giving efficient algorithms for two problems concerning the strong chromatic number of graphs. [ABSTRACT FROM AUTHOR]

In the classic Maximum Weight Independent Set problem, we are given a graph G with a nonnegative weight function on its vertices, and the goal is to find an independent set in G of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any P6-free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on P5-free graphs of Lokshtanov et al. [15] and the quasipolynomial-time algorithm on P6-free graphs of Lokshtanov et al. [14]. The main technical contribution leading to our main result is enumeration of a polynomial-size family F of vertex subsets with the following property: For every maximal independent set I in the graph, F contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I. [ABSTRACT FROM AUTHOR]

We consider the possibility of circumventing the decomposition problem for the range of values of random variables when testing various hypotheses. A brief review of the literature on this issue is given. A method is proposed for forming sets of independent components of a multidimensional random variable, based on testing hypotheses about the independence of paired combinations of components of a multidimensional random variable. The method uses a two-dimensional nonparametric algorithm for the recognition of kernel-type patterns, corresponding to the criterion of maximum likelihood. In contrast to the traditional technique using Pearson's criterion, the proposed technique avoids the problem of decomposing the range of values of random variables into multidimensional intervals. We present results of computational experiments performed using the method of forming sets of independent random variables. From the obtained data, an information graph is constructed, whose vertices correspond to the components of a multidimensional random variable, and the edges determine their independence, while the vertices of the complete subgraphs correspond to groups of independent components of the random variable. The results obtained form the basis for the synthesis of a multilevel nonparametric system for processing large volumes of data, each level of which corresponds to a specific set of independent random variables. [ABSTRACT FROM AUTHOR]

We present an algorithm that enumerates all the minimal triangulations of a graph in incremental polynomial time. Consequently, we get an algorithm for enumerating all the proper tree decompositions, in incremental polynomial time, where "proper" means that the tree decomposition cannot be improved by removing or splitting a bag. The algorithm can incorporate any method for (ordinary, single result) triangulation or tree decomposition, and can serve as an anytime algorithm to improve such a method. We describe an extensive experimental study of an implementation on real data from different fields. Our experiments show that the algorithm improves upon central quality measures over the underlying tree decompositions, and is able to produce a large number of high-quality decompositions. [ABSTRACT FROM AUTHOR]

Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is faster than the best known algorithm for the exact problem. The running time of our algorithm on general graphs with error tolerance ε is at most O (2 0.2680 n) times a polynomial in 1 / ε. On bipartite graphs, the exponential term in the running time is improved to O (2 0.2372 n). Our methods combine techniques from exact exponential algorithms with techniques from approximate counting. Along the way we generalise (to the multivariate case) the FPTAS of Sinclair, Srivastava, Štefankovič and Yin for approximating the hard-core partition function on graphs with bounded connective constant. Also, we obtain an FPTAS for counting independent sets on graphs with no vertices with degree at least 6 whose neighbours' degrees sum to 27 or more. By a result of Sly, there is no FPTAS that applies to all graphs with maximum degree 6 unless P = NP. [ABSTRACT FROM AUTHOR]

Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an algorithm that approximately counts the number of triangles in a graph using only polylogarithmic queries when the number of triangles on any edge in the graph is polylogarithmically bounded. Our query oracle Tripartite Independent Set (TIS) takes three disjoint sets of vertices A, B and C as inputs, and answers whether there exists a triangle having one endpoint in each of these three sets. Our query model generally belongs to the class of group queries (Ron and Tsur ACM Trans. Comput. Theory 8(4), 15, 2016; Dell and Lapinskas 2018) and in particular is inspired by the Bipartite Independent Set (BIS) query oracle of Beame et al. (2018). We extend the algorithmic framework of Beame et al., with TIS replacing BIS, for approximately counting triangles in graphs. [ABSTRACT FROM AUTHOR]

A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An eulerian factor of a 2-edge-coloured graph is a collection of vertex-disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u, v)-paths ((u, v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u, v. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor. [ABSTRACT FROM AUTHOR]

Biró et al. (Discrete. Math 100(1–3):267–279, 1992) introduced the concept of H-graphs, intersection graphs of connected subgraphs of a subdivision of a graph H. They are related to and generalize many important classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs. Our paper starts a new line of research in the area of geometric intersection graphs by studying several classical computational problems on H-graphs: recognition, graph isomorphism, dominating set, clique, and colorability. We negatively answer the 25-year-old question of Biró, Hujter, and Tuza which asks whether H-graphs can be recognized in polynomial time, for a fixed graph H. We prove that it is NP -complete if H contains the diamond graph as a minor. On the positive side, we provide a polynomial-time algorithm recognizing T-graphs, for each fixed tree T. For the special case when T is a star S d of degree d, we have an O (n 3.5) -time algorithm. We give FPT - and XP -time algorithms solving the minimum dominating set problem on S d -graphs and H-graphs, parametrized by d and the size of H, respectively. The algorithm for H-graphs adapts to an XP -time algorithm for the independent set and the independent dominating set problems on H-graphs. If H contains the double-triangle as a minor, we prove that the graph isomorphism problem is GI-complete and that the clique problem is APX-hard. On the positive side, we show that the clique problem can be solved in polynomial time if H is a cactus graph. Also, when a graph has a Helly H-representation, the clique problem is polynomial-time solvable. Further, we show that both the k-clique and the list k-coloring problems are solvable in FPT-time on H-graphs, parameterized by k and the treewidth of H. In fact, these results apply to classes of graphs with treewidth bounded by a function of the clique number. We observe that H-graphs have at most n O (‖ H ‖) minimal separators which allows us to apply the meta-algorithmic framework of Fomin, Todinca, and Villanger (2015) to show that for each fixed t, finding a maximum induced subgraph of treewidtht can be done in polynomial time. In the case when H is a cactus, we improve the bound to O (‖ H ‖ n 2) . [ABSTRACT FROM AUTHOR]

Prediction of rockburst in underground engineering is of significance as it is close to the safety of support structures, personnel, and working environments. To improve the accuracy of rockburst classification, this paper proposed an ensemble classifier RF-FA model in which the random forest classifier (RF) and firefly algorithm (FA) were combined to achieve the optimum performance on rockburst prediction. Five key parameters of surrounding rock, i.e., the depth H, the maximum tangential stress σθ, the uniaxial compressive strength σc, the tensile strength σt, and the elastic energy index Wet, are selected as input variables while the rockburst intensity including none, light, moderate, and strong classes was chosen as output. A total of 279 cases worldwide were collected and used for train and test the proposed RF-FA model. The results showed that the FA can optimize the hyperparameters of RF efficiently and the optimum model exhibited a high performance on rockburst data from the independent test set and new engineering projects. The feature importance obtained by the ensemble RF-FA model indicated that the elastic energy index plays the most important role in rockburst. Besides, the proposed model showed much better accuracy on rockburst classification compared with previously existing RF models and empirical criteria, which means it is a useful and robust tool for rockburst prediction. [ABSTRACT FROM AUTHOR]

In this paper, we consider a randomized greedy algorithm for independent sets in r‐uniform d‐regular hypergraphs G on n vertices with girth g. By analyzing the expected size of the independent sets generated by this algorithm, we show that α(G)≥(f(d,r)−ϵ(g,d,r))n, where ϵ(g,d,r) converges to 0 as g → ∞ for fixed d and r, and f(d, r) is determined by a differential equation. This extends earlier results of Garmarnik and Goldberg for graphs [8]. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely. [ABSTRACT FROM AUTHOR]

We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d - H I T T I N G S E T that runs in time n O (d 2 + (d / ϵ)) , uses O ((d 2 + (d / ϵ)) log n) bits of space, and achieves an approximation ratio of O ((d / ϵ) n ϵ) for any positive ϵ ≤ 1 and any d ∈ N . In particular, this yields a factor- O (log n) approximation algorithm which runs in time n O (log n) and uses O (log 2 n) bits of space (for constant d). As a corollary, we obtain similar bounds for V E R T E X C O V E R and several graph deletion problems. For bounded-multiplicity problem instances, one can do better. We devise a factor-2 approximation algorithm for V E R T E X C O V E R on graphs with maximum degree Δ , and an algorithm for computing maximal independent sets, both of which run in time n O (Δ) and use O (Δ log n) bits of space. For the more general d - H I T T I N G S E T problem, we devise a factor-d approximation algorithm which runs in time n O (d δ 2) and uses O (d δ 2 log n) bits of space on set families where each element appears in at most δ sets. For I N D E P E N D E N T S E T restricted to graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses O (log n) bits of space. We also devise a factor- O (d 2) approximation algorithm for D O M I N A T I N G S E T on d-degenerate graphs which runs in time n O (log n) and uses O (log 2 n) bits of space. For d-regular graphs, we show how a known randomized factor- O (log d) approximation algorithm can be derandomized to run in time n O (1) and use O (log n) bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms. [ABSTRACT FROM AUTHOR]

We study algorithmic properties of the graph class C H O R D A L - k e , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from C H O R D A L - k e . More precisely, we identify a large class of optimization problems on C H O R D A L - k e solvable in time 2 O (k log k) · n O (1) . Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on C H O R D A L - k e when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of C H O R D A L - k e graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on C H O R D A L - k e graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on C H O R D A L - k e graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of C H O R D A L - k e , namely, I N T E R V A L - k e and S P L I T - k e graphs. [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]