Search

This paper presents a new graph isomorphism invariant, called $\mathfrak{w}$-labeling, that can be used to design a polynomial-time algorithm for solving the graph isomorphism problem for various graph classes. For example, all non-cospectral graph pairs are distinguished by the proposed combinatorial method, furthermore, even non-isomorphic cospectral graphs can be distinguished assuming certain properties of their eigenspaces. We also investigate a refinement of the aforementioned labeling, called $\mathfrak{s}^k$-labeling, which has both theoretical and practical applications. Among others, it can be used to generate graph fingerprints, which uniquely identify all graphs in the considered databases, including all strongly regular graphs on at most 64 nodes and all graphs on at most 12 nodes. It provably identifies all trees and 3-connected planar graphs up to isomorphism, which -- as a byproduct -- gives a new isomorphism algorithm for both graph classes. The practical importance of this fingerprint lies in significantly speeding up searching in graph databases, which is a commonly required task in biological and chemical applications.

This paper introduces the \emph{$d$-distance $b$-matching problem}, in which we are given a bipartite graph $G=(S,T;E)$ with $S=\{s_1,\dots,s_n\}$, a weight function on the edges, an integer $d\in\mathbb{Z}_+$ and a degree bound function $b:S\cup T\to\mathbb{Z}_+$. The goal is to find a maximum-weight subset $M\subseteq E$ of the edges satisfying the following two conditions: 1) the degree of each node $v\in S\cup T$ is at most $b(v)$ in $M$, 2) if $s_it,s_jt\in M$, then $|i-j|\geq d$. In the cyclic version of the problem, the nodes in $S$ are considered to be in cyclic order. We get back the \emph{(cyclic) $d$-distance matching problem} when $b(s) = 1$ for $s\in S$ and $b(t) = \infty$ for $t\in T$. We prove that the $d$-distance matching problem is APX-hard even in the unweighted case. We show that $(2-\frac{1}{d})$ is a tight upper bound on the integrality gap of the natural integer programming model for the cyclic $d$-distance $b$-matching problem provided that $(2d-1)$ divides the size of $S$. For the non-cyclic case, the integrality gap is shown to be at most $(2-\frac{2}{d})$. The proofs give approximation algorithms with guarantees matching these bounds, and also improve the best known algorithms for the (cyclic) $d$-distance matching problem. In a related problem, our goal is to find a permutation of $S$ maximizing the weight of the optimal $d$-distance $b$-matching. This problem can be solved in polynomial time for the (cyclic) $d$-distance matching problem -- even though the (cyclic) $d$-distance matching problem itself is NP-hard and also hard to approximate arbitrarily. For (cyclic) $d$-distance $b$-matchings, however, we prove that finding the best permutation is NP-hard even if $b\equiv 2$ or $d=2$, and we give $e$-approximation algorithms.

This paper introduces the Simultaneous assignment problem. Let us given a graph with a weight and a capacity function on its edges, and a set of its subgraphs along with a degree upper bound function for each of them. We are also given a laminar system on the node set with an upper bound on the degree-sum in each member of the system. Our goal is to assign each edge a non-negative integer below its capacity such that the total weight is maximized, the degrees in each subgraph are below the associated degree upper bound, and the degree-sum bound is respected in each member of the laminar system. We identify special cases when the problem is solvable in polynomial time. One of these cases is a common generalization of the hierarchical $b$-matching problem and the laminar matchoid problem. This implies that both problems can be solved efficiently in the weighted, capacitated case even if both lower and upper bounds are present -- generalizing the previous polynomial-time algorithms. The problem is solvable for trees provided that the laminar system is empty and a natural assumption holds for the subgraphs. The general problem, however, is shown to be APX-hard in the unweighted case, which implies that the $d$-distance matching problem is APX-hard. Furthermore, we prove that the approximation guarantee of any polynomial-time algorithm must increase linearly in the number of the given subgraphs unless P=NP. We give a generic framework for deriving approximation algorithms, which can be applied to a wide range of problems. As an application to our problem, a constant-approximation algorithm is derived when the number of the subgraphs is a constant. The approximation guarantee is the same as the integrality gap of a strengthened LP-relaxation when the number of the subgraphs is small. Improved approximation algorithms are given when the degree bounds are uniform or the graph is sparse.

In this paper, we prove that the multicolored Ramsey number $R(G_1,\dots,G_n,K_{n_1},\dots,K_{n_r})$ is at least $(\gamma-1)(\kappa-1)+1$ for arbitrary connected graphs $G_1,\dots,G_n$ and $n_1,\dots,n_r\in\mathbb{N}$, where $\gamma=R(G_1,\dots,G_n)$ and $\kappa=R(K_{n_1},\dots,K_{n_r})$. Erd\H os at al. conjectured that $R(C_n,K_l)=(n-1)(l-1)+1$ for every $n\geq l\geq 3$ except for $n=l=3$. Nikiforov proved this conjecture for $n\geq 4l+2$. Using the above bound, we derive the following generalization of this result. $R(C_n,K_{n_1},\dots,K_{n_r})=(n-1)(\kappa-1)+1$, where $\kappa=R(K_{n_1},\dots,K_{n_r})$ and $n\geq 4\kappa+2$.

This paper introduces the \emph{$d$-distance matching problem}, in which we are given a bipartite graph $G=(S,T;E)$ with $S=\{s_1,\dots,s_n\}$, a weight function on the edges and an integer $d\in\mathbb Z_+$. The goal is to find a maximum weight subset $M\subseteq E$ of the edges satisfying the following two conditions: i) the degree of every node of $S$ is at most one in $M$, ii) if $s_it,s_jt\in M$, then $|j-i|\geq d$. The question arises naturally, for example, in various scheduling problems. We show that the problem is NP-complete in general and admits a simple $3$-approxi\-mation. We give an FPT algorithm parameterized by $d$ and also settle the case when the size of $T$ is constant. From an approximability point of view, we show that the integrality gap of the natural integer programming model is at most $2-\frac{1}{2d-1}$, and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial $(2-\frac{1}{d})$-approximation algorithm is also presented. Several greedy approaches are considered, in particular, a local search algorithm that achieves an approximation ratio of $3/2+\epsilon$ for any constant $\epsilon>0$ in the unweighted case. The novel approaches used in the analysis of the integrality gap and the approximation ratio of locally optimal solutions might be of independent combinatorial interest.