An algorithm is given that lifts any $\alpha$-approximation for MLA to an $(\alpha+3-2/(\Delta-1))-approximation for the problem, thus obtaining an $O(\sqrt{\log n}\log\log n)-approximation for the more general problem as well.
Abstract
The classical Minimum Linear Arrangement (MLA) problem has been studied extensively. It is known to be NP-hard and it admits an $O(\sqrt{\log n}\log\log n)$-approximation [Feige and Lee, IPL, 2007]. MLA can be defined as follows as design problem: Given a graph $G$ with vertex set $V(G)$, design a path $H$ on the same vertex set that minimizes the linear arrangement cost $\sum_{uv\in E(G)}\textrm{dist}_H(u,v)$, where $\textrm{dist}_H(u,v)$ indicates the distance of $u$ and $v$ in $H$. We initiate the study of the generalization in which $H$ is allowed to be a caterpillar graph of maximum degree at most $\Delta$. Caterpillars are the simplest generalization of paths, having pathwidth one and interpolating between paths and stars via the degree parameter $\Delta$. We give an algorithm that lifts any $\alpha$-approximation for MLA to an $(\alpha+3-2/(\Delta-1))$-approximation for our problem, thus obtaining an $O(\sqrt{\log n}\log\log n)$-approximation for our more general problem as well. Moreover, we derive a $4$-approximation whenever MLA is polynomial-time solvable, in particular, for trees. Complementing these results, we prove NP-hardness for every constant $\Delta\geq 2$, and, in stark contrast to MLA, show it remains NP-hard on trees when $\Delta$ is part of the input.
This paper provides the first truly linear-time approximation scheme for the Densest Subgraph Problem, and uses assignments arising from a flow-based formulation together with a structural carving lemma to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph.
A polynomial-time decoder yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.
Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva· 1 citation
Given graphs $H$ and $F$, the generalized Tur\'{a}n number ${\rm ex}(n,H,F)$ is the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Alon and Shikhelman (J. Combin. Theory Ser. B, 2016) initiated the systematic study of generalized Tur\'{a}n problems. Let $T$ be a tree on $k$ vertices, and write $n=a(k-1)+b$, where $0\leq b<k-1$. Recently, Gerbner and Palmer (Electron. J. Combin., 2026) proposed the following conjecture: for every $r\geq3$, the graph $aK_{k-1}\cup K_b$ maximizes the number of copies of $K_r$ among all $n$-vertex $T$-free graphs. In this paper, we verify their conjecture when $r=k-2$ or $r=k-3\geq5$. More precisely, we show that ${\rm ex}(n,K_r,T)=a\binom{k-1}{r}+\binom{b}{r}$ and characterize all extremal graphs.
Eternal vertex cover problem is a graph protection problem which is a dynamic two player game variant of the classical vertex cover problem. In this game, the minimum number of guards required to protect a graph $G$ is called the eternal vertex cover number of $G$, denoted by $evc(G)$. It is known that for any graph $G$, $\ mvc(G) \le evc(G) \le 2mvc(G)$, where $mvc(G)$ is the vertex cover number of $G$, and that these bounds are generally tight. However, no biconnected graph $G$ achieves $evc(G) = 2mvc(G)$ and no better lower bounds are known for them. In this work, we focus on biconnected graphs in graph families. For infinite graph families $\mathcal{F}$, consider the parameter $\rho(\mathcal{F})=\sup\{r \in \mathbb{R}:\text{ for infinitely many graphs }G \in \mathcal{F},\frac{evc(G)}{mvc(G)}\ge r\}$. No class of biconnected graphs $\mathcal{F}$ is known yet, for which $1<\rho(\mathcal{F})<2$. In this paper, we show that when $\mathcal{F}$ is the family of Halin graphs, $\frac{7}{6} \le \rho(\mathcal{F}) \le \frac{3}{2}$. Halin graphs are $3$-connected and they have treewidth three. To show the lower bound, we construct a family of Halin graphs for which the ratio tends to $\frac{7}{6}$ with increasing graph size. For the upper bound, we give two algorithms. Our first algorithm gives a defense strategy with $\frac{3}{2} mvc(G)$ guards and serves as a $\frac{3}{2}$ factor approximation algorithm to compute the eternal vertex cover number of Halin graphs. This algorithm also gives an upper bound of $\frac{4}{3}$ for $\rho$ for several subclasses of Halin graphs. Our second algorithm attains the upper bound of $\frac{4}{3}$ for caterpillar Halin graphs. Whether computing eternal vertex cover number is NP-hard for Halin graphs remains an open problem, as is the case with treewidth two graphs.
We study a natural extension of Ramsey theory relative to the classes of maximally planar and maximally outerplanar graphs. This can be seen as a continuation of the study of `Planar Ramsey theory', introduced by Axenovich et al. The question we ask is the following: For a fixed family $\mathcal{K}$ of graphs and a pair of graphs $\{H,F\}$, does there exist an integer $r_{\mathcal{K}} (H, F)$ such that for every graph $G \in \mathcal{K}$ with $|G| \geq r_{\mathcal{K}}(H, F)$, every red/blue edge-colouring of $G$ admits a red copy of $H$ or a blue copy of $F$? When such an integer exists, we say $\{H,F\}$ is unavoidable in $\mathcal{K}$,, and otherwise $\{H,F\}$ is avoidable in $\mathcal{K}$. Our work focuses on this problem where $\mathcal{K} = \mathcal{K}_{\mathrm{MOP}}$ and $\mathcal{K} = \mathcal{K}_{\mathrm{MP}}$, which denote the families of maximal outerplanar (MOP) graphs and maximal planar (MP) graphs, respectively. This framework generalises the classical Ramsey problem relative to these classes, as the case with $\mathcal{K} = \{K_n \colon n \geq 2\}$ corresponds to classical Ramsey. We also study the corresponding Ramsey numbers for MOP and MP, which we denote as $r_{\mathrm{MOP}}(H, F)$ and $r_{\mathrm{MP}}(H, F)$. In the case when $\mathcal{K} = \mathcal{K}_{\mathrm{MOP}}$, we completely determine all unavoidable pairs $\{H, F\}$ with $|E(F)| \geq 2$, together with upper bounds and sometimes exact values of $r_{\mathrm{MOP}}(H, F)$. When $\mathcal{K} = \mathcal{K}_{\mathrm{MP}}$, we completely determine all unavoidable pairs in the diagonal case $\{H, H\}$ when $H$ is connected, showing that $H$ must be one of the graphs $P_3$, $P_4$, $P_5$, $K_{1, 3}$ or the fork graph $S_{2,1,1}$. This work opens up further possibilities in the study of Ramsey theory relative to a class, and we offer several open problems in this vein.
The main result shows that the exact average-case complexity of this fundamental problem is $\Theta(nk)$ for every $k \leq n^{c'}$ and some $c'\in (0, 1)$, and reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input.
Cassandra Marcussen, Edward Pyne, R. Rubinfeld et al.· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
