Exploiting symmetry is a well-established technique to eliminate redundant work in combinatorial solvers, yet it often incurs computational overhead that limits its practical impact. In particular, practical instances arising from applications are frequently large and give rise to graphs whose size becomes a major bottleneck for algorithms dealing with symmetry. We propose a method for symmetry-preserving graph compression that reduces graph size while preserving the symmetries of the original graph in a controlled way. Our approach identifies and merges equivalent vertex colors under conditions that guarantee the recoverability of all symmetries. We provide both a theoretical foundation and efficient practical criteria for such merges, show that computing optimal and approximately optimal compression is intractable, and introduce a linear-time, practical heuristic. Extensive experiments on a vast library of graphs demonstrate that our new technique achieves significant compression ratios. Implemented in the state-of-the-art symmetry detection tool dejavu, we achieve an overall speedup of 1.39, with large modern SAT and MIP benchmarks benefiting the most.

We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g ≥ 1 and recovers the known tight bound for the planar case ( g = 0 ).

The Weisfeiler-Leman dimension of a graph \( G \) is the least number \( k \) such that the \( k \) -dimensional Weisfeiler-Leman algorithm distinguishes \( G \) from every other non-isomorphic graph, or equivalently, the least \( k \) such that \( G \) is definable in \((k+1)\) -variable logic with counting. The dimension is a standard measure of the descriptive or structural complexity of a graph and recently finds various applications in particular in the context of machine learning. This article studies the complexity of computing the Weisfeiler-Leman dimension. We observe that deciding whether the Weisfeiler-Leman dimension of \( G \) is at most \( k \) is NP -hard, even if \( G \) is restricted to have 4-bounded color classes. Therefore, we study parameterized versions of the problem. For each fixed \(k\geq 2\) , we give a polynomial-time algorithm that decides whether the Weisfeiler-Leman dimension of a given graph with 5-bounded color classes is at most \( k \) . Moreover, we show that for these bounds on the color classes, this is optimal because the problem is P -hard under logspace-uniform AC 0 -reductions. Furthermore, for each larger bound \( c \) on the color classes and each fixed \(k\geq 2\) , we provide a polynomial-time decision algorithm for the abelian case, that is, for structures of which each color class has an abelian automorphism group. While the graph classes we consider may seem quite restrictive, graphs with 4-bounded abelian colors include CFI-graphs and multipedes, which form the basis of almost all known hard instances and lower bounds related to the Weisfeiler-Leman algorithm.

The Weisfeiler-Leman dimension of a graph $G$ is the least number $k$ such that the $k$-dimensional Weisfeiler-Leman algorithm distinguishes $G$ from every other non-isomorphic graph. The dimension is a standard measure of the descriptive complexity of a graph and recently finds various applications in particular in the context of machine learning. In this paper, we study the computational complexity of computing the Weisfeiler-Leman dimension. We observe that in general the problem of deciding whether the Weisfeiler-Leman dimension of $G$ is at most $k$ is NP-hard. This is also true for the more restricted problem with graphs of color multiplicity at most 4. Therefore, we study parameterized versions of the problem. We give, for each fixed $k\geq 2$, a polynomial-time algorithm that decides whether the Weisfeiler-Leman dimension of a given graph of color multiplicity at most $5$ is at most $k$. Moreover, we show that for these color multiplicities this is optimal in the sense that this problem is P-hard under logspace-uniform $\text{AC}_0$-reductions. Furthermore, for each larger bound $c$ on the color classes and each fixed $k\geq 2$, we provide a polynomial-time decision algorithm for the abelian case, that is, for structures of which each color class has an abelian automorphism group. While the graph classes we consider may seem quite restrictive, graphs with $4$-bounded abelian colors include CFI-graphs and multipedes, which form the basis of almost all known hard instances and lower bounds related to the Weisfeiler-Leman algorithm.

Counting logics with a bounded number of variables form one of the central concepts in descriptive complexity theory. Although they restrict the number of variables that a formula can contain, the variables can be nested within scopes of quantified occurrences of themselves. In other words, the variables can be requantified. We study the fragments obtained from counting logics by restricting requantification for some but not necessarily all the variables. Similar to the logics without limitation on requantification, we develop tools to investigate the restricted variants. Specifically, we introduce a bijective pebble game in which certain pebbles can only be placed once and for all, and a corresponding two-parametric family of Weisfeiler-Leman algorithms. We show close correspondences between the three concepts. By using a suitable cops-and-robber game and adaptations of the Cai-Fürer-Immerman construction, we completely clarify the relative expressive power of the new logics. We show that the restriction of requantification has beneficial algorithmic implications in terms of graph identification. Indeed, we argue that with regard to space complexity, non-requantifiable variables only incur an additive polynomial factor when testing for equivalence. In contrast, for all we know, requantifiable variables incur a multiplicative linear factor. Finally, we observe that graphs of bounded tree-depth and 3-connected planar graphs can be identified using no, respectively, only a very limited number of requantifiable variables.

The k -dimensional Weisfeiler-Leman ( k -WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applications in Babai’s quasipolynomial-time isomorphism algorithm, practical isomorphism solvers, and algebraic graph theory. However, it also has surprising connections to other areas such as logic, proof complexity, combinatorial optimization, and machine learning. The algorithm iteratively computes a coloring of the k -tuples of vertices of a graph. Since Fürer’s linear lower bound [ICALP 2001], it has been an open question whether there is a super-linear lower bound for the iteration number for k -WL on graphs. We answer this question affirmatively, establishing an Ω ( n k /2 )-lower bound for all k .

Abstract. A colored graph is [Formula: see text]-ultrahomogeneous if every isomorphism between two induced subgraphs of order at most [Formula: see text] extends to an automorphism. A colored graph is [Formula: see text]-tuple regular if the number of vertices adjacent to every vertex in a set [Formula: see text] of order at most [Formula: see text] depends only on the isomorphism type of the subgraph induced by [Formula: see text]. We classify the finite vertex-colored [Formula: see text]-ultrahomogeneous graphs and the finite vertex-colored [Formula: see text]-tuple regular graphs for [Formula: see text] and [Formula: see text], respectively. Our theorem in particular classifies finite vertex-colored ultrahomogeneous graphs, where ultrahomogeneous means the graph is simultaneously [Formula: see text]-ultrahomogeneous for all [Formula: see text].

We extend Choiceless Polynomial Time (CPT), the currently only remaining promising candidate in the quest for a logic capturing Ptime , so that this extended logic has the following property: for every class of structures for which isomorphism is definable, the logic automatically captures Ptime . For the construction of this logic, we extend CPT by a witnessed symmetric choice operator. This operator allows for choices from definable orbits. But, to ensure polynomial-time evaluation, automorphisms have to be provided to certify that the choice set is indeed an orbit. We argue that, in this logic, definable isomorphism implies definable canonization. Thereby, our construction removes the non-trivial step of extending isomorphism definability results to canonization. This step was a part of proofs that show that CPT or other logics capture Ptime on a particular class of structures. The step typically required substantial extra effort.

We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm Blocking and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g>0 and recovers the known tight bound for the planar case (g=0).

The k-dimensional Weisfeiler-Leman (k-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applications in Babai’s quasipolynomial-time isomorphism algorithm, practical isomorphism solvers, and algebraic graph theory. However, it also has surprising connections to other areas such as logic, proof complexity, combinatorial optimization, and machine learning. The algorithm iteratively computes a coloring of the k-tuples of vertices of a graph. Since Fürer’s linear lower bound [ICALP 2001], it has been an open question whether there is a super-linear lower bound for the iteration number for k-WL on graphs. We answer this question affirmatively, establishing an $\Omega\left(n^{k / 2}\right)$-lower bound for all k.

Dedicated treatment of symmetries in satisfiability problems (SAT) is indispensable for solving various classes of instances arising in practice. However, the exploitation of symmetries usually takes a black box approach. Typically, off-the-shelf external, general-purpose symmetry detection tools are invoked to compute symmetry groups of a formula. The groups thus generated are a set of permutations passed to a separate tool to perform further analyzes to understand the structure of the groups. The result of this second computation is in turn used for tasks such as static symmetry breaking or dynamic pruning of the search space. Within this pipeline of tools, the detection and analysis of symmetries typically incurs the majority of the time overhead for symmetry exploitation. In this paper we advocate for a more holistic view of what we call the SAT-symmetry interface. We formulate a computational setting, centered around a new concept of joint graph/group pairs, to analyze and improve the detection and analysis of symmetries. Using our methods, no information is lost performing computational tasks lying on the SAT-symmetry interface. Having access to the entire input allows for simpler, yet efficient algorithms. Specifically, we devise algorithms and heuristics for computing finest direct disjoint decompositions, finding equivalent orbits, and finding natural symmetric group actions. Our algorithms run in what we call instance-quasi-linear time, i.e., almost linear time in terms of the input size of the original formula and the description length of the symmetry group returned by symmetry detection tools. Our algorithms improve over both heuristics used in state-of-the-art symmetry exploitation tools, as well as theoretical general-purpose algorithms.

In a recent breakthrough, Babai [ Proceedings of STOC, ACM, New York, 2016, pp. 684--697] gave a quasipolynomial-time graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithm runs in time $n^{\mathcal{O}((\log d)^{c})}$, where $n$ is the number of vertices of the input graphs, $d$ is the maximum degree of the input graphs, and $c$ is an absolute constant. The best previous isomorphism test for graphs of maximum degree $d$ due to Babai, Kantor, and Luks [ Proceedings of FOCS, IEEE, New York, 1983, pp. 162--171] runs in time $n^{\mathcal{O}(d/ \log d)}$.

We investigate the relationship between various isomorphism invariants for finite groups. Specifically, we use the Weisfeiler-Leman dimension (WL) to characterize, compare and quantify the effectiveness and complexity of invariants for group isomorphism. It turns out that a surprising number of invariants and characteristic subgroups that are classic to group theory can be detected and identified by a low dimensional Weisfeiler-Leman algorithm. These include the center, the inner automorphism group, the commutator subgroup and the derived series, the abelian radical, the solvable radical, the Fitting group and π-radicals. A low dimensional WL-algorithm additionally determines the isomorphism type of the socle as well as the factors in the derives series and the upper and lower central series. We also analyze the behavior of the WL-algorithm for group extensions and prove that a low dimensional WL-algorithm determines the isomorphism types of the composition factors of a group. Finally we develop a new tool to define a canonical maximal central decomposition for groups. This allows us to show that the Weisfeiler-Leman dimension of a group is at most one larger than the dimensions of its direct indecomposable factors. In other words the Weisfeiler-Leman dimension increases by at most 1 when taking direct products.

We extend Choiceless Polynomial Time (CPT), the currently only remaining promising candidate in the quest for a logic capturing Ptime, so that this extended logic has the following property: for every class of structures for which isomorphism is definable, the logic automatically captures Ptime.

We classify graphs and, more generally, finite relational structures that are identified by C^2 , that is, two-variable first-order logic with counting. Using this classification, we show that it can be decided in almost linear time whether a structure is identified by C^2 . Our classification implies that for every graph identified by this logic, all vertex-colored versions of it are also identified. A similar statement is true for finite relational structures. We provide constructions that solve the inversion problem for finite relational structures in linear time. By a result due to Otto, this problem has been known to be polynomial-time solvable. For graphs, we conclude that every C^2 -equivalence class contains a representative whose orbits are exactly the classes of the C^2 -partition of its vertex set and which has a single automorphism witnessing this fact. We show that such statements are not true for general k by providing examples of graphs of order linear in k which are identified by C^3 , but for which the orbit partition is strictly finer than the C^k -partition. We also construct identified graphs which have vertex-colored versions that are not identified by C^k .

We engineer a new probabilistic Monte-Carlo algorithm for isomorphism testing. Most notably, as opposed to all other solvers, it implicitly exploits the presence of symmetries without explicitly computing them. We provide extensive benchmarks, showing that the algorithm outperforms all state-of-the-art solutions for isomorphism testing on most inputs from the de facto standard benchmark library for isomorphism testing. On many input types, our data not only show improved running times by an order of magnitude, but also reflect a better asymptotic behavior. Our results demonstrate that, with current algorithms, isomorphism testing is in practice easier than the related problems of computing the automorphism group or canonically labeling a graph. The results also show that probabilistic algorithms for isomorphism testing can be engineered to outperform deterministic approaches, even asymptotically.

In the quest for a logic capturing PTime the next natural classes of structures to consider are those with bounded color class size. We present a canonization procedure for graphs with dihedral color classes of bounded size in the logic of Choiceless Polynomial Time (CPT), which then captures PTime on this class of structures. This is the first result of this form for non-abelian color classes. The first step proposes a normal form which comprises a "rigid assemblage". This roughly means that the local automorphism groups form 2-injective 3-factor subdirect products. Structures with color classes of bounded size can be reduced canonization preservingly to normal form in CPT. In the second step, we show that for graphs in normal form with dihedral color classes of bounded size, the canonization problem can be solved in CPT. We also show the same statement for general ternary structures in normal form if the dihedral groups are defined over odd domains.

In practice symmetries of combinatorial structures are computed by transforming the structure into an annotated graph whose automorphisms correspond exactly to the desired symmetries. An automorphism solver is then employed to compute the automorphism group of the constructed graph. Such solvers have been developed for over 50 years, and highly efficient sequential, single core tools are available. However no competitive parallel tools are available for the task. We introduce a new parallel randomized algorithm that is based on a modification of the individualization-refinement paradigm used by sequential solvers. The use of randomization crucially enables parallelization. We report extensive benchmark results that show that our solver is competitive to state-of-the-art solvers on a single thread, while scaling remarkably well with the use of more threads. This results in order-of-magnitude improvements on many graph classes over state-of-the-art solvers. In fact, our tool is the first parallel graph automorphism tool that outperforms current sequential tools.

The individualization-refinement paradigm for computing a canonical labeling and the automorphism group of a graph is investigated. A new algorithmic design aimed at reducing the size of the associated search space is introduced, and a new tool, named "Traces", is presented, together with experimental results and comparisons with existing software, such as McKay's "nauty". It is shown that the approach presented here leads to a huge reduction in the search space, thereby making computation feasible for several classes of graphs which are hard for all the main canonical labeling tools in the literature.

Color refinement is a crucial subroutine in symmetry detection in theory as well as practice. It has further applications in machine learning and in computational problems from linear algebra. While tight lower bounds for the worst case complexity are known [Berkholz, Bonsma, Grohe, ESA2013] no comparative analysis of design choices for color refinement algorithms is available. We devise two models within which we can compare color refinement algorithms using formal methods, an online model and an approximation model. We use these to show that no online algorithm is competitive beyond a logarithmic factor and no algorithm can approximate the optimal color refinement splitting scheme beyond a logarithmic factor. We also directly compare strategies used in practice showing that, on some graphs, queue based strategies outperform stack based ones by a logarithmic factor and vice versa. Similar results hold for strategies based on priority queues.

Individualization-Refinement (IR) algorithms form the standard method and currently the only practical method for symmetry computations of graphs and combinatorial objects in general. Through backtracking, on each graph an IR-algorithm implicitly creates an IR-tree whose order is the determining factor of the running time of the algorithm. We give a precise and constructive characterization which trees are IR-trees. This characterization is applicable both when the tree is regarded as an uncolored object but also when regarded as a colored object where vertex colors stem from a node invariant. We also provide a construction that given a tree produces a corresponding graph whenever possible. This provides a constructive proof that our necessary conditions are also sufficient for the characterization.

We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL), which allows the design of purely combinatorial graph isomorphism tests that are more powerful than the well-known Weisfeiler-Leman algorithm. We prove that, as an abstract computational model, polynomial-time DeepWL-algorithms have exactly the same expressiveness as the logic Choiceless Polynomial Time (with counting) introduced by Blass, Gurevich, and Shelah (Ann. Pure Appl. Logic., 1999). It is a well-known open question whether the existence of a polynomial-time graph isomorphism test implies the existence of a polynomial-time canonisation algorithm. Our main technical result states that for each class of graphs (satisfying some mild closure condition), if there is a polynomial-time DeepWL isomorphism test, then there is a polynomial-time canonisation algorithm for this class. This implies that there is also a logic capturing polynomial time on this class.

This paper considers the length of resolution proofs when using Krishnamurthy's classic symmetry rules. We show that inconsistent linear equation systems of bounded width over a fixed finite field $\mathbb{F}_p$ with $p$ a prime have, in their standard encoding as CNFs, polynomial length resolutions when using the local symmetry rule (SRC-II). As a consequence it follows that the multipede instances for the graph isomorphism problem encoded as CNF formula have polynomial length resolution proofs. This contrasts exponential lower bounds for individualization-refinement algorithms on these graphs. For the Cai-Fürer-Immerman graphs, for which Torán showed exponential lower bounds for resolution proofs (SAT 2013), we also show that already the global symmetry rule (SRC-I) suffices to allow for polynomial length proofs.

In comparison to graphs, combinatorial methods for the isomorphism problem of finite groups are less developed than algebraic ones. To be able to investigate the descriptive complexity of finite groups and the group isomorphism problem, we define the Weisfeiler-Leman algorithm for groups. In fact we define three versions of the algorithm. In contrast to graphs, where the three analogous versions readily agree, for groups the situation is more intricate. For groups, we show that their expressive power is linearly related. We also give descriptions in terms of counting logics and bijective pebble games for each of the versions.

Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in \(O\left (n \log n\right )\) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For \(\sqrt {n} \le s \le n\) , we present algorithms that use \(O\left (s \log n\right )\) bits and \(O\left (\frac {1}{s} \cdot n^{2} \cdot \log n\right )\) time for computing the length of a longest increasing subsequence, and \(O\left (\frac {1}{s} \cdot n^{2} \cdot \log ^{2} n\right )\) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

We give a new FPT algorithm testing isomorphism of n -vertex graphs of tree-width k in time 2 kpolylog(k) n 3 , improving the FPT algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time 2 O(k5 log k) n 5 . Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree-width k . Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai’s algorithm as a black box in one place. We also give a second algorithm that, at the price of a slightly worse running time 2 O(k2 log k) n 3 , avoids the use of Babai’s algorithm and, more importantly, has the additional benefit that it can also be used as a canonization algorithm.

We show that the 2-dimensional Weisfeiler-Leman algorithm stabilizes n-vertex graphs after at most O(n log n) iterations. This implies that if such graphs are distinguishable in 3-variable first order logic with counting, then they can also be distinguished in this logic by a formula of quantifier depth at most O(n log n). For this we exploit a new refinement based on counting walks and argue that its iteration number differs from the classic Weisfeiler-Leman refinement by at most a logarithmic factor. We then prove matching linear upper and lower bounds on the number of iterations of the walk refinement. This is achieved with an algebraic approach by exploiting properties of semisimple matrix algebras. We also define a walk logic and a bijective walk pebble game that precisely correspond to the new walk refinement.

We devise a unified framework for the design of canonization algorithms. Using hereditarily finite sets, we define a general notion of combinatorial objects that includes graphs, hypergraphs, relational structures, codes, permutation groups, tree decompositions, and so on.

We prove that the Weisfeiler--Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in first-order logic with counting using at most 4 variables. The previously best-known upper bounds for the dimension and number of variables were 14 and 15, respectively. First, we show that, for dimension 3 and higher, the WL-algorithm correctly tests isomorphism of graphs in a minor-closed class whenever it determines the orbits of the automorphism group of every arc-colored 3-connected graph belonging to this class. Then, we prove that, apart from several exceptional graphs (which have WL-dimension at most 2), the individualization of two appropriately chosen vertices of a colored 3-connected planar graph followed by the one-dimensional WL-algorithm produces the discrete vertex partition. This implies that the three-dimensional WL-algorithm determines the orbits of arc-colored 3-connected planar graphs. As a byproduct of the proof, we get a classification of the 3-connected planar graphs with fixing number 3.

We show that on graphs with n vertices, the 2-dimensional Weisfeiler-Leman algorithm requires at most O(n^2/log(n)) iterations to reach stabilization. This in particular shows that the previously best, trivial upper bound of O(n^2) is asymptotically not tight. In the logic setting, this translates to the statement that if two graphs of size n can be distinguished by a formula in first-order logic with counting with 3 variables (i.e., in C3), then they can also be distinguished by a C3-formula that has quantifier depth at most O(n^2/log(n)). To prove the result we define a game between two players that enables us to decouple the causal dependencies between the processes happening simultaneously over several iterations of the algorithm. This allows us to treat large color classes and small color classes separately. As part of our proof we show that for graphs with bounded color class size, the number of iterations until stabilization is at most linear in the number of vertices. This also yields a corresponding statement in first-order logic with counting. Similar results can be obtained for the respective logic without counting quantifiers, i.e., for the logic L3.

In a recent breakthrough, Babai (STOC 2016) gave quasipolynomial graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithms runs in time n^O((log d)^c), where n is the number of vertices of the input graphs, d is the maximum degree of the input graphs, and c is an absolute constant. The best previous isomorphism test for graphs of maximum degree d due to Babai, Kantor and Luks (FOCS 1983) runs in time n^O(d log d).

The individualization-refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, the currently fastest implementations of isomorphism solvers all follow this approach. While these solvers are fast in practice, from a theoretical point of view, no general lower bounds concerning the worst case complexity of these tools are known. In fact, it is an open question what the running time of individualization-refinement algorithms is. For all we know some of the algorithms could have polynomial running time.

Colour refinement is at the heart of all the most efficient graph isomorphism software packages. In this paper we present a method for extending the applicability of refinement algorithms to directed graphs with weighted edges. We use {Traces} as a reference software, but the proposed solution is easily transferrable to any other refinement-based graph isomorphism tool in the literature. We substantiate the claim that the performances of the original algorithm remain substantially unchanged by showing experiments for some classes of benchmark graphs.

The paper develops a new technique to extract a characteristic subset from a random source that repeatedly samples from a set of elements. Here a characteristic subset is a set that when containing an element contains all elements that have the same probability. With this technique at hand the paper looks at the special case of the tournament isomorphism problem that stands in the way towards a polynomial-time algorithm for the graph isomorphism problem. Noting that there is a reduction from the automorphism (asymmetry) problem to the isomorphism problem, a reduction in the other direction is nevertheless not known and remains a thorny open problem. Applying the new technique, we develop a randomized polynomial-time Turing-reduction from the tournament isomorphism problem to the tournament automorphism problem. This is the first such reduction for any kind of combinatorial object not known to have a polynomial-time solvable isomorphism problem.

We prove that the Weisfeiler-Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in first-order logic with counting using at most 4 variables. The previously best known upper bounds for the dimension and number of variables were 14 and 15, respectively. First we show that, for dimension 3 and higher, the WL-algorithm correctly tests isomorphism of graphs in a minor-closed class whenever it determines the orbits of the automorphism group of any arc-colored 3-connected graph belonging to this class. Then we prove that, apart from several exceptional graphs (which have WL-dimension at most 2), the individualization of two correctly chosen vertices of a colored 3-connected planar graph followed by the 1-dimensional WL-algorithm produces the discrete vertex partition. This implies that the 3-dimensional WL-algorithm determines the orbits of a colored 3-connected planar graph. As a byproduct of the proof, we get a classification of the 3-connected planar graphs with fixing number 3.

We show that on graphs with n vertices the 2-dimensional Weisfeiler-Leman algorithm requires at most O(n2 / log(n)) iterations to reach stabilization. This in particular shows that the previously best, trivial upper bound of O(n2) is asymptotically not tight. In the logic setting this translates to the statement that if two graphs of size n can be distinguished by a formula in first order logic with counting with 3 variables (i.e., in C3) then they can also be distinguished by a C3-formula that has quantifier depth at most O(n2 / log(n)).

Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized in deterministic logarithmic space (logspace). This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous classes of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined.

Tangles of graphs have been introduced by Robertson and Seymour in the context of their graph minor theory. Tangles may be viewed as describing “$k$-connected components” of a graph (though in a twisted way). An interesting aspect of tangles is that they can be defined not only for graphs, but more generally for arbitrary connectivity functions (that is, integer-valued submodular and symmetric set functions). However, tangles are difficult to deal with algorithmically. To start with, it is unclear how to represent them, because they are families of separations and, as such, may be exponentially large. Our first contribution is a data structure for representing and accessing all tangles of a graph up to some fixed order. Using this data structure, we can prove an algorithmic version of a very general structure theorem due to Carmesin et al. (for graphs) and Hundertmark (for arbitrary connectivity functions) that yields a canonical tree decomposition whose parts correspond to the maximal tangles. This may be viewed as a generalization of the decomposition of a graph into its 3-connected components.

We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the rank width of a graph is bounded in terms of its clique width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.

In this paper we resolve the complexity of the isomorphism problem on all but finitely many of the graph classes characterized by two forbidden induced subgraphs. To this end we develop new techniques applicable for the structural and algorithmic analysis of graphs. First, we develop a methodology to show isomorphism completeness of the isomorphism problem on graph classes by providing a general framework unifying various reduction techniques. Second, we generalize the concept of the modular decomposition to colored graphs, allowing for non-standard decompositions. We show that, given a suitable decomposition functor, the graph isomorphism problem reduces to checking isomorphism of colored prime graphs. Third, we extend the techniques of bounded color valence and hypergraph isomorphism on hypergraphs of bounded color class size as follows. We say a colored graph has generalized color valence at most k if, after removing all vertices in color classes of size at most k, for each color class C every vertex has at most k neighbors in C or at most k non-neighbors in C. We show that isomorphism of graphs of bounded generalized color valence can be solved in polynomial time.

Tangles of graphs have been introduced by Robertson and Seymour in the context of their graph minor theory. Tangles may be viewed as describing "k-connected components" of a graph (though in a twisted way). They play an important role in graph minor theory. An interesting aspect of tangles is that they cannot only be defined for graphs, but more generally for arbitrary connectivity functions (that is, integer-valued submodular and symmetric set functions).

The competition graph of an acyclic directed graph $D$ is the undirected graph on the same vertex set as $D$ in which two distinct vertices are adjacent if they have a common out-neighbor in $D$. The competition number of an undirected graph $G$ is the least number of isolated vertices that have to be added to $G$ to make it the competition graph of an acyclic directed graph. We resolve two conjectures concerning competition graphs. First, we prove a conjecture of Opsut by showing that the competition number of every quasi-line graph is at most 2. Recall that a quasi-line graph, also called a locally co-bipartite graph, is a graph for which the neighborhood of every vertex can be partitioned into at most two cliques. To prove this conjecture we devise an alternative characterization of quasi-line graphs to the one by Chudnovsky and Seymour. Second, we prove a conjecture of Kim by showing that the competition number of any graph is at most one greater than the number of holes in the graph. Our methods also allow us to prove a strengthened form of this conjecture recently proposed by Kim et al., showing that the competition number of any graph is at most one greater than the dimension of the subspace of the cycle space spanned by the holes.

It has long been known that for the paging problem in its standard form, competitive analysis cannot adequately distinguish algorithms based on their performance: there exists a vast class of algorithms that achieve the same competitive ratio, ranging from extremely naive and inefficient strategies (such as Flush-When-Full), to strategies of excellent performance in practice (such as Least-Recently-Used and some of its variants). A similar situation arises in the list update problem: in particular, under the cost formulation studied by Martínez and Roura [2000] and Munro [2000] every list update algorithm has, asymptotically, the same competitive ratio. Several refinements of competitive analysis, as well as alternative performance measures have been introduced in the literature, with varying degrees of success in narrowing this disconnect between theoretical analysis and empirical evaluation. In this article, we study these two fundamental online problems under the framework of bijective analysis [Angelopoulos et al. 2007, 2008]. This is an intuitive technique that is based on pairwise comparison of the costs incurred by two algorithms on sets of request sequences of the same size. Coupled with a well-established model of locality of reference due to Albers et al. [2005], we show that Least-Recently-Used and Move-to-Front are the unique optimal algorithms for paging and list update, respectively. Prior to this work, only measures based on average-cost analysis have separated LRU and MTF from all other algorithms. Given that bijective analysis is a fairly stringent measure (and also subsumes average-cost analysis), we prove that in a strong sense LRU and MTF stand out as the best (deterministic) algorithms.

To deploy a wireless sensor network for the purpose of large-scale monitoring, in this paper, we propose a heterogeneous and hierarchical wireless sensor network architecture. The architecture consists of sensor nodes, gateway nodes, and mobile sinks. The sensors transmit their sensing data to the gateway nodes for temporary storage through multihop relays, while the mobile sinks travel along predetermined trajectories to collect data from nearby gateway nodes. Under this paradigm of data gathering, we formulate a novel constrained optimization problem, namely, the capacitated minimum forest (CMF) problem, for the decision version of which we first show NP-completeness. We then devise approximation algorithms and provide upper bounds for their approximation ratios. We finally evaluate the performance of the proposed algorithms through experimental simulation. In our experiments, the approximation ratio delivered by the proposed algorithms is always less than 2. In the case of arbitrary gateway capacities, this contrasts our theoretical results which show that the approximation ratio is at most linear in the number of gateways. Our experiments thus indicate that for realistic inputs, our worst case analysis of the approximation ratio is very conservative. The proposed algorithms are the first approximation algorithms for the CMF problem, and our techniques may be applicable to other constrained optimization problems beyond wireless sensor networks.

It has long been known that for the paging problem in its standard form, competitive analysis cannot adequately distinguish algorithms based on their performance: there exists a vast class of algorithms which achieve the same competitive ratio, ranging from extremely naive and inefficient strategies (such as Flush-When-Full), to strategies of excellent performance in practice (such as Least-Recently-Used and some of its variants).A similar situation arises in the list update problem: in particular, under the cost formulation studied by Martínez and Roura [TCS 2000] and Munro [ESA 2000] every list update algorithm has, asymptotically, the same competitive ratio.Several refinements of competitive analysis, as well as alternative performance measures have been introduced in the literature, with varying degrees of success in narrowing this disconnect between theoretical analysis and empirical evaluation.In this paper we study these two fundamental online problems under the framework of bijective analysis [Angelopoulos, Dorrigiv and López-Ortiz, SODA 2007 and LATIN 2008].This is an intuitive technique which is based on pairwise comparison of the costs incurred by two algorithms on sets of request sequences of the same size.Coupled with a well-established model of locality of reference due to Albers, Favrholdt and Giel [JCSS 2005], we show that Least-Recently-Used and Move-to-Front are the unique optimal algorithms for paging and list update, respectively.Prior to this work, only measures based on average-cost analysis have separated LRU and MTF from all other algorithms.Given that bijective analysis is a fairly stringent measure (and also subsumes average-cost analysis), we prove that in a strong sense LRU and MTF stand out as the best algorithms.

We present a novel randomized approach to the graph isomorphism problem. Our algorithm aims at solving difficult instances by producing randomized certificates for non-isomorphism. We compare our implementation to the de facto standard nauty. On many of the hardest known instances, the incidence graphs of finite projective planes, our program is considerably faster than nauty. However, it is inherent to our approach that it performs better on pairs of non-isomorphic graphs than on isomorphic instances. Our algorithm randomly samples substructures in the given graphs in order to detect dissimilarities between them. The choice of the sought-after structures as well as the tuning of the search process is dynamically adapted during the sampling. Eventually, a randomized certificate is produced by which the user can verify the non-isomorphism of the input graphs. As a byproduct of our approach, we introduce a new concept of regularity for graphs which is meant to capture the computational hardness of isomorphism problems on graphs.