CyberSec Research

We show that, for every fixed positive integers $r$ and $k$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} admits a polynomial-time algorithm on $kP_3$-free graphs. This problem is a common generalization of \textsc{Max-Weight Independent Set}, \textsc{Odd Cycle Transversal} and \textsc{List $r$-Coloring}, among others. Our result has several consequences. First, it implies that, for every fixed $r \geq 5$, assuming $\mathsf{P}\neq \mathsf{NP}$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} is polynomial-time solvable on $H$-free graphs if and only if $H$ is an induced subgraph of either $kP_3$ or $P_5+kP_1$, for some $k \geq 1$. Second, it makes considerable progress toward a complexity dichotomy for \textsc{Odd Cycle Transversal} on $H$-free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rz{\k{a}}{\.z}ewski, Saurabh, and Sharma [TALG 2024]. Third, it gives a short and self-contained proof of the known result of Chudnovsky, Hajebi, and Spirkl [Combinatorica 2024] that \textsc{List $r$-Coloring} on $kP_3$-free graphs is polynomial-time solvable for every fixed $r$ and $k$. We also consider two natural distance-$d$ generalizations of \textsc{Max-Weight Independent Set} and \textsc{List $r$-Coloring} and provide polynomial-time algorithms on $kP_3$-free graphs for every fixed integers $r$, $k$, and $d \geq 6$.

Given a finite and non-empty set $X$ and randomly selected specific functions and relations on $X$, we investigate the existence and non-existence of fixed points and reflexive points, respectively. First, we consider the class of functions, weaken it to the classes of partial functions, total relations and general relations and also strengthen it to the class of permutations. Then we investigate the class of involutions and the subclass of proper involutions. Finally, we treat idempotent functions, partial idempotent functions and related concepts. We count relations, calculate corresponding probabilities and also calculate the limiting values of the latter in case that the cardinality of $X$ tends to infinity. All these results have been motivated and also supported by numerous experiments performed with the RelView tool.

Bent functions are Boolean functions in an even number of variables that are indicators of Hadamard difference sets in elementary abelian 2-groups. A bent function in m variables is said to be normal if it is constant on an affine space of dimension m/2. In this paper, we demonstrate that all bent functions in m = 8 variables -- whose exact count, determined by Langevin and Leander (Des. Codes Cryptogr. 59(1--3): 193--205, 2011), is approximately $2^106$ share a common algebraic property: every 8-variable bent function is normal, up to the addition of a linear function. With this result, we complete the analysis of the normality of bent functions for the last unresolvedcase, m= 8. It is already known that all bent functions in m variables are normal for m <= 6, while for m > = 10, there exist bent functions that cannot be made normal by adding linear functions. Consequently, we provide a complete solution to an open problem by Charpin (J. Complex. 20(2-3): 245-265, 2004)

Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if $m$ items are divided among $n$ agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that $m = \Omega(n\log n/\log\log n)$, generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of $m = n/(1-\mu)$ for the transition from non-existence to existence, where $\mu\in (0,1)$ denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if $m = \omega(\sqrt{r})$, where $r$ denotes the ratio between the two weights.

In the Dominated Cluster Deletion problem we are given an undirected graph $G$ and integers $k$ and $d$ and the question is to decide whether there exists a set of at most $k$ vertices whose removal results in a graph in which each connected component has a dominating set of size at most $d$. In the Elimination Distance to Dominated Clusters problem we are again given an undirected graph $G$ and integers $k$ and $d$ and the question is to decide whether we can recursively delete vertices up to depth $k$ such that each remaining connected component has a dominating set of size at most $d$. Bentert et al.~[Bentert et al., MFCS 2024] recently provided an almost complete classification of the parameterized complexity of Dominated Cluster Deletion with respect to the parameters $k$, $d$, $c$, and $\Delta$, where $c$ and $\Delta$ are the degeneracy, and the maximum degree of the input graph, respectively. In particular, they provided a non-uniform algorithm with running time $f(k,d)\cdot n^{O(d)}$. They left as an open problem whether the problem is fixed-parameter tractable with respect to the parameter $k+d+c$. We provide a uniform algorithm running in time $f(k,d)\cdot n^{O(d)}$ for both Dominated Cluster Deletion and Elimination Distance to Dominated Clusters. We furthermore show that both problems are FPT when parameterized by $k+d+\ell$, where $\ell$ is the semi-ladder index of the input graph, a parameter that is upper bounded and may be much smaller than the degeneracy $c$, positively answering the open question of Bentert et al. We almost complete the picture by providing an almost full classification for the parameterized complexity and kernelization complexity of Elimination Distance to Dominated Clusters. The one difficult base case that remains open is whether treedepth (the case $d=0$) is NP-hard on graphs of bounded maximum degree.

Discrete Forman-Ricci curvature (FRC) is an efficient tool that characterizes essential geometrical features and associated transitions of real-world networks, extending seamlessly to higher-dimensional computations in simplicial complexes. In this article, we provide two major advancements: First, we give a decomposition for FRC, enabling local computations of FRC. Second, we construct a set-theoretical proof enabling an efficient algorithm for the local computation of FRC in Vietoris-Rips (VR) complexes.Strikingly, this approach reveals critical information and geometric insights often overlooked by conventional classification techniques. Our findings open new avenues for geometric computations in VR complexes and highlight an essential yet under-explored aspect of data classification: the geometry underpinning statistical patterns.

This paper investigates concurrency-constrained scheduling problems, where the objective is to construct a schedule for a set of jobs subject to concurrency restrictions. Formally, we are given a conflict graph $G$ defined over a set of $n$ jobs, where an edge between two jobs in $G$ indicates that these jobs cannot be executed concurrently. Each job may have distinct attributes, such as processing time, due date, weight, and release time. The goal is to determine a schedule that optimizes a specified scheduling criterion while adhering to all concurrency constraints. This framework offers a versatile model for analyzing resource allocation problems where processes compete for shared resources, such as access to shared memory. From a theoretical perspective, it encompasses several classical graph coloring problems, including Chromatic Number, Sum Coloring, and Interval Chromatic Number. Given that even the simplest concurrency-constrained scheduling problems are NP-hard for general conflict graphs, this study focuses on conflict graphs with bounded treewidth. Our results establish a dichotomy: Some problems in this setting can be solved in FPT time, while others are shown to be XALP-complete for treewidth as parameter. Along the way, we generalize several previously known results on coloring problems for bounded treewidth graphs. Several of the FPT algorithms are based on the insight that completion times are bounded by the Grundy number of the conflict graph - the fact that this number is bounded by the product of treewidth and the logarithm of the number of vertices then leads to the FPT time bound.

We show that for any positive integers $g$ and $t$, there is a $K_{6}^{(1)}$-induced-minor-free graph of girth at least $g$ that is not a region intersection graph over the class of $K_t$-minor-free graphs. This answers in a strong form the recently raised question of whether for every graph $H$ there is a graph $H'$ such that $H$-induced-minor-free graphs are region intersection graphs over $H'$-minor-free graphs.

Let $G = (V, E)$ be a connected graph, and let $T$ in $V$ be a subset of vertices. An orientation of $G$ is called $T$-odd if any vertex $v \in V$ has odd in-degree if and only if it is in $T$. Finding a T -odd orientation of G can be solved in polynomial time as shown by Chevalier, Jaeger, Payan and Xuong (1983). Since then, $T$-odd orientations have continued to attract interest, particularly in the context of global constraints on the orientation. For instance, Frank and Kir\'aly (2002) investigated $k$-connected $T$-odd orientations and raised questions about acyclic $T$-odd orientations. This problem is now recognized as an Egres problem and is known as the "Acyclic orientation with parity constraints" problem. Szegedy ( 005) proposed a randomized polynomial algorithm to address this problem. An easy consequence of his work provides a polynomial time algorithm for planar graphs whenever $|T | = |V | - 1$. Nevertheless, it remains unknown whether it exists in general. In this paper we contribute to the understanding of the complexity of this problem by studying a more general one. We prove that finding a $T$-odd acyclic orientation on graphs having some directed edges is NP-complete.

We study complexity and periodicity of Delone sets by applying an algebraic approach to multidimensional symbolic dynamics. In this algebraic approach, $\mathbb{Z}^d$-configurations $c: \mathbb{Z}^d \to \mathcal{A}$ for a finite set $\mathcal{A} \subseteq \mathbb{C}$ and finite $\mathbb{Z}^d$-patterns are regarded as formal power series and Laurent polynomials, respectively. In this paper we study also functions $c: \mathbb{R}^d \to \mathcal{A}$ where $\mathcal{A}$ is as above. These functions are called $\mathbb{R}^d$-configurations. Any Delone set may be regarded as an $\mathbb{R}^d$-configuration by simply presenting it as its indicator function. Conversely, any $\mathbb{R}^d$-configuration whose support (that is, the set of cells for which the configuration gets non-zero values) is a Delone set can be seen as a colored Delone set. We generalize the concept of annihilators and periodizers of $\mathbb{Z}^d$-configurations for $\mathbb{R}^d$-configurations. We show that if an $\mathbb{R}^d$-configuration has a non-trivial annihilator, that is, if a linear combination of some finitely many of its translations is the zero function, then it has an annihilator of a particular form. Moreover, we show that $\mathbb{R}^d$-configurations with integer coefficients that have non-trivial annihilators are sums of finitely many periodic functions $c_1,\ldots,c_m: \mathbb{R}^d \to \mathbb{Z}$. Also, $\mathbb{R}^d$-pattern complexity is studied alongside with the classical patch-complexity of Delone sets. We point out the fact that sufficiently low $\mathbb{R}^d$-pattern complexity of an $\mathbb{R}^d$-configuration implies the existence of non-trivial annihilators. Moreover, it is shown that if a Meyer set has sufficiently slow patch-complexity growth, then it has a non-trivial annihilator. Finally, a condition for forced periodicity of colored Delone sets of finite local complexity is provided.

A hole is a chordless cycle with at least four vertices. A hole is odd if it has an odd number of vertices. A dart is a graph which vertices $a, b, c, d, e$ and edges $ab, bc, bd, be, cd, de$. Dart-free graphs have been actively studied in the literature. We prove that a (dart, odd hole)-free graph is perfect, or does not contain a stable set on three vertices, or is the join or co-join of two smaller graphs. Using this structure result, we design a polynomial-time algorithm for finding an optimal colouring of (dart, odd hole)-free graphs. A graph $G$ is perfectly divisible if every induced subgraph $H$ of $G$ contains a set $X$ of vertices such that $X$ meets all largest cliques of $H$, and $X$ induces a perfect graph. The chromatic number of a perfectly divisible graph $G$ is bounded by $\omega^2$ where $\omega$ denotes the number of vertices in a largest clique of $G$. We prove that (dart, odd hole)-free graphs are perfectly divisible.

Condorcet's paradox is a fundamental result in social choice theory which states that there exist elections in which, no matter which candidate wins, a majority of voters prefer a different candidate. In fact, even if we can select any $k$ winners, there still may exist another candidate that would beat each of the winners in a majority vote. That is, elections may require arbitrarily large dominating sets. We show that approximately dominating sets of constant size always exist. In particular, for every $\varepsilon > 0$, every election (irrespective of the number of voters or candidates) can select $O(\frac{1}{\varepsilon ^2})$ winners such that no other candidate beats each of the winners by a margin of more than $\varepsilon$ fraction of voters. Our proof uses a simple probabilistic construction using samples from a maximal lottery, a well-studied distribution over candidates derived from the Nash equilibrium of a two-player game. In stark contrast to general approximate equilibria, which may require support logarithmic in the number of pure strategies, we show that maximal lotteries can be approximated with constant support size. These approximate maximal lotteries may be of independent interest.

Our work began as an effort to understand calculations by Morris & Szekeres (1961) and Walker (1991) regarding fractional iteration.

Given a graph $G$ and a natural number $k$, the $k$-recolouring graph $\mathcal{C}_k(G)$ is the graph whose vertices are the $k$-colourings of $G$ and whose edges link pairs of colourings which differ at exactly one vertex of $G$. Recently, Hogan et al. proved that $G$ can be determined from $\mathcal{C}_k(G)$ provided $k$ is large enough (quadratic in the number of vertices of $G$). We improve this bound by showing that $k=\chi(G)+1$ colours suffice, and provide examples of families of graphs for which $k=\chi(G)$ colours do not suffice. We then extend this result to $k$-Kempe-recolouring graphs, whose vertices are again the $k$-colourings of a graph $G$ and whose edges link pairs of colourings which differ by swapping the two colours in a connected component induced by selecting those two colours. We show that $k=\chi(G)+2$ colours suffice to determine $G$ in this case. Finally, we investigate the case of independent set reconfiguration, proving that in only a few trivial cases is one guaranteed to be able to determine a graph $G$.

The frequency $K_i$s ($i\in[4,n]$) are studied for symmetrical traveling salesman problem ($TSP$) to identify the edges in optimal Hamiltonian cycle ($OHC$). A frequency $K_i$ is computed with a sort of ${{i}\choose{2}}$ optimal $i$-vertex paths with given endpoints (optimal $i$-vertex path) in a corresponding $K_i$ in $K_n$. In frequency $K_i$, the frequency of an edge is the number of the optimal $i$-vertex paths containing the edge in the corresponding $K_i$. Given an $OHC$ edge related to $K_i$, it has a frequency bigger than $\frac{1}{2}{{i}\choose{2}}$ in the corresponding frequency $K_i$, and that of an ordinary edge not in $OHC$ is smaller than $\frac{i+2}{2}$. On average, an $OHC$ edge in $K_i$ has a frequency bigger than $\frac{i^2-4i+7}{2}$ whereas an ordinary edge has a frequency smaller than 2. Moreover, given a frequency $K_i$ containing an $OHC$ edge related to $K_n$, the frequency of the $OHC$ edge is bigger than $\frac{1}{2}{{i}\choose{2}}$ in the worst average case. It implies that the average frequency of an $OHC$ edge computed with frequency $K_i$s is bigger than $\frac{1}{2}{{i}\choose{2}}$. It also found that the probability that an $OHC$ edge is contained in optimal $i$-vertex paths keeps stable or increases according to $i\in [4, n]$. As the frequency $K_i$s are used to compute the frequency of an edge, each $OHC$ edge has its own peak frequency at $i=P_0$ where $P_0=\frac{n}{2} + 2$ for even $n$ or $\frac{n+1}{2} + 1$ for odd $n$. For ordinary edges out of $OHC$, the probability that they are contained in optimal $i$-vertex paths decreases according to $i$. Moreover, the average frequency of an ordinary edge will be smaller than $\frac{1}{2}{{i}\choose{2}}$ if $i \geq [0.3660n + 1.5849]$. Based on these findings, an algorithm is presented to find $OHC$ in $O(n^62^{0.3660n})$ time using dynamic programming.

A king in a directed graph is a vertex $v$ such that every other vertex is reachable from $v$ via a path of length at most $2$. It is well known that every tournament (a complete graph where each edge has a direction) has at least one king. Our contributions in this work are: - We show that the query complexity of determining existence of a king in arbitrary $n$-vertex digraphs is $\Theta(n^2)$. This is in stark contrast to the case where the input is a tournament, where Shen, Sheng, and Wu [SICOMP'03] showed that a king can be found in $O(n^{3/2})$ queries. - In an attempt to increase the "fairness" in the definition of tournament winners, Ho and Chang [IPL'03] defined a strong king to be a king $k$ such that, for every $v$ that dominates $k$, the number of length-$2$ paths from $k$ to $v$ is strictly larger than the number of length-$2$ paths from $v$ to $k$. We show that the query complexity of finding a strong king in a tournament is $\Theta(n^2)$. This answers a question of Biswas, Jayapaul, Raman, and Satti [DAM'22] in the negative. A key component in our proofs is the design of specific tournaments where every vertex is a king, and analyzing certain properties of these tournaments. We feel these constructions and properties are independently interesting and may lead to more interesting results about tournament solutions.

Research of cycles through specific vertices is a central topic in graph theory. In this context, we focus on a well-studied computational problem, \textsc{$T$-Cycle}: given an undirected $n$-vertex graph $G$ and a set of $k$ vertices $T\subseteq V(G)$ termed \textit{terminals}, the objective is to determine whether $G$ contains a simple cycle $C$ through all the terminals. Our contribution is twofold: (i) We provide a $2^{O(\sqrt{k}\log k)}\cdot n$-time fixed-parameter deterministic algorithm for \textsc{$T$-Cycle} on planar graphs; (ii) We provide a $k^{O(1)}\cdot n$-time deterministic kernelization algorithm for \textsc{$T$-Cycle} on planar graphs where the produced instance is of size $k\log^{O(1)}k$. Both of our algorithms are optimal in terms of both $k$ and $n$ up to (poly)logarithmic factors in $k$ under the ETH. In fact, our algorithms are the first subexponential-time fixed-parameter algorithm for \textsc{$T$-Cycle} on planar graphs, as well as the first polynomial kernel for \textsc{$T$-Cycle} on planar graphs. This substantially improves upon/expands the known literature on the parameterized complexity of the problem.

Contraction of triangles is a standard operation in the study of cubic graphs, as it reduces the order of the graph while typically preserving many of its properties. In this paper, we investigate the converse problem, wherein certain vertices of cubic graphs are expanded into triangles to achieve a desired property. We first focus on bridgeless cubic graphs and define the parameter $T(G)$ as the minimum number of vertices that need to be expanded into triangles so that the resulting cubic graph can be covered with four perfect matchings. We relate this parameter to the concept of shortest cycle cover. Furthermore, we show that if $5$-Cycle Double Cover Conejcture holds true, then $T(G)\leq \frac{2}{5} |V(G)|$. We conjecture a tighter bound, $T(G)\leq \frac{1}{10}|V(G)|$, which is optimal for the Petersen graph, and show that this bound follows from major conjectures like the Petersen Coloring Conjecture. In the second part of the paper, we introduce the parameter $t(G)$ as the minimum number of vertex expansions needed for the graph to admit a perfect matching. We prove a Gallai type identity: $t(G)+\ell(G)=|V(G)|$, where $\ell(G)$ is the number of edges in a largest even subgraph of $G$. Then we prove the general upper bound $t(G)< \frac{1}{4}|V(G)|$ for cubic graphs, and $t(G)< \frac{1}{6}|V(G)|$ for cubic graphs without parallel edges. We provide examples showing that these bounds are asymptotically tight. The paper concludes with a discussion of the computational complexity of determining these parameters.