**On the price of independence for vertex cover, feedback vertex set and odd cycle transversal**
(2023)

Journal Article

Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2023). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. European Journal of Combinatorics, https://doi.org/10.1016/j.ejc.2023.103821

# Outputs (66)

Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs(2023)

Conference Proceeding

Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57For any finite set H = {H1,. .. , Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,. .. , Hp as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed... Read More about Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs.

The Complexity of Matching Games: A Survey(2023)

Journal Article

Benedek, M., Biro, P., Johnson, M., Paulusma, D., & Ye, X. (2023). The Complexity of Matching Games: A Survey. Journal of Artificial Intelligence Research, 77, 459-485. https://doi.org/10.1613/jair.1.14281Matching games naturally generalize assignment games, a well-known class of cooperative games. Interest in matching games has grown recently due to some breakthrough results and new applications. This state-of-the-art survey provides an overview of m... Read More about The Complexity of Matching Games: A Survey.

Computing weighted subset odd cycle transversals in H-free graphs(2022)

Journal Article

For the Odd Cycle Transversal problem, the task is to find a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal problem requires S to intersect only those odd cycles that include a vertex of... Read More about Computing weighted subset odd cycle transversals in H-free graphs.

Computing subset transversals in H-free graphs(2021)

Journal Article

we study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free graphs, that is, to graphs that do not contain some fixed graph... Read More about Computing subset transversals in H-free graphs.

Computing weighted subset transversals in H-free graphs(2021)

Presentation / Conference Contribution

For the Odd Cycle Transversal problem, the task is to nd a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal requires S to intersect only those odd cycles that include a vertex of a disting... Read More about Computing weighted subset transversals in H-free graphs.

Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration(2021)

Journal Article

We continue research into a well-studied family of problems that ask whether the vertices of a given graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We consider the ca... Read More about Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration.

What graphs are 2-dot product graphs?(2021)

Journal Article

Let d ≥ 1 be an integer. From a set of d-dimensional vectors, we obtain a d-dot product graph by letting each vector a u correspond to a vertex u and by adding an edge between two vertices u and v if and only if their dot product a u · a v ≥ t, for s... Read More about What graphs are 2-dot product graphs?.

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective(2021)

Journal Article

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to -... Read More about Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective.

Steiner trees for hereditary graph classes(2020)

Presentation / Conference Contribution

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (... Read More about Steiner trees for hereditary graph classes.

Computing subset transversals in H-free graphs(2020)

Presentation / Conference Contribution

We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free graphs, that is, to graphs that do not contain some fixed graph... Read More about Computing subset transversals in H-free graphs.

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy(2020)

Journal Article

We resolve the computational complexity of GRAPH ISOMORPHISM for classes of graphs characterized by two forbidden induced subgraphs H_{1} and H_2 for all but six pairs (H_1,H_2). Schweitzer had previously shown that the number of open cases was finit... Read More about Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy.

Clique-width for graph classes closed under complementation(2020)

Journal Article

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 H of forbidden induced subgraphs. We study the boundedness of cliq... Read More about Clique-width for graph classes closed under complementation.

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest(2020)

Journal Article

A graph is H-free if it contains no induced subgraph isomorphic to H. We prove new complexity results for the two classical cycle transversal problems FEEDBACK VERTEX SET and ODD CYCLE TRANSVERSAL by showing that they can be solved in polynomial time... Read More about On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest.

Independent transversals versus transversals(2019)

Presentation / Conference Contribution

We compare the minimum size of a vertex cover, feedback vertex set and odd cycle transversal of a graph with the minimum size of the corresponding variants in which the transversal must be an independent set. We investigate for which graphs H the two... Read More about Independent transversals versus transversals.

On cycle transversals and their connected variants in the absence of a small linear forest(2019)

Presentation / Conference Contribution

A graph is H-free if it contains no induced subgraph isomorphic to H. We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and Odd Cycle Transversal by showing that they can be solved in polynomial time... Read More about On cycle transversals and their connected variants in the absence of a small linear forest.

Connected vertex cover for (sP1+P5)-free graphs(2019)

Journal Article

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-... Read More about Connected vertex cover for (sP1+P5)-free graphs.

Filling the complexity gaps for colouring planar and bounded degree graphs(2019)

Journal Article

A colouring of a graphGVE=( ,)is a function→cV:{1, 2,...}such that≠cucv() ()for every∈uvE.Ak‐regular list assignment ofGis a functionLwith domainVsuch that for every∈uV,Lu()is asubset of{1, 2,...}of sizek. A colouringcofGrespects ak‐regular list assi... Read More about Filling the complexity gaps for colouring planar and bounded degree graphs.

Clique-width for hereditary graph classes(2019)

Journal Article

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability: if the clique-width of a graph class G is bounded by a constant, a wide range of problems that are NP-complete in general can be shown to be po... Read More about Clique-width for hereditary graph classes.

Finding a small number of colourful components(2019)

Presentation / Conference Contribution

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy(2019)

Presentation / Conference Contribution

We almost completely resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs H1 and H2. Schweitzer settled the complexity of this problem restricted to (H1;H2)-free graphs for a... Read More about Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy.

Hereditary graph classes: when the complexities of coloring and clique cover coincide(2018)

Journal Article

graph is (H1;H2)-free for a pair of graphs H1;H2 if it contains no induced subgraph isomorphic to H1 or H2. In 2001, Král’, Kratochvíl, Tuza, and Woeginger initiated a study into the complexity of Colouring for (H1;H2)-free graphs. Since then, others... Read More about Hereditary graph classes: when the complexities of coloring and clique cover coincide.

Connected Vertex Cover for (sP1+P5)-free graphs(2018)

Presentation / Conference Contribution

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-... Read More about Connected Vertex Cover for (sP1+P5)-free graphs.

On a conjecture of Mohar concerning Kempe equivalence of regular graphs(2018)

Journal Article

Let G be a graph with a vertex colouring α. Let a and b be two colours. Then a connected component of the subgraph induced by those vertices coloured either a or b is known as a Kempe chain. A colouring of G obtained from α by swapping the colours on... Read More about On a conjecture of Mohar concerning Kempe equivalence of regular graphs.

Independent Feedback Vertex Set for P5-free Graphs(2018)

Journal Article

The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer k≥0 , to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must... Read More about Independent Feedback Vertex Set for P5-free Graphs.

Erdős–Ko–Rado theorems for a family of trees(2018)

Journal Article

A family of sets is intersecting if any two sets in the family intersect. Given a graph and an integer , let denote the family of independent sets of size of . For a vertex of , let denote the family of independent sets of size that contain . This fa... Read More about Erdős–Ko–Rado theorems for a family of trees.

Surjective H-colouring: New hardness results(2018)

Journal Article

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring p... Read More about Surjective H-colouring: New hardness results.

Enclosings of decompositions of complete multigraphs in 2-factorizations(2018)

Journal Article

Let k, m, n, λ, and μ be positive integers. A decomposition of math formula into edge-disjoint subgraphs math formula is said to be enclosed by a decomposition of math formula into edge-disjoint subgraphs math formula if math formula and, after a sui... Read More about Enclosings of decompositions of complete multigraphs in 2-factorizations.

On the price of independence for vertex cover, feedback vertex set and odd cycle transversal(2018)

Presentation / Conference Contribution

Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if w... Read More about On the price of independence for vertex cover, feedback vertex set and odd cycle transversal.

Clique-Width for Graph Classes Closed under Complementation(2017)

Presentation / Conference Contribution

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 H of forbidden induced subgraphs. We initiate a systematic study i... Read More about Clique-Width for Graph Classes Closed under Complementation.

Independent feedback vertex sets for graphs of bounded diameter(2017)

Journal Article

The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a forest. The set A in such a partition is said to be an independent feedback... Read More about Independent feedback vertex sets for graphs of bounded diameter.

Recognizing Graphs Close to Bipartite Graphs(2017)

Presentation / Conference Contribution

We continue research into a well-studied family of problems that ask if the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We let G be the class of k-de... Read More about Recognizing Graphs Close to Bipartite Graphs.

Surjective H-Colouring: new hardness results(2017)

Presentation / Conference Contribution

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring p... Read More about Surjective H-Colouring: new hardness results.

Independent Feedback Vertex Set for P5-free Graphs(2017)

Presentation / Conference Contribution

The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k ≥ 0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independen... Read More about Independent Feedback Vertex Set for P5-free Graphs.

Kempe equivalence of colourings of cubic graphs(2016)

Journal Article

Given a graph G=(V,E) and a proper vertex colouring of G, a Kempe chain is a subset of V that induces a maximal connected subgraph of G in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by ex... Read More about Kempe equivalence of colourings of cubic graphs.

The price of connectivity for cycle transversals(2016)

Journal Article

For a family of graphs F, an F-transversal of a graph G is a subset S⊆V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. Let tF(G) be the minimum size of an F-transversal of G, and View the MathML source be... Read More about The price of connectivity for cycle transversals.

Smart grid-aware scheduling in data centres(2016)

Journal Article

In several countries the expansion and establishment of renewable energies result in widely scattered and often weather-dependent energy production, decoupled from energy demand. Large, fossil-fuelled power plants are gradually replaced by many small... Read More about Smart grid-aware scheduling in data centres.

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs(2016)

Journal Article

For a positive integer k, a k-coloring of a graph inline image is a mapping inline image such that inline image whenever inline image. The COLORING problem is to decide, for a given G and k, whether a k-coloring of G exists. If k is fixed (i.e., it i... Read More about A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs.

Filling the complexity gaps for colouring planar and bounded degree graphs(2016)

Presentation / Conference Contribution

We consider a natural restriction of the List Colouring problem, k-Regular List Colouring, which corresponds to the List Colouring problem where every list has size exactly k. We give a complete classification of the complexity of k-Regular List Colo... Read More about Filling the complexity gaps for colouring planar and bounded degree graphs.

What graphs are 2-dot product graphs?(2015)

Presentation / Conference Contribution

From a set of d-dimensional vectors for some integer d ≥ 1, we obtain a d-dot product graph by letting each vector au correspond to a vertex u and by adding an edge between two vertices u and v if and only if their dot product au · av ≥ t, for some f... Read More about What graphs are 2-dot product graphs?.

Kempe equivalence of colourings of cubic graphs(2015)

Presentation / Conference Contribution

Given a graph G = (V,E) and a proper vertex colouring of G, a Kempe chain is a subset of V that induces a maximal connected subgraph of G in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by... Read More about Kempe equivalence of colourings of cubic graphs.

Narrowing the complexity gap for colouring (Cs, Pt)-free graphs(2015)

Journal Article

For a positive integer k and graph G=(V,E), a k-colouring of G is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv∈E. The k-Colouring problem is to decide, for a given G, whether a k-colouring of G exists. The k-Precolouring Extension problem... Read More about Narrowing the complexity gap for colouring (Cs, Pt)-free graphs.

A Reconfigurations Analogue of Brooks' Theorem and Its Consequences(2015)

Journal Article

Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ-coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper co... Read More about A Reconfigurations Analogue of Brooks' Theorem and Its Consequences.

Knocking out P_k-free graphs(2015)

Journal Article

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Paralle... Read More about Knocking out P_k-free graphs.

The price of connectivity for cycle transversals(2015)

Presentation / Conference Contribution

For a family of graphs F, an F-transversal of a graph G is a subset S⊆V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. Let tF(G) be the minimum size of an F-transversal of G, and ctF(G) be the minimum size... Read More about The price of connectivity for cycle transversals.

A multi-level hypergraph partitioning algorithm using rough set clustering(2015)

Book Chapter

Lotfifar, F., & Johnson, M. (2015). A multi-level hypergraph partitioning algorithm using rough set clustering. In J. Träff, S. Hunold, & F. Versaci (Eds.), Euro-Par 2015 : parallel processing : 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings (159-170). Springer Verlag. https://doi.org/10.1007/978-3-662-48096-0_13The hypergraph partitioning problem has many applications in scientific computing and provides a more accurate inter-processor communication model for distributed systems than the equivalent graph problem. In this paper, we propose a sequential multi... Read More about A multi-level hypergraph partitioning algorithm using rough set clustering.

Finding Shortest Paths Between Graph Colourings(2015)

Journal Article

The k-colouring reconguration problem asks whether, for a given graph G, two proper k-colourings and of G, and a positive integer `, there exists a sequence of at most ` + 1 proper k-colourings of G which starts with and ends with and where successiv... Read More about Finding Shortest Paths Between Graph Colourings.

Algorithms for diversity and clustering in social networks through dot product graphs(2015)

Journal Article

In this paper, we investigate a graph-theoretical model of social networks. The dot product model assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a d -dimensional vector View... Read More about Algorithms for diversity and clustering in social networks through dot product graphs.

Smart grid-aware scheduling in data centres(2015)

Presentation / Conference Contribution

In several countries the expansion and establishment of renewable energies result in widely scattered and often weather-dependent energy production, decoupled from energy demand. Large, fossil-fuelled power plants are gradually replaced by many small... Read More about Smart grid-aware scheduling in data centres.

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs(2014)

Journal Article

A k-colouring of a graph G=(V,E) is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if t... Read More about Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs.

Finding paths between 3-colorings(2011)

Journal Article

Given a 3-colorable graph G together with two proper vertex 3-colorings α and β of G, consider the following question: is it possible to transform α into β by recoloring vertices of G one at a time, making sure that all intermediate colorings are pro... Read More about Finding paths between 3-colorings.

Obtaining online ecological colourings by generalizing first-fit(2010)

Presentation / Conference Contribution

A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vert... Read More about Obtaining online ecological colourings by generalizing first-fit.

Mixing 3-colourings in bipartite graphs(2009)

Journal Article

For a 3-colourable graph G, the 3-colour graph of G, denoted C_3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the fol... Read More about Mixing 3-colourings in bipartite graphs.

Upper bounds and algorithms for parallel knock-out numbers(2009)

Journal Article

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the... Read More about Upper bounds and algorithms for parallel knock-out numbers.

Connectedness of the graph of vertex-colourings(2008)

Journal Article

For a positive integer k and a graph G, the k-colour graph of G , Ck(G), is the graph that has the proper k-vertex-colourings of G as its vertex set, and two k -colourings are joined by an edge in Ck(G) if they differ in colour on just one vertex of... Read More about Connectedness of the graph of vertex-colourings.

Transversals of subtree hypergraphs and the source location problem in digraphs(2008)

Journal Article

A hypergraph H = (V,E) is a subtree hypergraph if there is a tree T on V such that each hyperedge of E induces a subtree of T. Since the number of edges of a subtree hypergraph can be exponential in n = |V|, one can not always expect to be able to fi... Read More about Transversals of subtree hypergraphs and the source location problem in digraphs.

Mixing 3-colourings in bipartite graphs(2007)

Journal Article

For a 3-colourable graph G, the 3-colour graph of G, denoted C3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the foll... Read More about Mixing 3-colourings in bipartite graphs.

Finding Paths between Graph Colourings: Computational Complexity and Possible Distances(2007)

Journal Article

Suppose we are given a graph G together with two proper vertex k-colourings of G, α and β. How easily can we decide whether it is possible to transform α into β by recolouring vertices of G one at a time, making sure we always have a proper k-colouri... Read More about Finding Paths between Graph Colourings: Computational Complexity and Possible Distances.

Amalgamations of factorizations of complete graphs(2007)

Journal Article

Let t be a positive integer, and let K=(k1,…,kt) and L=(l1,…,lt) be collections of nonnegative integers. A (t,K,L)-factorization of a graph is a decomposition of the graph into factors F1,…,Ft such that Fi is ki-regular and li-edge-connected. In this... Read More about Amalgamations of factorizations of complete graphs.

Cycle decompositions of the complete graph(2006)

Journal Article

The computational complexity of the parallel knock-out problem(2006)

Presentation / Conference Contribution

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.

The External Network Problem with edge- or arc-connectivity requirements(2005)

Presentation / Conference Contribution

The connectivity of a communications network can often be enhanced if the nodes are able, at some expense, to form links using an external network. In this paper, we consider the problem of how to obtain a prescribed level of connectivity with a mini... Read More about The External Network Problem with edge- or arc-connectivity requirements.

Amalgamations of factorizations of complete equipartite graphs,(2004)

Journal Article

Let t be a positive integer, and let L=(l1,…,lt) and K=(k1,…,kt) be collections of nonnegative integers. A graph has a (t,K,L) factorization if it can be represented as the edge-disjoint union of factors F1,…,Ft where, for 1it, Fi is ki-regular and a... Read More about Amalgamations of factorizations of complete equipartite graphs,.

Characterization of graphs with Hall number 2(2004)

Journal Article

Hall's condition is a simple requirement that a graph G and list assignment L must satisfy if G is to have a proper L-colouring. The Hall number of G is the smallest integer m such that whenever the lists on the vertices each has size at least m and... Read More about Characterization of graphs with Hall number 2.

An algorithm for finding factorizations of complete graphs,(2003)

Journal Article

We show how to find a decomposition of the edge set of the complete graph into regular factors where the degree and edge-connectivity of each factor is given.

Amalgamations of connected k-factorizations(2003)

Journal Article

Hilton, A., Johnson, M., Rodger, C., & Wantland, E. (2003). Amalgamations of connected k-factorizations. Journal of Combinatorial Theory, Series B, 88(2), 267-279. https://doi.org/10.1016/s0095-8956%2803%2900030-3In this paper, necessary and sufficient conditions are found for a graph with exactly one amalgamated vertex to be the amalgamation of a k-factorization of Kkn+1 in which each k-factor is connected. From this result, necessary and sufficient conditio... Read More about Amalgamations of connected k-factorizations.