Papers for

optimization software 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.

Graphs without induced stars have bounded path independence number

Induced Forest Minor Theorem for Graphs Without an Induced Star

Abstract: Motivated by recent work on tree independence number, we study the path independence number of a graph $G$: the minimum integer $k$ such that there is a path decomposition of $G$ where each bag induces a graph with independence number at most $k$. We show that every graph excluding both an induced forest minor and an induced star has bounded path independence number. This characterises when a graph class that excludes an induced star has bounded path independence number while also partially resolving a conjecture of Dallard, Krnc, Kwon, Milani{č}, Munaro, Štorgel and Wiederrecht (2024). Furthermore, we show that graphs excluding both an apex-forest induced minor and an induced star have bounded tree independence number. As a consequence, for every fixed apex-forest $H$ and integer $t$, there is a polynomial-time algorithm to test whether a $K_{1,t}$-induced-subgraph-free graph contains $H$ as an induced minor. Moreover, it follows that the Maximum Weight Independent Set problem, as well as several other NP-hard problems, can be solved in polynomial-time on $K_{1,t}$-induced-subgraph-free graphs that exclude $H$ as an induced minor.

Wed 9 SeptDiscrete Mathematics
The gist
This paper looks at a special way to break down graphs into smaller parts where each part has limited independent points. The authors show that if a graph does not contain certain star-shaped subgraphs or complex tree structures, then this kind of breakdown is always bounded. This helps understand when such decompositions exist and partially confirms a previous guess made by other researchers. The work also leads to new ways to test for specific graph patterns and solve tough problems efficiently on these restricted graphs.
Open → 2609.10406v1

When can optimality certificates be obtained for broad learning problems

When Can One Obtain Certificates of Optimality Using Positivstellensaetze?

Abstract: We study certificates of positivity and optimality for learning problems whose objectives and constraints need not be polynomial. We isolate an axiomatic core of Fischer's constructive strict and weak Positivstellensätze and prove the resulting theorems for abstract function algebras over ordered fields. The framework separates two roles that can otherwise be conflated: objective and constraint functions may be built from broad classes of continuous or definable operations, while the auxiliary primitives used to construct a certificate satisfy explicit scalar and closure axioms. We give instances over continuous and definable function algebras, including ordered fields not closed under square roots, derive lower-bound and global-optimality certificates, and analyze both expanded term length and shared computation-graph complexity.

Tue 8 SeptArtificial Intelligence
The gist
Many learning tasks need ways to prove that a solution is truly the best, but these tasks often involve complicated functions not just simple polynomials. The authors study a general mathematical framework that isolates key properties needed to construct such proofs, called certificates of optimality, even when the functions are complex and the underlying number systems lack some usual operations. They show how these certificates can still be built under very general conditions and analyze what influences their complexity. This helps understand when and how guarantees about best solutions can be reliably generated beyond standard polynomial cases.
Open → 2609.08736v1