Discrete Mathematics
See recent articles
Showing new listings for Monday, 6 October 2025
- [1] arXiv:2510.03176 [pdf, html, other]
-
Title: Optimized Degree Realization: Minimum Dominating Set & Maximum MatchingSubjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
The Degree Realization problem requires, given a sequence $d$ of $n$ positive integers, to decide whether there exists a graph whose degrees correspond to $d$, and to construct such a graph if it exists. A more challenging variant of the problem arises when $d$ has many different realizations, and some of them may be more desirable than others. We study \emph{optimized realization} problems in which the goal is to compute a realization that optimizes some quality measure. Efficient algorithms are known for the problems of finding a realization with the maximum clique, the maximum independent set, or the minimum vertex cover. In this paper, we focus on two problems for which such algorithms were not known. The first is the Degree Realization with Minimum Dominating Set problem, where the goal is to find a realization whose minimum dominating set is minimized among all the realizations of the given sequence $d$. The second is the Degree Realization with Maximum Matching problem, where the goal is to find a realization with the largest matching among all the realizations of $d$. We present polynomial time realization algorithms for these two open problems.
A related problem of interest and importance is \emph{characterizing} the sequences with a given value of the optimized function. This leads to an efficient computation of the optimized value without providing the realization that achieves that value. For the Maximum Matching problem, a succinct characterization of degree sequences with a maximum matching of a given size was known. This paper provides a succinct characterization of sequences with minimum dominating set of a given size.
New submissions (showing 1 of 1 entries)
- [2] arXiv:2510.02420 (cross-list from stat.ML) [pdf, html, other]
-
Title: Higher-arity PAC learning, VC dimension and packing lemmaComments: 12 pages, 1 figureSubjects: Machine Learning (stat.ML); Discrete Mathematics (cs.DM); Machine Learning (cs.LG); Combinatorics (math.CO); Logic (math.LO); Statistics Theory (math.ST)
The aim of this note is to overview some of our work in Chernikov, Towsner'20 (arXiv:2010.00726) developing higher arity VC theory (VC$_n$ dimension), including a generalization of Haussler packing lemma, and an associated tame (slice-wise) hypergraph regularity lemma; and to demonstrate that it characterizes higher arity PAC learning (PAC$_n$ learning) in $n$-fold product spaces with respect to product measures introduced by Kobayashi, Kuriyama and Takeuchi'15. We also point out how some of the recent results in arXiv:2402.14294, arXiv:2505.15688, arXiv:2509.20404 follow from our work in arXiv:2010.00726.
- [3] arXiv:2510.02473 (cross-list from math.CO) [pdf, html, other]
-
Title: Two Proofs of the Hamiltonian Cycle IdentitySubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
The Hamiltonian cycle polynomial can be evaluated to count the number of Hamiltonian cycles in a graph. It can also be viewed as a list of all spanning cycles of length $n$. We adopt the latter perspective and present a pair of original proofs for the Hamiltonian cycle identity which relates the Hamiltonian cycle polynomial to the important determinant and permanent polynomials. The first proof is a more accessible combinatorial argument. The second proof relies on viewing polynomials as both linear algebraic and combinatorial objects whose monomials form lists of graphs. Finally, a similar identity is derived for the Hamiltonian path polynomial.
- [4] arXiv:2510.02727 (cross-list from cs.DS) [pdf, other]
-
Title: On the Enumeration of all Unique Paths of Recombining Trinomial TreesSubjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
Recombining trinomial trees are a workhorse for modeling discrete-event systems in option pricing, logistics, and feedback control. Because each node stores a state-dependent quantity, a depth-$D$ tree naively yields $\mathcal{O}(3^{D})$ trajectories, making exhaustive enumeration infeasible. Under time-homogeneous dynamics, however, the graph exhibits two exploitable symmetries: (i) translational invariance of nodes and (ii) a canonical bijection between admissible paths and ordered tuples encoding weak compositions. Leveraging these, we introduce a mass-shifting enumeration algorithm that slides integer "masses" through a cardinality tuple to generate exactly one representative per path-equivalence class while implicitly counting the associated weak compositions. This trims the search space by an exponential factor, enabling markedly deeper trees -- and therefore tighter numerical approximations of the underlying evolution -- to be processed in practice. We further derive an upper bound on the combinatorial counting expression that induces a theoretical lower bound on the algorithmic cost of approximately $\mathcal{O}\bigl(D^{1/2}1.612^{D}\bigr)$. This correspondence permits direct benchmarking while empirical tests, whose pseudo-code we provide, corroborate the bound, showing only a small constant overhead and substantial speedups over classical breadth-first traversal. Finally, we highlight structural links between our algorithmic/combinatorial framework and Motzkin paths with Narayana-type refinements, suggesting refined enumerative formulas and new potential analytic tools for path-dependent functionals.
- [5] arXiv:2510.02901 (cross-list from math.CO) [pdf, html, other]
-
Title: A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest pathsComments: 29 pages, 18 FiguresSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by $k$ shortest paths has pathwidth at most $O(3^k)$. In this paper, we improve this upper bound on the pathwidth to a polynomial one; namely, we show that every graph whose edge set can be covered by $k$ shortest paths has pathwidth $O(k^4)$, answering a question from the same paper. Moreover, we prove that when $k\leq 3$, every such graph has pathwidth at most $k$ (and this bound is tight). Finally, we show that even though there exist graphs with arbitrarily large treewidth whose vertex set can be covered by $2$ isometric trees, every graph whose set of edges can be covered by $2$ isometric trees has treewidth at most $2$.
- [6] arXiv:2510.02950 (cross-list from cs.DS) [pdf, html, other]
-
Title: Low Recourse Arborescence Forests Under Uniformly Random ArcsComments: 21 pages (22 including title page), 4 figuresSubjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
In this work, we study how to maintain a forest of arborescences of maximum arc cardinality under arc insertions while minimizing recourse -- the total number of arcs changed in the maintained solution. This problem is the "arborescence version'' of max cardinality matching.
On the impossibility side, we observe that even in this insertion-only model, it is possible for $m$ adversarial arc arrivals to necessarily incur $\Omega(m \cdot n)$ recourse, matching a trivial upper bound of $O(m \cdot n)$. On the possibility side, we give an algorithm with expected recourse $O(m \cdot \log^2 n)$ if all $m$ arcs arrive uniformly at random.
Cross submissions (showing 5 of 5 entries)
- [7] arXiv:2208.02186 (replaced) [pdf, html, other]
-
Title: On Brooks' TheoremGopalan Sajith (1), Sanjeev Saxena (2) ((1) IIT Guwahati, (2) IIT Kanpur)Comments: 6 pagesSubjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)
In this note we give two proofs of Brooks' Theorem. The first is obtained by modifying an earlier proof and the second by combining two earlier proofs. We believe these proofs are easier to teach in Computer Science courses.
- [8] arXiv:2411.01630 (replaced) [pdf, html, other]
-
Title: Optimal Inapproximability of Promise Equations over Finite GroupsComments: Full version of an ICALP(A)'25 paperSubjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
A celebrated result of Hastad established that, for any constant $\varepsilon>0$, it is NP-hard to find an assignment satisfying a $(1/|G|+\varepsilon)$-fraction of the constraints of a given 3-LIN instance over an Abelian group $G$ even if one is promised that an assignment satisfying a $(1-\varepsilon)$-fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for 3-LIN instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 3-LIN the random assignment achieves an optimal approximation guarantee. We prove that the random assignment algorithm is still best possible under a stronger promise that the 3-LIN instance is almost satisfiable over an arbitrarily more restrictive group.
- [9] arXiv:2502.16577 (replaced) [pdf, html, other]
-
Title: SUperman: Efficient Permanent Computation on GPUsComments: 38 pages, 8 figures, 5 tables, 4 algorithms, 31 referencesSubjects: Distributed, Parallel, and Cluster Computing (cs.DC); Discrete Mathematics (cs.DM); Numerical Analysis (math.NA)
The permanent is a function, defined for a square matrix, with applications in various domains including quantum computing, statistical physics, complexity theory, combinatorics, and graph theory. Its formula is similar to that of the determinant; however, unlike the determinant, its exact computation is #P-complete, i.e., there is no algorithm to compute the permanent in polynomial time unless P=NP. For an $n \times n$ matrix, the fastest algorithm has a time complexity of $O(2^{n-1}n)$. Although supercomputers have been employed for permanent computation before, there is no work and, more importantly, no publicly available software that leverages cutting-edge High-Performance Computing accelerators such as GPUs. In this work, we design, develop, and investigate the performance of SUperman, a complete software suite that can compute matrix permanents on multiple nodes/GPUs on a cluster while handling various matrix types, e.g., real/complex/binary and sparse/dense, etc., with a unique treatment for each type. SUperman run on a single Nvidia A100 GPU is up to $86\times$ faster than a state-of-the-art parallel algorithm on 44 Intel Xeon cores running at 2.10GHz. Leveraging 192 GPUs, SUperman computes the permanent of a $62 \times 62$ matrix in 1.63 days, marking the largest reported permanent computation to date.