cs.DM

arXiv:2403.05943v2 Announce Type: replace Abstract: The classic theorem of Gallai and Milgram (1960) asserts that for every graph G, the vertex set of G can be partitioned into at most \alpha(G) vertex-disjoint paths, where \alpha(G) is the maximum size of an independent set in G. The proof of Gallai--Milgram's theorem is constructive and yields a polynomial-time algorithm that computes a covering of G by at most \alpha(G) vertex-disjoint paths. We prove the following algorithmic extension of Gallai--Milgram's theorem for undirected graphs: determining whether an undirected graph can be covered by fewer than \alpha(G) - k vertex-disjoint paths is fixed-parameter tractable (FPT) when parameterized by k. More precisely, we provide an algorithm that, for an n-vertex graph G and an integer parameter k \ge 1, runs in time 2^{k^{O(k^4)}} \cdot n^{O(1)}, and outputs a path cover P of G. Furthermore, it: - either correctly reports that P is a minimum-size path cover, - or outputs, together with P, an independent set of size |P| + k certifying that P contains at most \alpha(G) - k paths. A key subroutine in our algorithm is an FPT algorithm, parameterized by \alpha(G), for deciding whether G contains a Hamiltonian path. This result is of independent interest -- prior to our work, no polynomial-time algorithm for deciding Hamiltonicity was known even for graphs with independence number at most 3. Moreover, the techniques we develop apply to a wide array of problems in undirected graphs, including Hamiltonian Cycle, Path Cover, Largest Linkage, and Topological Minor Containment. We show that all these problems are FPT when parameterized by the independence number of the graph. Notably, the independence number parameterization, which describes graph's density, departs from the typical flow of research in parameterized complexity, which focuses on parameters describing graph's sparsity, like treewidth or vertex cover.

arXiv:2503.22368v1 Announce Type: new Abstract: We present an exact algorithm for computing the connected Maximum Common Subgraph (MCS) across multiple graphs, where edges or vertices may additionally be labeled to account for possible atom types or bond types, a classical labeling used in molecular graphs. Our approach leverages modular product graphs and a modified Bron-Kerbosch algorithm to enumerate maximal cliques, ensuring all intermediate solutions are retained. A pruning heuristic efficiently reduces the modular product size, improving computational feasibility. Additionally, we introduce a graph ordering strategy based on graph-kernel similarity measures to optimize the search process. Our method is particularly relevant for bioinformatics and cheminformatics, where identifying conserved structural motifs in molecular graphs is crucial. Empirical results on molecular datasets demonstrate that our approach is exact, scalable and fast.

arXiv:2503.22327v1 Announce Type: cross Abstract: The construction of a cost minimal network for flows obeying physical laws is an important problem for the design of electricity, water, hydrogen, and natural gas infrastructures. We formulate this problem as a mixed-integer non-linear program with potential-based flows. The non-convexity of the constraints stemming from the potential-based flow model together with the binary variables indicating the decision to build a connection make these programs challenging to solve. We develop a novel class of valid inequalities on the fractional relaxations of the binary variables. Further, we show that this class of inequalities can be separated in polynomial time for solutions to a fractional relaxation. This makes it possible to incorporate these inequalities into a branch-and-cut framework. The advantage of these inequalities is lastly demonstrated in a computational study on the design of real-world gas transport networks.

arXiv:2301.13735v2 Announce Type: replace Abstract: A class of graphs $\mathscr{C}$ is monadically stable if for any unary expansion $\widehat{\mathscr{C}}$ of $\mathscr{C}$, one cannot interpret, in first-order logic, arbitrarily long linear orders in graphs from $\widehat{\mathscr{C}}$. It is known that nowhere dense graph classes are monadically stable; these encompass most of the studied concepts of sparsity in graphs, including graph classes that exclude a fixed topological minor. On the other hand, monadic stability is a property expressed in purely model-theoretic terms and hence it is also suited for capturing structure in dense graphs. For several years, it has been suspected that one can create a structure theory for monadically stable graph classes that mirrors the theory of nowhere dense graph classes in the dense setting. In this work we provide a step in this direction by giving a characterization of monadic stability through the Flipper game: a game on a graph played by Flipper, who in each round can complement the edge relation between any pair of vertex subsets, and Connector, who in each round localizes the game to a ball of bounded radius. This is an analog of the Splitter game, which characterizes nowhere dense classes of graphs (Grohe, Kreutzer, and Siebertz, J.ACM'17). We give two different proofs of our main result. The first proof uses tools from model theory, and it exposes an additional property of monadically stable graph classes that is close in spirit to definability of types. Also, as a byproduct, we give an alternative proof of the recent result of Braunfeld and Laskowski (arXiv 2209.05120) that monadic stability for graph classes coincides with existential monadic stability. The second proof relies on the recently introduced notion of flip-wideness (Dreier, M\"ahlmann, Siebertz, and Toru\'nczyk, ICALP 2023) and provides an efficient algorithm to compute Flipper's moves in a winning strategy.

arXiv:2503.10504v1 Announce Type: cross Abstract: Ever since E. T. Parker constructed an orthogonal pair of $10\times10$ Latin squares in 1959, an orthogonal triple of $10\times10$ Latin squares has been one of the most sought-after combinatorial designs. Despite extensive work, the existence of such an orthogonal triple remains an open problem, though some negative results are known. In 1999, W. Myrvold derived some highly restrictive constraints in the special case in which one of the Latin squares in the triple contains a $4\times4$ Latin subsquare. In particular, Myrvold showed there were twenty-eight possible cases for an orthogonal pair in such a triple, twenty of which were removed from consideration. We implement a computational approach that quickly verifies all of Myrvold's nonexistence results and in the remaining eight cases finds explicit examples of orthogonal pairs -- thus explaining for the first time why Myrvold's approach left eight cases unsolved. As a consequence, the eight remaining cases cannot be removed by a strategy of focusing on the existence of an orthogonal pair; the third square in the triple must necessarily be considered as well. Our approach uses a Boolean satisfiability (SAT) solver to derive the nonexistence of twenty of the orthogonal pair types and find explicit examples of orthogonal pairs in the eight remaining cases. To reduce the existence problem into Boolean logic we use a duality between the concepts of transversal representation and orthogonal pair and we provide a formulation of this duality in terms of a composition operation on Latin squares. Using our SAT encoding, we find transversal representations (and equivalently orthogonal pairs) in the remaining eight cases in under a day of computing.

arXiv:2103.10684v2 Announce Type: replace-cross Abstract: We prove that for any $\varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(\frac32-\varepsilon)t$-colouring that is "frozen" with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.

arXiv:2503.10541v1 Announce Type: new Abstract: In a digraph $D$, an arc $e=(x,y) $ in $D$ is considered transitive if there is a path from $x$ to $y$ in $D- e$. A digraph is transitive-free if it does not contain any transitive arc. In the Transitive-free Vertex Deletion (TVD) problem, the goal is to find at most $k$ vertices $S$ such that $D-S$ has no transitive arcs. In our work, we study a more general version of the TVD problem, denoted by $\ell$-Relaxed Transitive-free Vertex Deletion ($\ell$-RTVD), where we look for at most $k$ vertices $S$ such that $D-S$ has no more than $\ell$ transitive arcs. We explore $\ell$-RTVD on various well-known graph classes of digraphs such as directed acyclic graphs (DAGs), planar DAGs, $\alpha$-bounded digraphs, tournaments, and their multiple generalizations such as in-tournaments, out-tournaments, local tournaments, acyclic local tournaments, and obtain the following results. Although the problem admits polynomial-time algorithms in tournaments, $\alpha$-bounded digraphs, and acyclic local tournaments for fixed values of $\ell$, it remains NP-hard even in planar DAGs with maximum degree 6. In the parameterized realm, for $\ell$-RTVD on in-tournaments and out-tournaments, we obtain polynomial kernels parameterized by $k+\ell$ for bounded independence number. But the problem remains fixed-parameter intractable on DAGs when parameterized by $k$.

arXiv:2503.10002v1 Announce Type: cross Abstract: Given $d>0$ and a positive integer $n$, let $G$ be a triangle-free graph on $n$ vertices with average degree $d$. With an elegant induction, Shearer (1983) tightened a seminal result of Ajtai, Koml\'os and Szemer\'edi (1980/1981) by proving that $G$ contains an independent set of size at least $(1+o(1))\frac{\log d}{d}n$ as $d\to\infty$. By a generalisation of Shearer's method, we prove that the number of independent sets in $G$ must be at least $\exp\left((1+o(1))\frac{(\log d)^2}{2d}n\right)$ as $d\to\infty$. This improves upon results of Cooper and Mubayi (2014) and Davies, Jenssen, Perkins, and Roberts (2018). Our method also provides good lower bounds on the independence polynomial of $G$, one of which implies Shearer's result itself. As certified by a classic probabilistic construction, our bound on the number of independent sets is sharp to several leading terms as $d\to\infty$.

arXiv:2503.10158v1 Announce Type: cross Abstract: Integral linear systems $Ax=b$ with matrices $A$, $b$ and solutions $x$ are also required to be in integers, can be solved using invariant factors of $A$ (by computing the Smith Canonical Form of $A$). This paper explores a new problem which arises in applications, that of obtaining conditions for solving the Modular Linear System $Ax=b\rem n$ given $A,b$ in $\zz_n$ for $x$ in $\zz_n$ along with the constraint that the value of the linear function $\phi(x)=$ is coprime to $n$ for some solution $x$. In this paper we develop decomposition of the system to coprime moduli $p^{r(p)}$ which are divisors of $n$ and show how such a decomposition simplifies the computation of Smith form. This extends the well known index calculus method of computing the discrete logarithm where the moduli over which the linear system is reduced were assumed to be prime (to solve the reduced systems over prime fields) to the case when the factors of the modulus are prime powers $p^{r(p)}$. It is shown how this problem can be addressed effciently using the invariant factors and Smith form of the augmented matrix $[A,-p^{r(p)}I]$ and conditions modulo $p$ satisfied by $w$, where $p^{r(p)}$ vary over all divisors of $n$ with $p$ prime.

arXiv:2503.10240v1 Announce Type: new Abstract: We introduce and study the spherical dimension, a natural topological relaxation of the VC dimension that unifies several results in learning theory where topology plays a key role in the proofs. The spherical dimension is defined by extending the set of realizable datasets (used to define the VC dimension) to the continuous space of realizable distributions. In this space, a shattered set of size d (in the VC sense) is completed into a continuous object, specifically a d-dimensional sphere of realizable distributions. The spherical dimension is then defined as the dimension of the largest sphere in this space. Thus, the spherical dimension is at least the VC dimension. The spherical dimension serves as a common foundation for leveraging the Borsuk-Ulam theorem and related topological tools. We demonstrate the utility of the spherical dimension in diverse applications, including disambiguations of partial concept classes, reductions from classification to stochastic convex optimization, stability and replicability, and sample compression schemes. Perhaps surprisingly, we show that the open question posed by Alon, Hanneke, Holzman, and Moran (FOCS 2021) of whether there exist non-trivial disambiguations for halfspaces with margin is equivalent to the basic open question of whether the VC and spherical dimensions are finite together.

arXiv:2503.09904v1 Announce Type: new Abstract: In studies on complex network systems using graph theory, eigen-analysis is typically performed on an undirected graph model of the network. However, when analyzing cascading failures in a power system, the interactions among failures suggest the need for a directed graph beyond the topology of the power system to model directions of failure propagation. To accurately quantify failure interactions for effective mitigation strategies, this paper proposes a stochastic interaction graph model and associated eigen-analysis. Different types of modes on failure propagations are defined and characterized by the eigenvalues of a stochastic interaction matrix, whose absolute values are unity, zero, or in between. Finding and interpreting these modes helps identify the probable patterns of failure propagation, either local or widespread, and the participating components based on eigenvectors. Then, by lowering the failure probabilities of critical components highly participating in a mode of widespread failures, cascading can be mitigated. The validity of the proposed stochastic interaction graph model, eigen-analysis and the resulting mitigation strategies is demonstrated using simulated cascading failure data on an NPCC 140-bus system.

arXiv:2503.10320v1 Announce Type: cross Abstract: Cellular Automata (CA) are commonly investigated as a particular type of dynamical systems, defined by shift-invariant local rules. In this paper, we consider instead CA as algebraic systems, focusing on the combinatorial designs induced by their short-term behavior. Specifically, we review the main results published in the literature concerning the construction of mutually orthogonal Latin squares via bipermutive CA, considering both the linear and nonlinear cases. We then survey some significant applications of these results to cryptography, and conclude with a discussion of open problems to be addressed in future research on CA-based combinatorial designs.

arXiv:2502.18382v2 Announce Type: replace Abstract: We extend the bounded degree graph model for property testing introduced by Goldreich and Ron (Algorithmica, 2002) to hypergraphs. In this framework, we analyse the query complexity of three fundamental hypergraph properties: colorability, $k$-partiteness, and independence number. We present a randomized algorithm for testing $k$-partiteness within families of $k$-uniform $n$-vertex hypergraphs of bounded treewidth whose query complexity does not depend on $n$. In addition, we prove optimal lower bounds of $\Omega(n)$ on the query complexity of testing algorithms for $k$-colorability, $k$-partiteness, and independence number in $k$-uniform $n$-vertex hypergraphs of bounded degree. For each of these properties, we consider the problem of explicitly constructing $k$-uniform hypergraphs of bounded degree that differ in $\Theta(n)$ hyperedges from any hypergraph satisfying the property, but where violations of the latter cannot be detected in any neighborhood of $o(n)$ vertices.

arXiv:2503.04591v2 Announce Type: replace Abstract: We settle the theoretical ground for the study of automata networks under block-parallel update schedules, which are somehow dual to the block-sequential ones, but allow for repetitions of automaton updates. This gain in expressivity brings new challenges, and we analyse natural equivalence classes of update schedules: those leading to the same dynamics, and to the same limit dynamics, for any automata network. Countings and enumeration algorithms are provided, for their numerical study. We also prove computational complexity bounds for many classical problems, involving fixed points, limit cycles, the recognition of subdynamics, reachability, etc. The PSPACE-completeness of computing the image of a single configuration lifts the complexity of most problems, but the landscape keeps some relief, in particular for reversible computations.

arXiv:2503.00579v2 Announce Type: replace-cross Abstract: Convex solutions $A,B,I,J$ of four Abel equations are numerically studied. We do not know exact formulas for any of these functions, but conjecture that $A,B$ and $I,J$ are closely related. [Corrigendum at end.]

arXiv:2503.05562v1 Announce Type: cross Abstract: The dominating number $\gamma(G)$ of a graph $G$ is the minimum size of a vertex set whose closed neighborhood covers all the vertices of the graph. The packing number $\rho(G)$ of $G$ is the maximum size of a vertex set whose closed neighborhoods are pairwise disjoint. In this paper we study graph classes ${\cal G}$ such that $\gamma(G)/\rho(G)$ is bounded by a constant $c_{\cal G}$ for each $G\in {\cal G}$. We propose an inductive proof technique to prove that if $\cal G$ is the class of $2$-degenerate graphs, then there is such a constant bound $c_{\cal G}$. We note that this is the first monotone, dense graph class that is shown to have constant ratio. We also show that the classes of AT-free and unit-disk graphs have bounded ratio. In addition, our technique gives improved bounds on $c_{\cal G}$ for planar graphs, graphs of bounded treewidth or bounded twin-width. Finally, we provide some new examples of graph classes where the ratio is unbounded.

arXiv:2304.06348v4 Announce Type: replace Abstract: We propose a generic framework for establishing the decidability of a wide range of logical entailment problems (briefly called querying), based on the existence of countermodels that are structurally simple, gauged by certain types of width measures (with treewidth and cliquewidth as popular examples). As an important special case of our framework, we identify logics exhibiting width-finite finitely universal model sets, warranting decidable entailment for a wide range of homomorphism-closed queries, subsuming a diverse set of practically relevant query languages. As a particularly powerful width measure, we propose to employ Blumensath's partitionwidth, which subsumes various other commonly considered width measures and exhibits highly favorable computational and structural properties. Focusing on the formalism of existential rules as a popular showcase, we explain how finite partitionwidth sets of rules subsume other known abstract decidable classes but - leveraging existing notions of stratification - also cover a wide range of new rulesets. We expose natural limitations for fitting the class of finite unification sets into our picture and suggest several options for remedy.

arXiv:2503.05136v1 Announce Type: new Abstract: Fully Homomorphic Encryption (FHE) is a cryptographic scheme that enables computations to be performed directly on encrypted data, as if the data were in plaintext. BFV is one of the most popular FHE schemes. The BFV scheme is designed for homomorphic addition and multiplication of integers. BFV's encoding scheme does not require such approximation issues, because BFV is designed to encode only integers. Therefore, BFV guarantees exact encryption and decryption. BFV is suitable for use cases where the encrypted and decrypted values should exactly match (e.g., voting, financial computation), whereas CKKS is suitable for the use cases that tolerate tiny errors (e.g., data analytics, machine learning). In BFV, each plaintext is encrypted as an RLWE ciphertext. Therefore, BFV's ciphertext-to-ciphertext addition, ciphertext-to-plaintext addition, and ciphertext-to-plaintext multiplication are implemented based on GLWE's homomorphic addition and multiplication, with $k = 1$ to make GLWE an RLWE. This tutorial article is designed to help the reader understand how BFV works from the mathematical level.

arXiv:2503.05661v1 Announce Type: cross Abstract: Two graph parameters are said to be coarsely equivalent if they are within constant factors from each other for every graph $G$. Recently, several graph parameters were shown to be coarsely equivalent to tree-length. Recall that the length of a tree-decomposition ${\cal T}(G)$ of a graph $G$ is the largest diameter of a bag in ${\cal T}(G)$, and the tree-length $tl(G)$ of $G$ is the minimum of the length, over all tree-decompositions of $G$. Similarly, the length of a path-decomposition ${\cal P}(G)$ of a graph $G$ is the largest diameter of a bag in ${\cal P}(G)$, and the path-length $pl(G)$ of $G$ is the minimum of the length, over all path-decompositions of $G$. In this paper, we present several graph parameters that are coarsely equivalent to path-length. Among other results, we show that the path-length of a graph $G$ is small if and only if one of the following equivalent conditions is true: (a) $G$ can be embedded to an unweighted caterpillar tree (equivalently, to a graph of path-width one) with a small additive distortion; (b) there is a constant $r\ge 0$ such that for every triple of vertices $u,v,w$ of $G$, disk of radius $r$ centered at one of them intercepts all paths connecting two others; (c) $G$ has a $k$-dominating shortest path with small $k\ge 0$; (d) $G$ has a $k'$-dominating pair with small $k'\ge 0$; (e) some power $G^\mu$ of $G$ is an AT-free (or even a cocomparability) graph for a small integer $\mu\ge 0$.

arXiv:2503.05695v1 Announce Type: new Abstract: In this work, we revisit well-studied problems of fair allocation of indivisible items among agents with general, non-monotone valuations. We explore the existence and efficient computation of allocations that satisfy either fairness or equity constraints. The fairness notions we consider ensure that each agent values her bundle at least as much as others', allowing for (any or some) item removal, while the equity guarantees roughly equal valuations among agents, with similar adjustments. For objective valuations where items are classified as either goods or chores, we present a pseudo-polynomial local-search algorithm computing an ``equitable-up-to-any-good-or-any-chore'' (EQX*) allocation, a weaker version of an ``equitable-up-to-any-item" (EQX) allocation. Additionally, we provide a polynomial-time greedy algorithm that computes an ``equitable-up-to-one-item" (EQ1) allocation, and a similar algorithm returning an EQX* allocation when the valuations are also additive. As a key technical contribution of this work, by leveraging fixed-point theorems (such as Sperner's Lemma and its variants), we establish the existence of ``equitable-up-to-one-good-and-one-chore'' (EQ1*) and ``envy-free-up-to-one-good-and-one-chore'' (EF1*) allocations for non-negative (and possibly non-objective and non-monotone) valuations. This holds even when items are arranged in a path and bundles must form connected sub-paths. Additionally, we present a polynomial-time dynamic-programming algorithm that computes an EQ1* allocation. Finally, we extend the EF1* and EQ1* results to non-positive valuations using a novel multi-coloring variant of Sperner's lemma, a combinatorial result of independent interest. For monotone non-increasing valuations and path-connected bundles, this implies the existence of EF1 and EQ1 allocations, with EQ1 allocations being efficiently computable.