ABSTRACT. We consider the classical makespan minimization scheduling problem where $n$ jobs must be scheduled on $m$ identical machines. Using weighted random sampling, we developed two sublinear time approximation schemes: one for the case where $n$ is known and the other for the case where $n$ is unknown. Both algorithms not only give a $(1+3\epsilon)$-approximation to the optimal makespan but also generate a sketch schedule.

Our first algorithm, which targets the case where $n$ is known and draws samples in a single round under weighted random sampling, has a running time of $\tilde{O}(\tfrac{m^5}{\epsilon^4} \sqrt{n}+A(\ceiling{m\over \epsilon}, {\epsilon} ))$, where $A(\mathcal{N}, \alpha)$ is the time complexity of any $(1+\alpha)$-approximation scheme for the makespan minimization of $\mathcal{N}$ jobs. The second algorithm addresses the case where $n$ is unknown. It uses adaptive weighted random sampling, and runs in sublinear time $\tilde{O}\left( \tfrac{m^5} {\epsilon^4} \sqrt{n} + A(\ceiling{m\over \epsilon}, {\epsilon} )\right)$. We also provide an implementation that generates a weighted random sample using $O(\log n)$ uniform random samples.

ABSTRACT. Suppose that a group test operation is available for checking order relations in a set, can this speed up problems like finding the minimum/maximum element, determining the rank of element, and computing order statistics? We consider a one-sided group inequality test to be available, where queries are of the form $u \le_Q V$ or $V \le_Q u$, and the answer is `yes' if and only if there is some $v \in V$ such that $u \le v$ or $v \le u$, respectively. We restrict attention to total orders and focus on query-complexity; for min or max finding, we give a Las Vegas algorithm that makes $\bigo(\log^2 n)$ expected queries. We observe that rank determination can be solved with existing ``defect-counting'' algorithms, but also give a simple Monte Carlo approximation algorithm with expected query complexity $\softo(\frac{1}{\delta^2} \log \frac{1}{\epsilon})$, where $1-\epsilon$ is the probability that the algorithm succeeds and we allow a relative error of $1 \pm \delta$ for $\delta > 0$ in the estimated rank. We then give a Monte Carlo algorithm for approximate selection that has expected query complexity $\softo(\frac{1}{\delta^4}\log \frac{1}{\epsilon \delta^2} )$; it has probability at least $\frac{1}{2}$ to output an element $x$, and if so, $x$ has the desired approximate rank with probability $1-\epsilon$.

ABSTRACT. In various domination and coverage problems, certain vertices or edges should not be dominated/covered and are designated as vulnerable. Motivated by this, we define the k-Vertex Maximum Domination Ratio with Vulnerable Vertices (k-Max DRVV) problem, which extends the budgeted dominating set problem to include vulnerability constraints. We propose an approximation algorithm based on an unbudgeted variant of k-Max DRVV, termed the Maximum Domination Ratio with Vulnerable Vertices (DRVV) problem. For bounded-degree graphs of order n, our algorithm provides an O(k/n)-approximation for the k-Max DRVV problem. We also introduce the Vertex Cover with Vulnerable Edges (VCVE) problem, which can be naturally expressed as a special case of the Red-Blue Set Cover problem. We develop a 4-approximation algorithm for the VCVE problem.

ABSTRACT. We study the hardness of reoptimization of the fundamental and hard to approximate SetCover problem. Reoptimization considers an instance together with a solution and a modified instance where the goal is to approximate the modified instance while utilizing the information gained from the solution to the related instance. We study four different types of reoptimization for (weighted) SetCover: adding a set, removing a set, adding an element to the universe, and removing an element from the universe. A few of these cases are known to be easier to approximate than the classic SetCover problem. We show that all other cases are essentially as hard to approximate as SetCover. The reoptimization problem of adding and removing an element in the unweighted is known to admit a PTAS. For these settings we show that there is no EPTAS under common hardness assumptions via a novel combination of the classic way to show that a reoptimization problem is NP-hard and the relation between EPTAS and FPT.

ABSTRACT. Let $G$ be a simple (possibly infinite) graph. Our focus is on finding a vertex subset $C \subseteq V(G)$, called a code, that has certain special properties, and minimize the size (or density) of $C$. Given a graph $G$, a fixed code $C$, and an arbitrary vertex subset $F$ of $G$, the $(I,r)$-set of $F$ is defined as $I_r(F) = B_r(F) \cap C$, where $B_r(F)$ is the set of vertices at distance at most $r$ from some vertex of $F$. The code $C$ is an $(r,\leq l)$-LDA code if $I_r(F_1) \neq I_r(F_2)$ whenever $F_1 \neq F_2$, $F_1 \cap C = F_2 \cap C$, and $|F_1|, |F_2| \leq l$ for all $F_1, F_2 \subseteq V(G)$. Similarly, $C$ is an $(r,\leq l)$-LDB code if $I_r(F_1) \neq I_r(F_2)$ whenever $F_1 \neq F_2$, and $|F_1|, |F_2| \leq l$ for all $F_1, F_2 \subseteq V(G) \setminus C$. In particular, $(1,\leq 1)$-LDA and $(1,\leq 1)$-LDB codes are the same, and are popularly known as locating-dominating codes. In this article, we find the exact minimum densities of $(1,\leq l)$-LDA and $(1,\leq l)$-LDB codes in the infinite triangular grid for all $l \geq 2$.

ABSTRACT. A graph $G$ is $k$-vertex-critical if $\chi(G)=k$ but $\chi(G-v)<k$ for all $v\in V(G)$. In this paper we make progress on the open problem of the finiteness of $k$-vertex-critical $(P_4+\ell P_1)$-free graphs by showing that there are only finitely many $k$-vertex-critical graphs in the following subfamilies of $(P_4+\ell P_1)$-free graphs for all $k\ge 1$ and $\ell\ge 0$: \begin{itemize} \item $(P_4+\ell P_1,2P_2)$-free graphs, \item $(P_4+\ell P_1,\text{chair})$-free graphs, \item $(P_4+\ell P_1,P_5,\text{bull})$-free graphs, and \item $(P_4+\ell P_1,P_5,\text{cricket})$-free graphs. \end{itemize}

\noindent In fact, all but the first of these are special cases of our more general result that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,\broom{4}{m},\broom{3}{m}^{+})$-free graphs for all $k\ge 1$ and $\ell,m\ge 0$. Here $\broom{n}{m}$ is the graph obtained from a path of order $n$ by identifying one of its leaves with the centre vertex of $K_{1,m}$ and $\broom{n}{m}^{+}$ is the graph obtained by identifying an edge of $K_3$ with the edge of $\broom{n}{m}$ with endpoints of degrees $2$ and $m$, respectively. Our results imply the existence of simple polynomial-time certifying algorithms to decide the $k$-colourability of all graphs in these subfamilies for every fixed $k$.

We also show that $\chi(G)\le \ell+2$ for all $(P_4+\ell P_1,K_3)$-free graphs and all $\ell\ge 0$, improving the previously known upper bound of $2\ell+2$ that followed from Randerath and Schiermeyer's 2004 result on $(P_t,K_3)$-free graphs.

ABSTRACT. We revisit a classical paper about (even hole, triangle)-free graphs [Conforti, Cornuejols, Kapoor and Vuskovic, Triangle-free graphs that are signable without even holes, Journal of Graph Theory, 34(3), 204--220, 2000]. In fact, the previous study describes a more general class, the so called triangle-free odd signable graphs, and we further generalise the class to the (theta, triangle, wac)-free graphs (not worth defining in an abstract).

We exhibit a stronger structure theorem, by precisely describing basic classes and separators named clique separator, 2-separator and P_3-separator. We prove that, under some additional conditions, the separators preserve the treewidth and several properties. Some consequences are a recognition algorithm with running time O(|V(G)|^4|E(G)|), a proof that the treewidth of graphs in the class is at most 4 (improving a previous bound of 5), and a simple criterion to decide if a graph in the class is planar.