Author name cluster

Matthew Johnson 0002

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

MFCS Conference 2023 Conference Paper

Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs

Matthew Johnson 0002
Barnaby Martin
Sukanya Pandey
Daniël Paulusma
Siani Smith
Erik Jan van Leeuwen

For any finite set ℋ = {H_1, …, H_p} of graphs, a graph is ℋ-subgraph-free if it does not contain any of H_1, …, H_p as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity can be classified on classes of ℋ-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most 3 and examine their complexity on H-subgraph-free graph classes where H is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree 3. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.

Details

MFCS Conference 2018 Conference Paper

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

Konrad K. Dabrowski
Matthew Johnson 0002
Giacomo Paesani
Daniël Paulusma
Viktor Zamaraev

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 we require that they are independent; that is, what is the price of independence? If G has a vertex cover, feedback vertex set or odd cycle transversal that is an independent set, then we let, respectively, ivc(G), ifvs(G) or ioct(G) denote the minimum size of such a set. We investigate for which graphs H the values of ivc(G), ifvs(G) and ioct(G) are bounded in terms of vc(G), fvs(G) and oct(G), respectively, when the graph G belongs to the class of H-free graphs. We find complete classifications for vertex cover and feedback vertex set and an almost complete classification for odd cycle transversal (subject to three non-equivalent open cases).

Details

MFCS Conference 2017 Conference Paper

Clique-Width for Graph Classes Closed under Complementation

Alexandre Blanché
Konrad K. Dabrowski
Matthew Johnson 0002
Vadim V. Lozin
Daniël Paulusma
Viktor Zamaraev

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 into the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the |H|=1 case by classifying the boundedness of clique-width for every set H of self-complementary graphs. We then completely settle the |H|=2 case. In particular, we determine one new class of (H1, complement of H1)-free graphs of bounded clique-width (as a side effect, this leaves only six classes of (H1, H2)-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the |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 F of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for ({H1, complement of H1} + F)-free graphs coincides with the one for the |H|=2 case if and only if 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 COLOURING.

Details

MFCS Conference 2017 Conference Paper

Recognizing Graphs Close to Bipartite Graphs

Marthe Bonamy
Konrad K. Dabrowski
Carl Feghali
Matthew Johnson 0002
Daniël Paulusma

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-degenerate graphs. The problem is known to be polynomial-time solvable if k=0 (bipartite graphs) and NP-complete if k=1 (near-bipartite graphs) even for graphs of diameter 4, as shown by Yang and Yuan, who also proved polynomial-time solvability for graphs of diameter 2. We show that recognizing near-bipartite graphs of diameter 3 is NP-complete resolving their open problem. To answer another open problem, we consider graphs of maximum degree D on n vertices. We show how to find A and B in O(n) time for k=1 and D=3, and in O(n^2) time for k >= 2 and D >= 4. These results also provide an algorithmic version of a result of Catlin [JCTB, 1979] and enable us to complete the complexity classification of another problem: finding a path in the vertex colouring reconfiguration graph between two given k-colourings of a graph of bounded maximum degree.

Details