Papers for
network optimization teams
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.
Structure aware solver improves finding hamiltonian cycles in graphs
StructHCP: Structure-Aware SAT--CEGAR for the Hamiltonian Cycle Problem
Abstract: Many exact Hamiltonian-cycle solvers use the same edge-level representation for every input, even when graph structure admits a smaller set of global decisions. We present StructHCP, a SAT--CEGAR pipeline that selects a representation through inexpensive structural recognizers. Specialized searches handle high-degree clusters and paired chains, while complete directed and undirected encodings handle cubic and general graphs. Every returned cycle is reconstructed when necessary and verified in the input graph. On the 1,001-instance FHCP Challenge Set, StructHCP solves 826 instances, compared with 741 when the same general SAT--CEGAR engine is applied directly to every unreduced input graph. Relative to this ablation, StructHCP reduces PAR-2 by 32.9 percent. Formulation selection solves 82 more instances than the contracted general encoding; high-degree-cluster and cubic graphs account for 81 of this difference. StructHCP also solves 34 of the 51 instances solved by neither HCup nor Cut-set CEGAR, raising the combined coverage of the three solvers from 950 to 984. Twelve of its solutions lie outside the union of published per-instance SAT results analyzed here, and six also lie outside the published exact result sets in our comparison. These results show that selecting the representation can complement connectivity refinement on structured HCP instances.
Maxmmp problem is hard but admits approximation methods
Maximum Matching-Match: Hardness and Approximation
Abstract: In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024). Given a graph, a partial vertex coloring, and a multiset of colored sticks, the goal is to complete the coloring and assign the sticks to graph edges so as to maximize the number of satisfied edges. We first prove that \textsc{MaxMMP} is APX-hard by an reduction from \textsc{Max-Cut}. The hardness already holds with two colors, no precolored vertices, and only bichromatic sticks. We then give a simple deterministic $\frac{2}{c(c+1)}$-approximation for completely uncolored instances, improving to $\frac{2}{c(c-1)}$ when all sticks are bichromatic. Next, we obtain a randomized $\frac{1-\frac{1}{e}}{2c}$-approximation for arbitrary instances with $c$ colors by reducing the remaining coloring choices to monotone submodular maximization under a partition matroid. On bipartite graphs, the approximation ratio improves to $\frac{1-\frac{1}{e}}{c}$. For every fixed $c$, we further obtain deterministic $\frac{1}{2c}$ and $\frac{1}{c}$-approximations on general and bipartite graphs, respectively, in time $n^{O(c^2)}$. Finally, for every fixed number of colors, we show that \textsc{MaxMMP} can be solved exactly in time $n^{O(c^2)}$ on trees and on cographs.