Papers for

circuit layout engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Conflict-free graph cuts complexity classified by edge conflicts and degree

Conflict-Free Cuts: Exploring the Boundaries of Tractability

Abstract: A conflict-free cut of a host graph $G$ is an edge cut containing no conflicting pair of edges. The conflicts are specified by a conflict graph $\widehat G$ whose vertex set is $E(G)$. The conflict-free cut problem asks if the given instance $(G, \widehat G)$ has a conflict-free cut. When restricted to planar $G$ and 1-regular $\widehat G$, the problem is polynomial time solvable when $G$ has maximum degree 4, but NP-complete already at maximum degree 5. We study the complexity of conflict-free cut problem under restrictions on the degrees of $G$, the components of $\widehat G$, and the locality of the conflicts. A conflict is local if its two edges share an endpoint in $G$. We prove the following results. * For $Δ(\widehat G)\le1$, a directed-cycle formulation gives a polynomial-time algorithm when $|E(G)|\le2|V(G)|$, hence for maximum degree four. The problem is NP-complete on $5$-regular hosts with exactly $1$-regular conflicts. * For $Δ(\widehat G)\le1$, we give a constructive FPT algorithm in $s_4(G)=\sum_v\max\{0,d_G(v)-4\}$, single-exponential for planar hosts. For arbitrary conflicts, we give an XP algorithm in $η=\max\{0,|E(\widehat G)|-|V(G)|\}$. * On $4$-regular hosts, local exactly $2$-regular conflicts with components $C_3,C_4$ give NP-completeness. For local conflicts at maximum degree four, pair or triangle components separately permit polynomial algorithms, but mixing them gives NP-completeness. We classify cases where $\widehat G$ is a union of cliques. * An $a$-COC is a vertex set whose deletion leaves components of order at most $a$. For local conflicts, the problem is FPT in the minimum $2$-COC size, but NP-complete with a supplied $3$-COC of size six. Without locality, hardness holds with a supplied $2$-COC of size six. Both hardness results use exactly $1$-regular conflicts.

Wed 11 NovData Structures and Algorithms
The gist
This paper studies a problem where you try to cut edges in a graph without cutting any pairs of edges that conflict with each other. Conflicts are defined by another graph on the edges. The researchers show exactly when this problem is easy or hard to solve, depending on how many connections each node has and how conflicts are arranged. They also provide algorithms that work efficiently in certain cases and prove that the problem remains difficult in others.
Open → 2611.15846v1

Extending prescribed edge paths to cycles in hypercubes is NP-complete

On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes

Abstract: Let $Q_n$ be the $n$-dimensional hypercube, and let $P\subseteq E(Q_n)$ be a set of prescribed edges. It is known that, for $n\ge 2$, every such set $P$ with $|P|\leq 2n-3$ whose edges form a linear forest is contained in a Hamiltonian cycle of $Q_n$. This bound is sharp for general linear forests. The computational complexity of deciding whether a prescribed edge set of a hypercube can be extended to a Hamiltonian cycle was posed as an open question by Dvořák [SIAM J. Discrete Math. 19 (2005) 135--144]. We prove that the problem is NP-complete even when the prescribed edges form a spanning linear forest with no isolated vertices. We give a polynomial-time reduction from a restricted 3-SAT problem, using local spanning path-forest gadgets for variables and clauses that are uniformly embedded in the hypercube. The same reduction therefore establishes NP-hardness of two versions of Hamiltonian-cycle extension problems for general prescribed edge sets.

Sun 8 NovComputational Complexity
The gist
This paper studies a puzzle involving a high-dimensional cube, called a hypercube, where some connections between points are fixed. The question is whether those fixed connections can be part of a loop that visits every point exactly once. The authors show that deciding this is a very hard problem, even if the fixed connections form simple structures without isolated points. They prove this by turning a known hard logic problem into this puzzle, using clever gadgets inside the hypercube.
Open → 2611.11476v1

Graphic matroid parity solved faster than previous nm time barrier

Faster graphic matroid parity: Breaking the $nm$ time complexity barrier

Abstract: In the graphic matroid parity problem, we are given an undirected multigraph $G=(V,E)$ with $n$ vertices, together with a partition of $E$ into $m$ pairs of distinct edges, and the goal is to find a maximum-cardinality collection of pairs whose union is a forest. This problem generalizes both graph matching and graphic matroid intersection. Graph matching admits the celebrated $\tilde{O}(\sqrt{n}m)$-time algorithm of Micali--Vazirani~[FOCS'80], and graphic matroid intersection admits $o(nm)$-time algorithms due to Gabow--Stallmann~[ICALP'85] and Gabow--Xu~[FOCS'89]. In contrast, for graphic matroid parity, Gabow--Stallmann~[FOCS'84 \& Combinatorica'86] gave an $O(n^2 m)$-time algorithm, and its $\tilde{O}(nm)$-time implementation by Gabow--Stallmann~[ICALP'85] had long remained the best known bound, except in very dense regimes where $m=ω(n^3)$, in which case the algebraic $\tilde{O}(n^4)$-time algorithm of Cheung--Lau--Leung~[SODA'11 \& TALG'14] is faster. We present a randomized $\tilde{O}(n^{3/2} \sqrt{m} + \sqrt{n} m)$-time algorithm for graphic matroid parity. This is the first algorithm to break the $O(nm)$-time complexity barrier for this problem outside the very dense regime. Moreover, it improves over the previous bounds except in very sparse regimes where $m=\tilde{O}(n)$ and in very dense regimes where $m = \tildeΩ(n^{3.5})$. In particular, when $m=Θ(n^2)$, our algorithm runs in $\tilde{O}(n^{2.5})$ time, which nearly matches the $\tilde{O}(n^{2.5})$-time bounds of Micali--Vazirani for graph matching and of Gabow--Xu for graphic matroid intersection in this regime.

Sun 1 NovData Structures and Algorithms
The gist
The graphic matroid parity problem involves choosing pairs of edges in a graph so that their union forms a forest, which is a structure without cycles. This problem is tricky and generalizes other well-known graph problems like matching. Previous best algorithms ran in time proportional to the product of the number of vertices and pairs of edges, which could be slow. The authors developed a new randomized algorithm that runs faster, especially when the graph is of average density, thus breaking that longstanding speed barrier.
Open → 2611.02287v1

Safe hypergraph shrinking methods keep best solutions intact

Safe Hypergraph Contraction via Capacity-Aware Repair Certificates

Abstract: Multilevel partitioners shrink circuit hypergraphs through vertex contractions, yet a contraction that satisfies block capacity can still eliminate every optimal balanced bipartition. We develop certified safe coarsening (CSC) to identify contractions that preserve an optimum without computing that optimum. CSC certifies a repair for any feasible partition that splits a candidate group: the repair must respect the fixed block capacities and must not increase the cut-net objective. Its bounds exclude hyperedges that capacity constraints force to be cut. A pair certificate checks individual merges, while a directed minimum-cut test certifies groups whose savings emerge only when vertices move together. We prove that certified disjoint batches and successive rounds with recertification retain at least one globally optimal feasible partition for hypergraphs with positive integer vertex and net weights. Experiments on exactly solvable instances confirm optimum preservation for every tested configuration; integration with KaHyPar lowers the sum of per-instance best cuts on circuit benchmarks, with additional runtime.

Thu 1 OctData Structures and Algorithms
The gist
Finding the best way to split complex circuits into parts is tricky, especially when trying to simplify the problem by grouping parts together. The authors developed a way to safely combine parts without accidentally losing the best possible split. Their method checks if the merging keeps the optimal solution feasible by verifying certain safety conditions. Tests show this approach works well on circuits and helps find better splits overall.
Open → 2610.01678v1

Planar digraph feedback vertex set solved faster with new algorithms

Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs

Abstract: We consider Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size $k$. We give a randomized algorithm with one-sided error running in time $(2+\sqrt5)^k n^{O(1)}= 4.24^k n^{O(1)}$, and a deterministic algorithm running in time $8.04^k n^{O(1)}$. Both algorithms use polynomial space. To the best of our knowledge, these are the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs. This contrasts with general digraphs, where the best known algorithms run in time $2^{O(k\log k)}(n+m)$, and whether a $2^{o(k\log k)}n^{O(1)}$-time algorithm exists remains a major open problem. Our main tool is an exact Euler-type counting identity for plane digraphs. It shows that every small solution must carry a large share of the vertices whose in- and out-arcs alternate in the embedding, while solutions avoiding such vertices can be computed by reducing to Directed Feedback Arc Set, which is known to be solvable in polynomial time on planar digraphs via the Lucchesi-Younger theorem.

Sat 26 SeptData Structures and Algorithms
The gist
Directed Feedback Vertex Set is a problem about removing certain points from a network of arrows to break all cycles. The authors found faster algorithms to solve this problem specifically for networks that can be drawn on a plane without crossings. Their new methods are more efficient than previous ones for this special case and use clever counting techniques and known mathematical results. These algorithms also keep the memory use manageable.
Open → 2609.32728v1

Fast algorithm finds disjoint paths in graphs on complex surfaces

Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting

Abstract: We study the \textsc{$k$-Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph $G$ with $n$ vertices and $k$ vertex pairs embedded on a surface of Euler genus $g$, we present a $2^{O(k^2+g^2)}n$-time algorithm that computes $k$ pairwise vertex-disjoint paths connecting the given vertex pairs if such paths exist. Our approach relies on the decomposition of $G$ into $O(k+g)$ planar subgraphs while bounding the complexity of the boundaries between these subgraphs. This approach enables the use of techniques for compressing linkages in planar graphs. Moreover, our techniques yield two kernels of size polynomial in $k$, $g$, and the treewidth of the graph, and of size $2^{O(k+g)}$. These results extend recent advances on \textsc{$k$-Disjoint Paths} on planar graphs [Cho et al. SODA 2023] and [Włodarczyk and Zehavi FOCS 2023] to surface-embedded graphs.

Thu 24 SeptData Structures and AlgorithmsComputational Geometry
The gist
Finding multiple routes that don’t cross each other on a map-like structure can be very tricky, especially when the map is drawn on complicated surfaces like a donut shape. The authors developed a new method that quickly solves this problem for maps drawn on surfaces with a certain complexity measure called Euler genus. They break the complex surface into simpler flat parts and use clever techniques to stitch paths together without overlaps. Their work extends previous solutions from flat surfaces to more complex ones.
Open → 2609.29324v1

Planar directed graphs simplified by removing few vertices to avoid cycles

A Polynomial Kernel for Planar Directed Feedback Vertex Set

Abstract: The Directed Feedback Vertex Set problem (DFVS) asks whether a digraph can be made acyclic by deleting at most $k$ vertices. Whether DFVS admits a polynomial kernel parameterized by $k$ is a major open problem in kernelization, even for planar digraphs. We resolve the planar case by giving a deterministic kernel with $O(k^{66}\log^2 k)$ vertices and arcs. Our algorithm proceeds in three stages. First, we apply structural reduction rules to the input digraph, bounding the number of directed faces and some special vertices. Second, we pass to the planar dual, where vertex deletion corresponds to adding groups of reverse arcs to make each weakly connected component strongly connected. The structural bounds in the first stage yield a small retained vertex set in the dual. We then compress the dual instance by identifying vertices with the same distance records from this retained vertex set. The main technical contribution is a directed-cut argument showing that this identification preserves feasibility. Finally, we transform the polynomial-size dual instance back into an instance of Planar Directed Feedback Vertex Set via a $3$-CNF encoding and a planar graph construction.

Sun 20 SeptData Structures and Algorithms
The gist
The problem tackled is figuring out if a directed network (digraph) can be made free of loops by removing a small number of nodes. The authors provide a way to shrink such planar networks into a much smaller version without changing the answer to this problem. They do this by clever steps including simplifying the graph, switching perspectives to its dual, and compressing repeated patterns while keeping the problem’s solution intact. This leads to a smaller, manageable instance that still accurately represents whether the original network can be made loop-free.
Open → 2609.23669v1

Sat solving techniques improve graph labeling with minimum label span

Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems

Abstract: The Antibandwidth and Cyclic Antibandwidth problems are NP-hard graph labeling problems that aim to maximize the minimum (cyclic) distance between labels assigned to adjacent vertices. Extensive research on these problems has resulted in a variety of mathematical formulations and computational approaches. However, their minimum span perspective, in which a prescribed minimum (cyclic) distance is fixed and the objective is to minimize the label span, has received comparatively little attention. In this paper, we consider this complementary perspective by introducing the Minimum Span Antibandwidth/Cyclic Antibandwidth Labeling (MSABL/MSCABL) problems and developing a unified Boolean Satisfiability (SAT)-based framework for solving them. The SAT-based framework formulates MSABL/MSCABL as a sequence of decision problems and exploits their monotonicity to accelerate the search process. We also consider two SAT solving strategies, parallel and incremental SAT solving: the former examines multiple candidate spans concurrently, while the latter reuses a single SAT instance while progressively restricting the label domain. The proposed approaches are evaluated on benchmark instances from the Harwell-Boeing Sparse Matrix Collection and compared with CPLEXCP, CPLEXMIP, and Gurobi. The results show that SAT-based approaches are highly competitive in solution quality, with the parallel approach performing best overall for MSCABL and the incremental approach for MSABL. With the no-hole constraint, they remain competitive with CPLEXCP and significantly outperform CPLEXMIP and Gurobi, particularly for MSCABL. These results demonstrate the effectiveness of SAT solving as an exact approach for MSABL and MSCABL.

Thu 17 SeptArtificial Intelligence
The gist
Assigning numbers to connected points in a network can be tricky, especially when trying to keep certain minimum gaps between connected points. The authors focus on a related problem where the gap is set first, and the goal is to use the smallest possible range of numbers. They developed a method using SAT solvers (tools that decide if a set of logical statements can be true) to find exact solutions more efficiently. Their approach works well compared to existing optimization software, especially when they apply certain constraints. This shows that SAT solving is a strong tool for these challenging graph labeling problems.
Open → 2609.20091v1