Search

Given a clique-width $k$-expression of a graph $G$, we provide $2^{O(k)}\cdot n$ time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree, Connected Dominating Set, or Connected Vertex Cover. We also propose a $2^{O(k)}\cdot n$ time algorithm for Feedback Vertex Set. The best running times for all the considered cases were either $2^{O(k\cdot \log(k))}\cdot n^{O(1)}$ or worse.

The 0–1-knapsack problem is a well-known NP-hard problem in combinatorial optimization. We consider the extensions to the knapsack problem with conflict graph (KCG) and the knapsack problem with forcing graph (KFG). KCG has first been introduced by Yamada et al. and represents incompatibilities between items of the knapsack instance. KFG has been introduced by Pferschy and Schauer and represents the necessity of items for other items. Within this paper we provide pseudo-polynomial solutions for KCG and KFG with co-graphs as conflict and forcing graphs and extend these solutions to conflict and forcing graphs of bounded clique-width. Our solutions are based on dynamic programming using the tree-structure representing the conflict graph and the forcing graph. Further we conclude fully polynomial time approximation schemes for KCG on conflict graphs of bounded clique-width and KFG on forcing graphs of bounded clique-width. This generalizes the known results for conflict graphs and forcing graphs of bounded tree-width of Pferschy and Schauer.

Finding a diagonal matrix congruent to $A - cI$ for constants $c$, where $A$ is the adjacency matrix of a graph $G$ allows us to quickly tell the number of eigenvalues in a given interval. If $G$ has clique-width $k$ and a corresponding $k$-expression is known, then diagonalization can be done in time $O(\text{poly}(k) n)$ where $n$ is the order of $G$., Comment: 25 pages

We discover new hereditary classes of graphs that are minimal (with respect to set inclusion) of unbounded clique-width. The new examples include split permutation graphs and bichain graphs. Each of these classes is characterised by a finite list of minimal forbidden induced subgraphs. These, therefore, disprove a conjecture due to Daligault, Rao and Thomasse from 2010 claiming that all such minimal classes must be defined by infinitely many forbidden induced subgraphs. In the same paper, Daligault, Rao and Thomasse make another conjecture that every hereditary class of unbounded clique-width must contain a labelled infinite antichain. We show that the two example classes we consider here satisfy this conjecture. Indeed, they each contain a canonical labelled infinite antichain, which leads us to propose a stronger conjecture: that every hereditary class of graphs that is minimal of unbounded clique-width contains a canonical labelled infinite antichain., Comment: 17 pages, 7 figures

1.1 The VLSI Verification Problem Verification of integrated circuit design is a process that checks the implementation of the design against its specification and identifies design bugs. The view that design verification is subservient to design implementation has soon become invalid when designs become just moderately complex. It has been claimed that the verification complexity is growing at a double-exponential rate (Saleh, 2004), i.e., exponential with respect to Moore’s law. Consequently, nowadays, about 50%-80% of the design time and efforts are spent in verylarge-scale-integration (VLSI) design verification. It becomes well known that verification is the biggest single bottleneck (Goering, 2008) in VLSI design. There are two categories of verification methods. • Simulation-based methods. In this category, the verification engineers develop a set of tests to stress a given design; the design is therefore often called the design-under-test or DUT. A test can be an abstract description about the control and observation applied upon the DUT. To actually apply the control and observation, a structure called test-bench (TB) needs to be constructed and simulated together with the DUT. The TB concretizes the abstract tests into “0/1” signals and directly interact with the DUT in these signals. • Formal methods. In formal methods, verification engineers don’t provide tests, but design properties – properties that a correct design should or should not have. Meanwhile, the design usually needs to be represented as a finite-state-machine (FSM) model. Then some model-checking tool computes whether the model abides by the properties. Formal methods form useful supplement to simulation in verifying control-intensive and FSM-based designs.

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability. In this paper we design a succinct data structure for graphs on $n$ vertices whose clique-width is at most $k \leq \epsilon \sqrt{\log n / \log \log n}$ for some constant $0 , along with supporting degree, adjacency, neighborhood queries efficiently. This resolves an open problem of Kamali (Algorithmica-2018).

We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial-time results on graph classes, and answers open questions posed by Campos and Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b-Coloring and Fall Coloring are tight under the Exponential Time Hypothesis., LIPIcs, Vol. 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), pages 43:1-43:15

Given an undirected graph, a conflict-free coloring (CFON*) is an assignment of colors to a subset of the vertices of the graph such that for every vertex there exists a color that is assigned to exactly one vertex in its open neighborhood. The minimum number of colors required for such a coloring is called the conflict-free chromatic number. The decision version of the CFON* problem is NP-complete even on planar graphs.

This, the last chapter of the book, might be called ‘beyond line graphs’ because most of the graphs under consideration are not in fact line graphs. Recall that Krausz’s characterization theorem was this: A graph is a line graph if and only if its edges can be partitioned into complete subgraphs in such a way that each vertex is in just one or two of the subgraphs. Here, we extend this idea and define the Krausz dimension of a graph G to be the minimum value of d for which the edge set of G can be partitioned into complete subgraphs in such a way that each vertex is in at most d of the subgraphs. This turns out to be an NP-complete parameter, and so our focus is on bounds and critical graphs.

An acyclic r-coloring of a directed graph \(G=(V,E)\) is a partition of the vertex set V into r acyclic sets. The dichromatic number of a directed graph G is the smallest r such that G allows an acyclic r-coloring. For symmetric digraphs the dichromatic number equals the well-known chromatic number of the underlying undirected graph. This allows us to carry over the \(\text {W}[1]\)-hardness and lower bounds for running times of the chromatic number problem parameterized by clique-width to the dichromatic number problem parameterized by directed clique-width. We introduce the first polynomial-time algorithm for the acyclic coloring problem on digraphs of constant directed clique-width. From a parameterized point of view our algorithm shows that the Dichromatic Number problem is in \(\text {XP}\) when parameterized by directed clique-width and extends the only known structural parameterization by directed modular width for this problem. Furthermore, we apply defineability within monadic second order logic in order to show that Dichromatic Number problem is in \(\text {FPT}\) when parameterized by the directed clique-width and r. For directed co-graphs, which is a class of digraphs of directed clique-width 2, we even show a linear time solution for computing the dichromatic number.

Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify ���-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of ���-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can approximate every possible ���-branchwidth, providing a unifying parameterized framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions., LIPIcs, Vol. 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 63:1-63:23

In this paper, we present an algorithm to approximate the clique-width of a graph. The proposed approach is based on computing the shortest paths between pairs of vertices. We experimentally show that our proposal approximates the clique-width of simple graphs in polynomial time, while other methods that calculate it in an exact way, transform the problem to SAT, that is well-known as NP-Complete.

Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable to intractable? This type of question is by now very well-studied, but, somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes "for free". Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy First-Fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP-hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width., Comment: Conference version appeared in ESA 2020. This is the full version which has been accepted for publication at SIDMA

Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is FPT when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter. Specifically, we define an ( α , β , δ ) -clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most δ labels, a) every label consists of at most β sets of twin vertices, and b) all the labels together induce a graph with independence number at most α. We show that for every two constants α , δ > 0 the problem is FPT when parameterized by β plus the smallest width of an ( α , β , δ ) -clique-width decomposition.

Representations of graphs are a way of encoding the structure of a graph by using other discrete structures. The object of a representation of a graph is to encode its structure efficiently. Typically a graph can be encoded by an n× n adjacency matrix. It is possible, however, to encode graphs much more efficiently using other representation schemes. This work considers tree representations of graphs. A tree representation of a target graph G is an assignment of subtrees of a host tree to the vertices of G in such a way that if uv ∈ E(G), then the subtree assigned to the vertex u and the subtree assigned to the vertex v have at least t nodes in common. This study considers tree representations such that the host tree comes from the family of subdivided n-stars. The largest such representable asteroidal set is constructed, and a lower bound on the length of the longest cycle representable on this family of host tree is also discovered. Next we move to a different area of study. The study of closure systems and closure spaces is a relatively new direction in mathematics. Jamison writes in his new text that ‘the notion of closure is pervasive throughout mathematics’. Surely, closure and closed sets can be discussed in almost any mathematical setting. It has been shown by Pfaltz in 1995 that for any finite ground set S, with |S| = n such that n ≥ 10, there are n unique closure operators on S. In topology, the separation properties provide criteria for categorizing topological spaces. While not all closure spaces are topological spaces, we may still explore whether the separation properties hold under certain conditions. This work defines a class of closure operators on the integers and investigates the conditions for which the resulting closure space satisfies the different definitions of separability.

Daligault, Rao and Thomass\'e asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev (JCTB 2017+) gave a negative answer to this question, but their counterexample is a class that can only be characterised by infinitely many forbidden induced subgraphs. This raises the issue of whether the question has a positive answer for finitely defined hereditary graph classes. Apart from two stubborn cases, this has been confirmed when at most two induced subgraphs $H_1,H_2$ are forbidden. We confirm it for one of the two stubborn cases, namely for the $(H_1,H_2)=(\mbox{triangle},P_2+P_4)$ case, by proving that the class of $(\mbox{triangle},P_2+P_4)$-free graphs has bounded clique-width and is well-quasi-ordered. Our technique is based on a special decomposition of $3$-partite graphs. We also use this technique to prove that the class of $(\mbox{triangle},P_1+P_5)$-free graphs, which is known to have bounded clique-width, is well-quasi-ordered. Our results enable us to complete the classification of graphs $H$ for which the class of $(\mbox{triangle},H)$-free graphs is well-quasi-ordered., Comment: 32 pages, 4 figures. An extended abstract of this paper appeared in the proceedings of WG 2017

Clique-width is one of the most important parameters that describes structural complexity of a graph. Probably, only treewidth is more studied graph width parameter. In this paper we study how clique-width influences the complexity of the Maximum Happy Vertices (MHV) and Maximum Happy Edges (MHE) problems. We answer a question of Choudhari and Reddy ’18 about parameterization by the distance to threshold graphs by showing that MHE is \(\mathrm {NP}\)-complete on threshold graphs. Hence, it is not even in \(\mathrm {XP}\) when parameterized by clique-width, since threshold graphs have clique-width at most two. As a complement for this result we provide a \(n^{\mathcal {O}(\ell \cdot \mathrm {cw})}\) algorithm for MHE, where \(\ell \) is the number of colors and \(\mathrm {cw}\) is the clique-width of the input graph. We also construct an \(\mathrm {FPT}\) algorithm for MHV with running time \(\mathcal {O}^*((\ell +1)^{\mathcal {O}(\mathrm {cw})})\), where \(\ell \) is the number of colors in the input. Additionally, we show \(\mathcal {O}(\ell n^2)\) algorithm for MHV on interval graphs.

Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class \(\mathcal{G}\) if they are so on the atoms (graphs with no clique cut-set) of \(\mathcal{G}\). Hence, we initiate a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A graph G is H-free if H is not an induced subgraph of G, and it is \((H_1,H_2)\)-free if it is both \(H_1\)-free and \(H_2\)-free. A class of H-free graphs has bounded clique-width if and only if its atoms have this property. This is no longer true for \((H_1,H_2)\)-free graphs, as evidenced by one known example. We prove the existence of another such pair \((H_1,H_2)\) and classify the boundedness of clique-width on \((H_1,H_2)\)-free atoms for all but 18 cases.

Given a graph \(G=(V,E)\), the vertex expansion of a set \(S\subset V\) is defined as \( \varPhi ^V(S)=\frac{|N(S)|}{|S|}. \) In the Small Set Vertex Expansion (SSVE) problem, we are given a graph \(G=(V,E)\) and a positive integer \(k\le \frac{|V(G)|}{2}\), the goal is to return a set \(S\subset V(G)\) of k nodes minimizing the vertex expansion \( \varPhi ^V(S)=\frac{|N(S)|}{k}\); equivalently minimizing |N(S)|. SSVE has not been as well studied as its edge-based counterpart Small Set Expansion (SSE). SSE, and SSVE to a less extend, have been studied due to their connection to other hard problems including the Unique Games Conjecture and Graph Colouring. Using the hardness of Minimum k-Union problem, we prove that Small Set Vertex Expansion problem is NP-complete. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[1]-hard when parameterized by k, (2) the problem is fixed-parameter tractable (FPT) when parameterized by the neighbourhood diversity nd, and (3) it is fixed-parameter tractable (FPT) when parameterized by treewidth tw of the input graph.

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set ${\cal H}$ of forbidden induced subgraphs. We initiate a systematic study into the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the $|{\cal H}|=1$ case by classifying the boundedness of clique-width for every set ${\cal H}$ of self-complementary graphs. We then completely settle the $|{\cal H}|=2$ case. In particular, we determine one new class of $(H,\overline{H})$-free graphs of bounded clique-width (as a side effect, this leaves only six classes of $(H_1,H_2)$-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the $|{\cal H}|=2$ case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for a set ${\cal F}$ of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for $(\{H,\overline{H}\}\cup {\cal F})$-free graphs coincides with the one for the $|{\cal H}|=2$ case if and only if ${\cal F}$ does not include the bull (the only non-empty self-complementary graphs on fewer than five vertices are $P_1$ and $P_4$, and $P_4$-free graphs have clique-width at most $2$). Finally, we discuss the consequences of our results for the Colouring problem., Comment: 39 pages, 7 figures

The Satisfactory Partition problem consists in deciding if the set of vertices of a given undirected graph can be partitioned into two nonempty parts such that each vertex has at least as many neighbours in its part as in the other part. The Balanced Satisfactory Partition problem is a variant of the above problem where the two partite sets are required to have the same cardinality. Both problems are known to be NP-complete. This problem was introduced by Gerber and Kobler [European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors, but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The three main results of the paper are the following: (1) The Satisfactory Partition problem is polynomial-time solvable for block graphs, (2) The Satisfactory Partition problem and its balanced version can be solved in polynomial time for graphs of bounded clicque-width, and (3) A generalized version of the Satisfactory Partition problem is W[1]-hard when parametrized by treewidth.

Golumbic and Trenk first introduced tolerance graph [7] to generalize some well-known applications of interval graphs. In a tolerance graph, every vertex is represented by an interval and a tolerance such that an edge occurs if and only if the overlap of corresponding intervals is at least as large as the tolerance associated with one of the vertices. Resource allocation sharing tolerate among users and certain scheduling problems can be modeled by tolerance graphs.

Recently, people, devices, processes, and other entities have been more connected than at any other point in history. In general, a graph is a natural, neat, and flexible structure to model the complex relationships, interactions, and interdependencies between objects (Fig. 4.1). In particular, each graph consists of nodes (or vertices) that represent objects and edges (or links) that represent the relationships among the graph nodes. Graphs have been widely used to represent datasets in a wide range of application domains such as social science, astronomy, computational biology, telecommunications, computer networks, semantic Web, protein networks, and many others (Sakr and Pardede, Graph Data Management: Techniques and Applications, 2011 [73]).

Computing all-pairs shortest paths is a fundamental and much-studied problem with many applications. Unfortunately, despite intense study, there are still no significantly faster algorithms for it than the 𝒪(n³) time algorithm due to Floyd and Warshall (1962). Somewhat faster algorithms exist for the vertex-weighted version if fast matrix multiplication may be used. Yuster (SODA 2009) gave an algorithm running in time 𝒪(n^2.842), but no combinatorial, truly subcubic algorithm is known. Motivated by the recent framework of efficient parameterized algorithms (or "FPT in P"), we investigate the influence of the graph parameters clique-width (cw) and modular-width (mw) on the running times of algorithms for solving ALL-PAIRS SHORTEST PATHS. We obtain efficient (and combinatorial) parameterized algorithms on non-negative vertex-weighted graphs of times 𝒪(cw²n²), resp. 𝒪(mw²n + n²). If fast matrix multiplication is allowed then the latter can be improved to 𝒪(mw^{1.842} n + n²) using the algorithm of Yuster as a black box. The algorithm relative to modular-width is adaptive, meaning that the running time matches the best unparameterized algorithm for parameter value mw equal to n, and they outperform them already for mw ∈ 𝒪(n^{1 - ε}) for any ε > 0., LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 38:1-38:15

M AX -C UT , E DGE D OMINATING S ET , G RAPH C OLORING , and H AMILTONIAN C YCLE on graphs of bounded clique-width have received significant attention as they can be formulated in MSO 2 (and, therefore, have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle’s theorem), but cannot be formulated in MSO 1 (which would have yielded linear-time algorithms on bounded clique-width graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g ( k ) n f ( k ) on graphs of clique-width k . Fomin et al. (2010) showed that the running times cannot be improved to g ( k ) n O (1) assuming W[1]≠FPT. However, this does not rule out non-trivial improvements to the exponent f ( k ) in the running times. In a follow-up paper, Fomin et al. (2014) improved the running times for E DGE D OMINATING S ET and M AX -C UT to n O ( k ) , and proved that these problems cannot be solved in time g ( k ) n o ( k ) unless ETH fails. Thus, prior to this work, E DGE D OMINATING S ET and M AX -C UT were known to have tight n Θ ( k ) algorithmic upper and lower bounds. In this article, we provide lower bounds for H AMILTONIAN C YCLE and G RAPH C OLORING . For H AMILTONIAN C YCLE , our lower bound g ( k ) n o ( k ) matches asymptotically the recent upper bound n O ( k ) due to Bergougnoux, Kanté, and Kwon (2017). As opposed to the asymptotically tight n Θ( k ) bounds for E DGE D OMINATING S ET , M AX -C UT , and H AMILTONIAN C YCLE , the G RAPH C OLORING problem has an upper bound of n O (2 k ) and a lower bound of merely n o (√ [4] k ) (implicit from the W[1]-hardness proof). In this article, we close the gap for G RAPH C OLORING by proving a lower bound of n 2 o ( k ) . This shows that G RAPH C OLORING behaves qualitatively different from the other three problems. To the best of our knowledge, G RAPH C OLORING is the first natural problem known to require exponential dependence on the parameter in the exponent of n .

Recently, there have been found relations between the algebraic co-rank and the zero forcing number along with the minimum rank. We continue on this direction by giving a characterization of the graphs with real algebraic co-rank at most 2. This implies that for any graph with minimum rank at most 3, its minimum rank is bounded from above by its real algebraic co-rank. This sheds some light on the conjecture that the real minimum rank is bounded from above by the real algebraic co-rank.

In this paper, we show that for a fixed k, there is an NC algorithm that separates the graphs of rank-width at most k from those with rank-width at least, by Bireswar Das, Anirban Dasgupta, Murali Krishna Enduri, and Vinod I. Reddy, 2018-08-10 12:16:50, https://doi.org/10.1016/j.ipl.2018.07.007

We rephrase the Distance labeling problem as a specific uniform variant of the Channel Assignment problem and show that the latter one is fixed parameter tractable when parameterized by the neighborhood diversity together with the largest weight. Consequently, the Distance labeling problem is FPT when parameterized by the neighborhood diversity, the maximum p i and k . This is indeed a more general answer to an open question of Fiala et al.: Parameterized complexity of coloring problems: Treewidth versus vertex cover. Finally, we show that the uniform variant of the Channel Assignment problem becomes NP -complete when generalized to graphs of bounded clique width.

A more descriptive but too long title would be : Constructing fly-automata to check properties of graphs of bounded tree-width expressed by monadic second-order formulas written with edge quantifications. Such properties are called MSO2 in short. Fly-automata (FA) run bottom-up on terms denoting graphs and compute " on the fly " the necessary states and transitions instead of looking into huge, actually unimplementable tables. In previous works, we have constructed FA that process terms denoting graphs of bounded clique-width, in order to check their monadic second-order (MSO) properties (expressed by formulas without edge quan-tifications). Here, we adapt these FA to incidence graphs, so that they can check MSO2 properties of graphs of bounded tree-width. This is possible because: (1) an MSO2 property of a graph is nothing but an MSO property of its incidence graph and (2) the clique-width of the incidence graph of a graph is linearly bounded in terms of its tree-width. Our constructions are actually implementable and usable. We detail concrete constructions of automata in this perspective.

Does well-quasi-ordering by induced subgraphs imply bounded clique-width for hereditary\ud classes? This question was asked by Daligault, Rao, and Thomass ́e [Well-quasi-order of\ud relabel functions. Order, 27(3) (2010), 301–315]. We answer this question negatively by\ud presenting a hereditary class of graphs of unbounded clique-width which is well-quasi-ordered\ud by the induced subgraph relation. We also show that graphs in our class have at most\ud logarithmic clique-width and that the number of minimal forbidden induced subgraphs for\ud our class is infinite. These results lead to a conjecture relaxing the above question and to a\ud number of related open questions connecting well-quasi-ordering and clique-width.

Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically, we apply a mathematical programming formulation and several heuristic methods based on the tabu search methodology to solve it. In line with the previous paper on this topic, we consider bipartite graphs in our experimentation. The extensive computational experiments with more than 1000 instances show the superiority of our proposals in both, quality and computing time.

This paper introduces a system for measuring the elegance of a graph based on the steps needed to build the graph and on its symmetry structure. The measure is designed to capture the essence of the notion of elegance in mathematics, namely, simplicity and clarity. The term “elegance” is used instead of “aesthetics” to distinguish the measure from those dependent on visual representation of a graph. Elegance is based solely on the abstract properties of a graph. A framework for measurement is defined and applied in a special case.

Graph transduction methods have been widely adopted for label prediction under semi-supervised settings. To alleviate the relevant sensitivity to initial labels and graph construction processes, recent studies have been aiming at developing robust graph transduction techniques. In particular, the graph transduction method via greedy gradient Max-Cut (GGMC) that minimizes a cost function over a continuous classification function and a binary label variable has been successfully applied to a wide range of applications. However, this method predominately relies on the choice of a high-quality single graph representation, often leading to unstable performance due to selection bias. To tackle this major drawback, we leverage an ensemble learning framework into the GGMC method for exploiting the advantage of constructing and combining multiple graphs. As opposed to performing constrained Max-Cut on a single graph, the proposed multiple graph greedy gradient Max-Cut method (MG-GGMC) simultaneously solves the label prediction and the true graph estimation problems. Specifically, the true graph is approximated by a linear combination of a set of constructed graphs. The coefficients of the linear combination are learned automatically by alternately minimizing a unified objective function in an iterative manner. Comparison studies with representative methods across various real-world benchmarks conspicuously demonstrate the efficaciousness and the superiority of the proposed algorithm in standard evaluation metrics.