CS Paper Radar

Complexity, approximation, and extension of proper $\{a,b\}$-edge-weightings

Péter Madarasi, Máté Simon

cs.DM cs.CCmath.CO ·submitted 2026-09-25 12:44 UTC · v1
theory

Abstract

For distinct integers $a$ and $b$, an $\{a,b\}$-edge-weighting assigns $a$ or $b$ to each edge and labels each vertex by the sum of its incident weights. Such a weighting is proper if adjacent vertices receive distinct labels. We prove that, for every fixed pair of distinct integers, deciding whether a proper weighting exists is NP-complete even for simple cubic planar graphs. On planar multigraphs with $m$ edges, we give an exact $2^{O(\sqrt m)}$-time algorithm and, assuming the Exponential Time Hypothesis (ETH), exclude $2^{o(\sqrt m)}$-time algorithms even for simple cubic planar graphs. As a consequence, locally irregular $2$-edge-coloring is NP-complete on simple cubic planar graphs, admits a deterministic $2^{O(\sqrt n)}$-time algorithm on $n$-vertex graphs in this class, and admits no $2^{o(\sqrt n)}$-time algorithm under ETH. For maximizing the number of edges joining vertices with distinct labels, we give a deterministic efficient polynomial-time approximation scheme (EPTAS) on planar multigraphs, a polynomial-time $1/2$-approximation on multigraphs, and APX-completeness even on simple cubic graphs. Extending a partial $\{a,b\}$-edge-weighting to a proper one is NP-complete for every fixed pair even on simple cubic planar bipartite graphs, while it is polynomial-time solvable on trees. The hardness persists even when the prescribed edges form disjoint paths of length $6$ and all edges of each path have the same prescribed weight.

Closest papers

Nearest neighbours by meaning across the whole index.

Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path

cs.CC cs.DMmath.CO ·2026-11-10 ·Jan Diester, Kolja Kühn, Manuel Rapp, Samuel Schneider, Torsten Ueckerdt
similarity 0.70
Abstract

We examine the computational complexity of well-known problems on subgraphs of the strong product of two paths. Namely, for Max Cut we show NP-hardness on induced subgraphs of $P \boxtimes P$ answering a question by Dvořák, Huynh, Joret, Liu, and Wood (2021). For 3-Edge Coloring we show NP-hardness on subgraphs of $P \boxtimes P$ and that it is equivalent to 3-Edge Coloring on planar graphs for induced subgraphs of $P \boxtimes P$. It is a long standing open question whether 3-Edge Coloring on planar graphs is NP-hard. As a second contribution, we consider graphs of the form $G \boxtimes P$ and show that Feedback Vertex Set on these graphs is FPT in the clique-width of $G$. Furthermore, we show that it can be solved in polynomial time if $G$ is chordal or co-comparable and that the computational complexity depends on the parity of $P$ if $G$ is bipartite. Namely, it is solvable in polynomial time if $P$ has an even number of vertices but is NP-complete otherwise. For Max Cut, we show that it can be solved in polynomial time if $G$ is bipartite.

0.06

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.70
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

Odd Cycle Transversal on $H$-free graphs

cs.DS cs.DMmath.CO ·2026-09-25 ·Esther Galby, Paloma T. de Lima, Andrea Munaro, Amir Nikabadi
similarity 0.68
Abstract

\textsc{Odd Cycle Transversal} is a classic $\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite, or equivalently, a maximum-weight induced bipartite subgraph. We show that \textsc{Odd Cycle Transversal} is quasi-polynomial-time solvable on $kP_4$-free graphs, for every fixed $k \in \mathbb{N}$. In fact, we provide an $n^{O_k(\log n)}$-time algorithm for the more general \textsc{Max-Weight List $2$-Colorable Induced Subgraph}, where the notation $O_{k}(\cdot)$ hides factors depending on $k$. Paired with known results from the literature, this allows us to obtain a complete complexity dichotomy for these two problems on $H$-free graphs into cases solvable in quasi-polynomial time and cases which are $\mathsf{NP}$-hard, in particular resolving an open problem of Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024]. Our algorithms are based on a new structural tool that may be of independent interest. We introduce the notion of $H$-amiable family and show that, for every fixed graph $H$ without isolated vertices and every fixed $k\ge2$, every $kH$-free graph admits an $H$-amiable family of quasi-polynomial size that can be constructed in quasi-polynomial time. Besides yielding the aforementioned algorithms, this result gives, for every fixed connected graph $H$ and every fixed $k\ge2$, a reduction from \textsc{Max-Weight Independent Set} on $kH$-free graphs to the same problem on $H$-free graphs with $n^{O_{H,k}(\log n)}$ overhead. In this setting, it improves the $n^{O_{H,k}(\log^3 n)}$ overhead obtained by specializing the general reduction of Gartland and Lokshtanov [FOCS 2020].

0.16

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

cs.DS cs.CC ·2026-10-05 ·Josh Alman, Virginia Vassilevska Williams
highly cited similarity 0.67
Abstract · 76 pages

We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial size in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs with polynomially bounded integer weights in $O(n^{2.9995})$ time. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the $3$SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight $k$-Clique hypotheses, and the three rectangular hinted Online Matrix--Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems. All of these results follow from a single new algorithm for thin matrix products. Let $X$ be an $N\times D$ integer matrix and $Y$ a $D\times N$ integer matrix with $D\le N^{1/18}$, and let $W$ be any set of at most $N^2/\sqrt D$ positions. We compute the entries $(XY)[I,J]$, $(I,J)\in W$, in $O(N^2/D^{0.063})$ operations, which is polynomially less than the time needed to write down $XY$ or to compute $N^2/\sqrt D$ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in $W$, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have $n$ vertices but one part has $n^{\varepsilon}$ vertices for $\varepsilon<0.12$. By known reductions, Exact Triangle, and hence $3$SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of $XY$, not known in advance.

0.51

Structural Complexity of Matching-Match: Dense and Sparse Graphs

cs.DS ·2026-09-22 ·Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
theory similarity 0.67
Abstract

The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We study how the complexity of this realization problem depends on the host graph. On the dense side, we give a polynomial-time algorithm for complete $k$-partite graphs for every fixed number $k$ of parts, with arbitrary precoloring and an arbitrary number of colors. We prove a sharp complement-degree threshold: the problem is polynomial-time solvable when $Δ(\overline G)\le1$, but NP-complete on completely uncolored graphs already when $Δ(\overline G)=2$. This yields a dichotomy for uniform complete multipartite graphs, and connected diameter two already suffices for NP-completeness. We also prove W[1]-hardness on cographs parameterized by the number of colors. On the sparse side, completely uncolored paths and cycles admit a linear-time characterization by Euler trails and circuits, while counting feasible colorings is $\#P$-complete on both classes. Counting is nevertheless polynomial-time solvable on stars and complete graphs, even with arbitrary precoloring. A decomposition-transfer theorem yields NP-completeness already at tree-depth two. A separate path-decomposition reduction gives a maximum-degree threshold between one and two for completely uncolored disconnected host graphs with unrestrictedly many colors. Components with at most two edges are tractable, while a disjoint union of $P_4$'s is NP-complete. Finally, precoloring restores tractability in several cases: star forests are polynomial when every center is precolored, and two broad precoloring regimes on length-two spiders are polynomial even when the number of colors is unbounded.

0.21

Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor (and More)

cs.CC cs.DMcs.DSmath.CO ·2026-09-10 ·Édouard Bonnet, Yeonsu Chang
similarity 0.66
Abstract · 34 pages, 11 figures

We show that Max Independent Set (MIS) remains NP-hard in graphs excluding the $5 \times 5$ grid as an induced minor. This negatively answers a question of Dallard--Milanič--Štorgel that has attracted sustained attention, and refutes a conjecture by Gartland and Lokshtanov. Unless $N$-variable 3-SAT can be solved in time $2^{\mathcal O(N^{1-\varepsilon})}$ for some $\varepsilon > 0$, MIS requires $2^{Ω(n^{1/2-o(1)})}$ time on $n$-vertex graphs in this class. This complements a $2^{\widetilde{O}(n^{2/3})}$-time algorithm on any $H$-induced-minor-free class by Korhonen and Lokshtanov. Exploiting a connection between low twin-width or reduced parameters on one hand and planar-induced-minor-freeness on the other, we further show that 3-Coloring, Feedback Vertex Set and Dominating Set are NP-complete on weakly sparse graphs of reduced component max-leaf (hence twin-width) at most 3, even when a witnessing contraction sequence is given. Classes of bounded reduced component max-leaf (by any constant) and of twin-width at most 3 are known to exclude a fixed planar graph as an induced minor. The 3-Coloring and Feedback Vertex Set results refute more cases of the Gartland--Lokshtanov conjecture, even when the inputs are weakly sparse. The complexity of MIS in weakly sparse graphs excluding a planar induced minor remains open.

0.48

Vertex-Coloring Edge-Weighting: Kernelization and Generalization

cs.DS cs.CCcs.DM ·2026-09-23 ·Shubhada Aute, Fahad Panolan, Geevarghese Philip
similarity 0.65
Abstract · 46 page, 2 figures

An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it. Such an edge weighting is proper if adjacent vertices always receive distinct colors. Deciding whether a graph admits a proper weighting is known to be NP-complete for the weight set $\{0,1\}$, and also for $\{1,2\}$. In recent work (arXiv:2604.12363) we showed that both problems are FPT parameterized by the vertex cover number $k$, but it was open -- to the best of our knowledge -- whether either parameterized problem had a polynomial kernel. In this work, we show that both problems have polynomial kernels when parameterized by $k$. We also show that both problems are W[1]-hard parameterized by treedepth, answering another question from our earlier work. We then study the pre-weighted versions of the two problems, in which the weights of some edges are fixed in advance, and the task is to extend the assignment to a proper weighting of the whole graph. We show that both pre-weighted problems are FPT parameterized by the vertex cover number $k$. For the $\{1,2\}$ version the running time is $2^{O(k \log k)} \cdot n$; for the $\{0,1\}$ version we obtain the same running time when every pre-weight is $1$, and a slower FPT algorithm in the general case. We also show that both pre-weighted problems are W[1]-hard parameterized by either of (i) the feedback vertex set number or (ii) the treedepth of the input graph. Since a graph with no pre-assigned weights is a special case, our algorithms for the pre-weighted versions solve the two original problems as well, in time $2^{O(k \log k)} \cdot n$, significantly improving on the bound of $2^{O(k^4)} \cdot n^{O(1)}$ from our earlier work.

0.29

Recognizing Label-Connected Graphs

cs.DS cs.DM ·2026-11-03 ·Ralf Klasing, George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis
similarity 0.65
Abstract

In classical gossiping, each participant initially knows a distinct piece of information. Whenever two participants call each other, they exchange everything they know. We study Gossiping: given an undirected multigraph whose vertices represent participants and whose edges represent available calls, decide whether the calls can be ordered so that every participant learns all information, using each edge at most once. Equivalently, can one time label per edge make the graph temporally connected by strict temporal paths? This recognition problem is NP-complete; we study its parameterized complexity. After linear-time preprocessing, we give an exact $O(3^{n/3}n^3)$-time algorithm and a deterministic $2^{O(tw)}n$-time algorithm, where $n$ is the number of vertices and $tw$ is the treewidth of the underlying simple graph. We introduce a Tree Contraction Rule that extends the treewidth algorithm to single-exponential algorithms for parameters that may remain small on dense graphs, such as tree-independence number and clique-width, without requiring a decomposition as input. For the excess $δ=m-(2n-4)$ over the minimum number of calls, where $m$ is the number of edges, we give a randomized $2^{O(δ)}n^3$-time algorithm with one-sided error. Its main subroutine solves Rooted Independent Cycle: finding a cycle through four prescribed vertices whose edges are independent in a represented linear matroid. We solve this problem deterministically in $2^{O(r)}m$ arithmetic operations over the finite field representing the matroid, where $r$ is its rank. Gossiping is polynomial-time solvable at maximum degree four, counting parallel edges, but NP-complete on planar simple graphs of maximum degree five. The treewidth algorithm yields a $2^{O(\sqrt n)}$-time algorithm on planar graphs.

0.29