CS Paper Radar

Vertex Ordering for Exact Triangle Listing: Concave Geometry and Certified Rounding

Kourosh Mirsohi, Melika Gorgi, Erfan Hajihashemi

cs.DS ·submitted 2026-10-16 23:28 UTC · v1
theory

Abstract

Exact forward triangle listers orient each edge of a graph by a vertex order. The order does not change the output, but it changes the work. For the adaptive lister, which scans the smaller of the two forward neighborhoods, the number of candidate tests is a known sum of minima of forward degrees, but how to optimize it had not been characterized. We show that this work is a concave function of the forward degrees, so choosing an order is concave minimization over the orientation polytope, whose vertices are the forward-degree vectors of orders. A single sort therefore rounds any point of the polytope, including the out-degree vector of any orientation, to an order with no more work, with a computable lower bound on the improvement. Minimizing the work is nevertheless NP-hard and APX-hard on triangle-free graphs of maximum degree three, and under the Unique Games Conjecture it has no polynomial-time constant-factor approximation. We also analyze logistic score relaxations and the large-graph limit of degree-based orders; on random cubic graphs, the expected work of every degree-based order is asymptotically at least $2.43$ times the expected optimum. Tangent refinement followed by iterated local search reduces the work by \HeldTIKMean\% on average on nine held-out networks fixed by a pre-registered protocol, and by \NSFrozenTILSMean\% in a supplementary rescoring, specified in advance, against a stronger reference that adds the published Neigh local search. The gains are in candidate tests; we observe no reproducible wall-clock speedup.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs

cs.DS ·2026-10-19 ·Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang, Pravesh Kothari, Euiwoong Lee +2 more
theory similarity 0.65
Abstract · 70 Pages

We give a polynomial-time algorithm that achieves an $α_{GW} + \tildeΩ(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints. This improves on the $α_{GW}+\tildeΩ(1/d^2)$-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show a matching Unique Games hardness under randomized polynomial-time reductions, thereby proving that the gain on $α_{GW}$ is optimal up to $\mathrm{polylog}(d)$ factors. Here, $α_{GW} \approx 0.878$ is the approximation ratio of the Goemans-Williamson algorithm. Our results resolve an open question due to Raghavendra and refute his conjectured optimal approximation ratio of $α_{GW} + \tildeΩ(1/\sqrt{d})$. Our local improvement scheme can be thought of as using an adaptive (based on the neighbors) shift applied to the Gaussian before using the GW sign rounding. This allows us to implement a ``soft but simultaneous'' flipping decision at each vertex as opposed to hard but sequential flipping decisions in prior works. Our hardness results are based on a new sparsification lemma for graphs produced by the reduction from Unique Games [Khot-Kindler-Mossel-O'Donnell, SICOMP'07] that preserves the optimal values up to a factor of $1 \pm ε$ while subsampling to an average degree of only $\tilde{O}(1/ε)$. This is the first example of a CSP in which the optimal advantage on degree-$d$ instances is asymptotically smaller than $O(1/\sqrt{d})$ [Trevisan, STOC'01]. A key idea in the proof of our sparsification theorem establishes new bounds on the number of ``nearly optimal'' cuts in the output of the KKMO reduction. This step, in turn, relies on a new, robust inverse Majority-Is-Stablest theorem.

0.15

Minimum Sum Vertex Cover via Minimum Vertex Cover

cs.DS cs.DM ·2026-09-22 ·Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak, Michiel Smid
theory similarity 0.63
Abstract

The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered. We study the problem through the structure of vertex covers and obtain new approximation and exact algorithms, together with conditional lower bounds. For graphs of maximum degree $Δ$, we show that a simple ordering algorithm based on a minimum vertex cover achieves approximation ratio $R_Δ\le {(\sqrtΔ+1)}/{2}$. For $d$-regular graphs, we give a polynomial-time $1.184$-approximation by combining Max-$k$-Vertex-Cover approximation with a structural bound on optimal prefixes. On the exact side, we give an algorithm parameterized by the vertex cover number $k$ running in $2^{O(k\log k)} + O(n+m)$ time, improving the previous dependence on $k$, where $n$ and $m$ are the number of vertices and edges in the graph, respectively. We also develop a separator-based exact algorithm running in $ 2^{O(\sqrt n \log n)}$ time on planar, bounded-genus, and fixed-minor-free graph classes. Finally, we prove that Minimum Sum Vertex Cover is NP-hard on planar graphs and, assuming ETH, admits no $2^{o(\sqrt n)}$-time exact algorithm on $n$-vertex planar graphs. Thus our planar upper bound is tight up to logarithmic factors in the exponent.

0.20

Parallel Edge Ranking of Trees

cs.DS ·2026-10-08 ·Jeff Giliberti, MohammadTaghi Hajiaghayi, Changki Yun
theory similarity 0.61
Abstract

In this work, we prove that computing the edge ranking of a tree in parallel is P-Complete, and complement this hardness with new algorithmic results for both PRAM and the MPC model. An optimal tree edge ranking assigns positive integer ranks to the edges such that any two edges with the same rank are separated by an edge of higher rank, while minimizing the highest rank. Although an optimal edge ranking, which minimizes the maximum rank, can be computed in polynomial time sequentially, its parallel complexity has remained open for almost 35 years [de la Torre, Greenlaw, Schäffer, SODA'93] and was listed as an open problem in Limits to Parallel Computation [Greenlaw, Hoover, Ruzzo, 1995]. Specifically, we show that deciding whether a tree has edge ranking at most $K$ is P-complete, already for trees of diameter at most six. Our reduction encodes monotone circuit evaluation into a greedy allocation procedure underlying known sequential algorithms. Using a rooted product of trees, we further prove that computing an edge ranking within constant additive error remains P-hard. On the algorithmic side, we break the long-standing 2-approximation barrier by designing a deterministic NC algorithm that computes an $(1+o(1))$-approximate edge ranking. Second, we show that P-completeness can be bypassed in Massively Parallel Computation (MPC) with strongly sublinear local memory: we give a deterministic algorithm that computes an optimal edge ranking of an $n$-vertex, diameter-$D$ tree in $O(\log D + \frac{n^{3/4}D^{1/4}}{S})$ rounds with $S = Θ(n^{3/4+δ})$ local memory, for $δ\in (0, 1/4)$, requiring only $O(1)$ rounds on the hard diameter-six instances. This result reinforces the separation between $\mathsf{NC}$ and what can be computed efficiently in MPC.

0.30

Fixed-Threshold Peeling in Sublinear MPC: Round-Approximation Tradeoffs and Applications

cs.DS ·2026-08-10 ·Slobodan Mitrović, Theodore Pan, Wen-Horng Sheu
similarity 0.60
Abstract

A number of fundamental graph problems admit simple algorithms based on iterative peeling: repeatedly remove all vertices whose current degree is below a fixed threshold. This paradigm underlies algorithms for density-dependent edge orientation, density-dependent coloring, densest subgraph, and $k$-core decomposition. In this paper, we study these problems in the sub-linear MPC model and achieve the following round-approximation tradeoffs. For density-dependent edge orientation, given any integer $t > 0$, we compute an orientation with maximum out-degree at most $(2+ε)(t+1)α(G)$ in $O(\lg^{1/(t+2)} n \cdot \operatorname{poly}(\lg \lg n))$ rounds, where $α(G)$ denotes the minimum possible maximum out-degree of an orientation of $G$. In the $\operatorname{poly}(\lg\lg n)$-round regime, this gives an $O(\lg\lg n/\lg\lg\lg n)$-approximation, improving the approximation factor of the recent work by Ghaffari and Grunau [PODC 2025]. We obtain a similar improvement for density-dependent coloring. For densest subgraph, we obtain a $(4+ε)$-approximation in $\widetilde O(\lg^{1/3} n)$ MPC rounds and a $(6+ε)$-approximation in $\widetilde O(\lg^{1/4} n)$ MPC rounds. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrović [ICML 2019] with a slightly larger approximation factor. This is the first $O(1)$-approximate algorithm for densest subgraph to break the $Θ(\sqrt{\lg n})$ round-complexity barrier in the sub-linear MPC model. For $k$-core decomposition, given any integer $t > 0$, we compute approximate coreness values within a factor of $(2+ε)(t+1)$ in $O(\lg^{1/(t+2)} n \cdot \operatorname{poly}(\lg \lg n))$ MPC rounds for any integer $t > 0$. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrović [ICML 2019], again giving a round-approximation tradeoff.

0.04

Orientations without transitive arcs for cubic graphs and phylogenetic networks

cs.CC cs.DMmath.COq-bio.PE ·2026-08-20 ·Janosch Döcker, Simone Linz
similarity 0.60
Abstract

An $st$-orientation of an undirected graph $G$ is an acyclic digraph with a single source $s$ and a single sink $t$ that can be obtained from $G$ by assigning a direction to each edge. The classical problem of deciding if an undirected graph $G$ has an $st$-orientation can be solved efficiently. On the other hand, deciding if an $st$-orientation of $G$ exists that does not have any transitive arc is NP-complete, even if each vertex of $G$ has degree at most four. Here we show that this last decision problem remains NP-complete if $G$ is cubic, which settles an open question by Binucci et al. (2025). We obtain NP-completeness for two variants of the problem: (i) $s$ and $t$ are fixed and given as part of the input and (ii) $s$ and $t$ can be chosen freely. We then use these results to investigate the computational complexity of a problem that arises in computational evolution. Specifically, we show that the problem of deciding if an unrooted binary phylogenetic network has an orientation as a rooted binary phylogenetic network without any shortcuts (the analog of a transitive arcs in phylogenetics) is NP-complete. Our results connect the two (mostly) distinct research areas of orienting undirected graphs and orienting unrooted phylogenetic networks.

0.27

Dynamic Edge Orientation via Random Walks: From Trees to Outerplanar Graphs and Beyond

cs.DS ·2026-08-25 ·Gabriel Marques Domingues, Minh Hang Nguyen, Shay Solomon
theory similarity 0.59
Abstract · Abstract truncated to fit arXiv limits

We study the \emph{fully dynamic edge orientation problem}, focusing on \emph{worst-case} time bounds. An undirected graph undergoes edge insertions and deletions, and the goal is to maintain an orientation with small {\em maximum outdegree} (hereafter, outdegree) and small worst-case update time. The outdegree of any orientation is at least $α-1$, where $α$ is the graph's \emph{arboricity}, i.e., the minimum number of forests into which its edge set can be partitioned. When $α= O(1)$, it is long known that both the outdegree and the worst-case update time can be bounded by $O(\log n)$. Despite numerous follow-ups, no $o(\log^3 n)$ worst-case update time is known for maintaining constant outdegree, even for very basic graph families---with a notable exception, \emph{forests}. For forests, a \emph{simple folklore} algorithm maintains outdegree 2 via \emph{random walks}: When an insertion creates a vertex of outdegree 3, the algorithm repeatedly chooses a uniformly random outgoing edge until reaching a vertex of outdegree at most 1, and then flips the resulting directed path. As the underlying graph is cycle-free, the path length is easily shown to be $O(\log n)$ in expectation, and also with high probability for polynomially long update sequences. We prove that this simple random walk paradigm extends to \emph{outerplanar graphs}. Our algorithm maintains constant outdegree with $O(\log n)$ worst-case update time, where the time bound holds in expectation, and also with high probability for polynomially long update sequences. We give a \emph{tight analysis}: outdegree 4 is achievable with $O(\log n)$-length paths, while outdegree 3 incurs $\mathtt{poly}(n)$-length paths. We also extend the argument to $K_{2,t}$-minor-free graphs, for any $t \ge 2$, with the outdegree bound depending only on $t$ and with the same update time guarantees. The locality of [...]

0.27

Orienting mixed graphs for reachability pairs: When the all pairs setting is easier than the general one

cs.DS cs.CC ·2026-10-19 ·Florian Hörsch, Marta Piecyk, Krisztina Szilágyi
similarity 0.59
Abstract

Given a mixed graph $G$ and an ordered pair $(u,v)$ of vertices in $V(G)$, we say that an orientation $\vec{G}$ of $G$ satisfies $(u,v)$ if $v$ is reachable from $u$ in $\vec{G}$. We consider problems in which we seek orientations that satisfy a maximum number of pairs. We distinguish between two different problems. In the most general problem called Fixed Pairs Maximum Mixed Reachability Orientation (FPRO), a multiset $P$ of ordered pairs of vertices in $V(G)$ comes with the input. In the more restricted problem All Pairs Maximum Mixed Reachability Orientation (APRO), $P$ contains exactly one copy of every ordered pair of distinct vertices in $V(G)$. We compare the computational complexity of FPRO and APRO in two ways: First, we show that both FPRO and APRO behave similarly when it comes to approximation. Namely, they both admit an asymptotic approximation, but are unlikely to admit a constant factor approximation. Then, we consider the parameterization with respect to the treewidth of the underlying graph of the input mixed graph. We show that here the complexities of FPRO and APRO differ significantly. While it is well-known that FPRO is NP-hard even when this parameter is 1, we show that APRO is XP with respect to this parameter. On the other hand, we give a $W[1]$-hardness result for APRO.

0.13

What remains of the planar induced minor conjectures?

cs.DM cs.CCcs.DSmath.CO ·2026-11-06 ·Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski
similarity 0.59
Abstract · 26 pages, 7 figures

Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph $H$, Maximum Weight Independent Set and List $3$-Coloring are polynomial-time solvable in $H$-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is $\mathsf{NP}$-hard in graphs excluding the $5\times5$ grid as an induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several $16$-vertex trees, and we introduce a second, independent family of hard instances. We also prove that $3$-Coloring is $\mathsf{NP}$-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless $\mathsf{NP}\subseteq\mathsf{QP}$. On the structural side, we identify planar graphs $H$ for which the structural conjecture holds, while the algorithmic one fails. Thus, constantly dominated balanced separators cannot by themselves explain the tractability of Maximum Weight Independent Set and List $3$-Coloring.

0.15