On the König deficiency of zero-reducible graphs

In a recent paper, Levit and Mandrescu (2016) have given an interesting characterization of graphs having a unique perfect matching and satisfying the König property at the same time. Such graphs are exactly the ones that can be reduced to the empty graph by a simple leaf elimination procedure. The procedure can be implemented in linear time. This result is in line with our conjecture (Bartha and Krész 2010) that the property of having a unique perfect matching is decidable for all graphs in linear time. The König property is, however, too restrictive even for the class of graphs having a unique perfect matching (UPM graphs, for short), which class is already very small to begin with.

In this paper we add a second component, called line reduction, to the leaf elimination procedure. Line reduction, which has been studied by Bartha and Krész (2006, 2009), also preserves the number of perfect matchings and has a linear-time implementation. It is therefore natural to combine leaf elimination with line reduction and see if the resulting reduction can still be implemented in linear time. We give a positive answer to this question in Sect. 4, thus obtaining a larger subclass of UPM graphs that is still decidable in linear time. This class consists of graphs that can be reduced to the empty graph by the help of the combined reduction. Such graphs will be called zero-reducible.

We also investigate the possibility whether, on the analogy of the main result of Levit and Mandrescu (2016), one could come up with a characterization of zero-reducible graphs in terms of the König property. Unfortunately it turns out that such a characterization is not likely to exist. Moreover, in Sect. 5 we prove that the problem of finding the independence number of zero-reducible graphs is still NP-complete. Finally, in Sect. 6 we consider graphs that have a unique near-perfect matching, that is, graphs with a vertex v such that \(G-v\) has a unique perfect matching. We call these graphs almost UPM, and extend the Levit and Mandrescu type characterization of UPM graphs having the König property to almost UPM graphs having the König property.

Throughout the paper, we are going to follow the terminology and notation of Lovász and Plummer (1986) concerning elementary concepts in graph theory. Let \(G=(V(G),E(G))\) be an undirected graph. Our concern is with the relationship between the numbers \(\nu (G)\) (the matching number of G), \(\tau (G)\) (the vertex covering number of G), and \(\alpha (G)\) (the independence number of G) in the light of a reduction procedure which has the power to substantially simplify graphs. Two properties of graphs will be of distinguished interest for us. The so called König property (also known as the König–Egervári property), and the property of having a unique perfect matching, abbreviated as the UPM property. By definition, graph G has the König property if \(\nu (G)=\tau (G)\). It is known that \(\nu (G)\le \tau (G)\) for all graphs G. Also, \(\alpha (G)=|V(G)|-\tau (G)\), since the maximum independent sets of G are exactly the complements of the minimum vertex covers. Thus, \(\alpha (G) + \nu (G) \le |V(G)|\) with the two sides being equal iff G has the König property. We introduce the numberas the König deficiency of G.

For any \(v\in V(G)\), \(G-v\) stands for the graph obtained from G by deleting vertex v together with all the edges incident with v. By definition (Gallai 1963), a graph G is factor-critical if \(G-v\) has a perfect matching for each \(v\in V(G)\). A perfect matching of \(G-v\) is then called a near-perfect matching of G. In our discussion we shall use the so called Gallai-Edmonds decomposition (G-E decomposition, for short) of graphs (Edmonds 1965; Gallai 1964; Lovász and Plummer 1986), which splits the set \(V(G)\) into three disjoint subsets D(G), A(G), and C(G) as follows.According to the Gallai-Edmonds Structure Theorem, each connected component of the subgraph of G spanned by D(G) is factor critical, and the subgraph spanned by C(G) has a perfect matching. Moreover, every maximum matching of G composes of:The number of vertices ultimately left uncovered in D(G) is invariant, and is called the (matching-) deficiency of G.

The following two results are quoted from Lovász and Plummer (1986).

Notice that D(G) being an independent set is equivalent to the fact that each factor-critical component spanned by D(G) is a single vertex.

Recall that a nice subgraph of G is a subgraph \(G'\) having a perfect matching \(M'\) that can be extended to one of G.

The third result, due to Kotzig (1959), is still the most powerful one in the study of UPM graphs. We quote the result as stated in Lovász and Plummer (1986, Theorem 5.3.10). The result allows UPM graphs to be demolished by successively removing certain cut edges from it. Recall that a cut edgee in G is one the removal of which disconnects the component of G containing e.

Now we turn to a brief overview of the second fundamental concept used in the paper. An abstract reduction system (Derschowitz and Jouannaud 1990) consists of a set A and a finite number of irreflexive binary relations \(R_1, \ldots , R_n\) over A. It is customary to write \(a\rightarrow _{R_i} b\) for \((a,b)\in R_i\). The reduction is carried out by the relation \(R=\cup _i R_i\) in such a way that a reduces to b if \(a\rightarrow _R^* b\). The relation \(\rightarrow _R ^*\) denotes the reflexive and transitive closure of \(\rightarrow _R\). It is generally not required that \(\rightarrow _R\) be antisymmetric, even though in our case it will be. An element \(a\in A\) is called irreducible or minimal if there exists no \(b\in A\) such that \(a\rightarrow _R b\). (Remember that R is irreflexive.) Let us agree that we simply write \(\rightarrow \) for \(\rightarrow _R\) if R is understood.

Reduction R is confluent (has the Church-Rosser or diamond property) if, for every \(a,b,c\in A\), \(a\rightarrow b\) and \(a\rightarrow c\) imply that \(b\rightarrow ^*d\) and \(c\rightarrow ^* d\) for an appropriate \(d\in A\). Confluence is a vital property with regard to finding irreducible elements in abstract reduction systems. It says that, if \(a\in A\) can be reduced in two different ways: \(a\rightarrow b\) and \(a\rightarrow c\), then b and c can further be reduced (possibly in several steps) to a common element \(d\in A\). A terminating system is one in which there exists no infinite chain \(a_0\rightarrow a_1 \rightarrow \ldots \) of reductions. Notice that termination implies the antisymmetry of \(\rightarrow ^*\). As it is well-known, in a confluent and terminating system every element \(a\in A\) reduces to a unique minimal one \({\hat{a}}\). This minimal element is common to all \(b\in A\) such that \(a \leftrightarrow ^*b\).

In this section we introduce a confluent and terminating reduction system on graphs, operating with only two component reductions: leaf reduction and line reduction. As mentioned in Sect. 1, both components have been studied earlier separately in Levit and Mandrescu (2016) and Bartha and Krész (2006, 2009), respectively, and it has been observed that they preserve the number of perfect matchings in graphs. Moreover, leaf reduction (elimination) preserves the König deficiency as well.

By the usual terminology, the unique edge \(e=(v,u)\) incident with a leaf v is called pendant. Deleting an edge, together with both of its endpoints, is generally referred to as exploding the edge. Thus, one leaf reduction step amounts to exploding a pendant edge in G. Clearly, leaf reduction by itself is a confluent and terminating reduction system on the set of (isomorphism classes of) graphs. It is also clear that leaf reduction preserves the number of perfect matchings in G, but not necessarily the number of maximum matchings in general. Indeed, every perfect matching of G must cover any leaf with its pendant edge.

From this point on, by a graph we shall mean a multigraph having no loops. Leaf reduction works naturally for multigraphs as well, and the observation in the previous paragraph on the number of perfect matchings remains true.

Recall that a subdividing vertex in \(V(G)\) is one having exactly two neighbors, to which it is connected by a single edge. Let \(c\in V(G)\) be a subdividing vertex in G that is adjacent to the (necessarily distinct) vertices \(f_1\) and \(f_2\). The triple \(r=(f_1,c,f_2)\) is called a redex with centerc and focuses\(f_1\), \(f_2\).

To be precise, by merging \(f_1\) and \(f_2\) we mean deleting these two vertices from G and replacing them with a new vertex f in \(G'\) such that for every vertex \(v\in V(G)\cap V(G')\), \((f,v)\in E(G')\) iff \((f_1,v)\in E(G)\) or \((f_2,v)\in E(G))\). By this definition, multiplicities of the edges incident with the merged vertices are added up.

Line reduction by itself is also confluent and terminating (Bartha and Krész 2006), and it preserves the number of perfect matchings, too.

Since both \(\rightarrow _\mathbf{f}\) and \(\rightarrow _\mathbf{l}\) are terminating, Theorem 4 implies that every graph G can be reduced to a unique minimal graph \({\hat{G}}\) free from leaves and redexes. If G has a perfect matching, then the number of perfect matchings in \({\hat{G}}\) is the same as in G.

Now we investigate the relationship between reduction and the König property.

Proposition 2 implies that \(\rightarrow _\mathbf{l}\) preserves the König property, but not the König deficiency in general. Our next theorem is in fact a refinement of Proposition 2. Let \({\bar{H}}\) denote the graph obtained from the graph H in Fig. 1a by deleting the vertices \(v_1\) and \(v_2\). The leaf vertex popping up in \({\bar{H}}\) is then called unsafe. In general, a vertex \(u\in V(G)\) in an arbitrary graph G is unsafe if an instance of \({\bar{H}}\) with possible even subdivisions on its edges can be pasted on G as a subgraph, so that the unsafe vertex of \({\bar{H}}\) coincides with u. If G has a perfect matching, then an unsafe vertex v is nice if the UPM of \({\bar{H}}\) (with its possible subdivisions) can be extended to a perfect matching of G.

How efficiently can reduction be implemented by an algorithm? This is an important question, since the reduction may substantially decrease the size of the graph, so it could be used as a preamble to some other graph algorithms having a more significant time complexity. Two obvious examples are finding the number of perfect matchings in a graph and deciding if a graph has the König property. The latter example could use Theorem 5 above as a theoretical basis. Other application areas have been mentioned in Bartha and Krész (2009). Line reduction, as described in Bartha and Krész (2009), has been successfully applied in the search of maximum matchings (Korenwein et al. 2018) using parameterized complexity analysis as a theoretical measure, backed up by an experimental study showing a significant speed-up in implementation.

Along this line one may even hope for a polynomial-time algorithm for calculating the König deficiency of graphs that can be reduced to the empty graph. As introduced in Sect. 1, such graphs are called zero-reducible. Indeed, while reversing the steps of the reduction, one might think that a suitable maximum independent set or minimum vertex cover could gradually be built up from scratch for the graph. This appears to be likely, since the class of zero-reducible graphs is just a narrow subclass of the class of UPM graphs, which is already very restricted itself. Disappointingly, however, we are going to show in Section 4 that finding the König deficiency of a zero-reducible graph is an NP-hard problem.

As it is customary in complexity analyses concerning graphs, n and m will stand for the number of vertices and edges in graphs, respectively. If the basis of the reduction is just \(\rightarrow _\mathbf{f}\), then graphs reducible to the empty graph are called zero-leaf-reducible. Leaf reduction by itself can be carried out by a straightforward linear-time (\({\mathcal {O}}(m)\)) algorithm. For a concrete implementation, see Levit and Mandrescu (2016). Thus, zero-leaf-reducibility of graphs is decidable in linear time. Performing line reduction (i.e., obtaining the minimal graph for an input graph G) is a much more complicated issue. A true linear-time algorithm has been worked out for this problem in (Bartha and Krész 2009), building on a single bottom-up pass of a depth-first tree constructed for G. In fact, the algorithm is akin to the so called static tree set union implementation (Gabow and Tarjan 1985) of the well-known union-find problem, where the structure of unions to be performed is known in advance.

Unfortunately, the algorithm in Bartha and Krész (2009) cannot directly be adopted to accommodate leaf reduction. The problem is that, when deleting the vertex adjacent to a leaf, the depth-first tree keeping track of the redex information will fall, and it must be reconstructed. The extra cost incurred is of course intolerable. For this reason, in the present paper we take a completely different approach to implement reduction, even though we firmly believe that the original depth-first algorithm can be fixed somehow to accommodate leaf reduction just by “patching up” the base tree whenever needed. We shall return to this issue shortly.

Our present solution is based on the standard union-find technique by Tarjan (1975) to implement the dynamic union of disjoint sets forming a partition of a given universe set A. For the sake of implementation, A is identified with the set \(\{1,\ldots ,n\}\), and each group S of the current partition is identified by a canonical representant \(i\in S\). Starting from the trivial partition of n groups, one can perform the union of two groups, or find out the (canonical representant of the) group [i] in which a given element i resides. The goal is to keep track of the partitioning information in such a way that the amortized cost of one operation (either union or find) becomes minimal. The concrete description and implementation of different union-find techniques can be found in most undergraduate textbooks on algorithms. The reader is referred e.g. to Sedgewick and Wayne (2011) for a detailed study of this matter.

The fastest way to implement union-find is the so called quick union with path compression method, originally introduced by Tarjan (1975). Groups in the current partition are structured as trees, and the weighted quick-union rule joins the tree of the smaller group to the tree of the larger one as a subtree attached to the root. Path compression means that, whenever a find(i) operation is performed, a pointer is introduced from node i to the root r of the tree that i resides in. Moreover, to speed up subsequent find’s, the pointer to r will be added (and later updated) to each node along the branch from i to r as part of the find(i) operation, which will actually visit these nodes. See Sedgewick and Wayne (2011) for details.

It was shown in Tarjan (1975) that the time required to execute \(m\ge n\) find operations and at most \(n-1\) intermixed unions by this implementation is \({\mathcal {O}}(m\cdot \alpha (m,n))\), where the two-variable function \(\alpha \) (not to be confused with the independence number \(\alpha \)) is related to the functional inverse of the Ackermann function and is very slow growing. The actual definition of \(\alpha \) is complicated (see Tarjan 1975), but the value of \(\alpha (m,n)\) is claimed to remain under 3 for all practical purposes. For this reason, the union-find technique is said to be practically linear-time.

Our idea is to implement the shrinking of a graph G along a redex \(r=(f_1,c,f_2)\) by creating a meta-graph \({\bar{G}}\) having a meta-vertex \(f=\{f_1,f_2\}\), the adjacency list of which is the join of \(f_1\)’s and \(f_2\)’s adjacency lists, excluding the edges between \(f_1\) and \(f_2\). We then proceed iteratively, combining and deleting meta-vertices as the reduction requires. In each step, the meta-vertices of the current meta-graph \({\bar{G}}\) form a partition of V(G), which partition is maintained by union-find. There is one catch, however, which must be avoided. One cannot calculate the exact adjacency list of each newly created meta-vertex, because this would require the full scan of both component adjacency lists to see if there are any edges to be dropped. The cumulative impact of this scan on the overall complexity of the algorithm would of course be fatal. On the other hand, we need to recognize if a meta-vertex becomes a leaf or the center of a redex, that is, its degree becomes 1 or 2. The trick to solve this dilemma is simple. The adjacency lists of the two components of a union will only be joined formally, leaving in the so called “redundant” edges connecting the two focuses, which will be screened out gradually later. We then use a function Check() to perform a smart garbage collection every time a meta-vertex is involved in a reduction step to see if the degree of the meta-vertex has reached 2. The details are as follows.

Algorithm 1. The algorithm maintains a list of meta-leaves Leaves, and a list of meta-redex-centers Redexes. Each vertex on Leaves and Redexes is the canonical representant of the corresponding meta-vertex as a non-empty subset of V(G). As long as either Leaves or Redexes in not empty, the algorithm executes either Step (a) or Step (b), with priority given to Step (a).

Step (a)Step (b)The description of the function Check() is as follows.

Check(v), vertex v, returns integer;Analysis of Algorithm 1

Every time it is invoked, the garbage collector method Check() will check if the argument vertex v has become a leaf or redex-center. It does so by identifying some of the redundant edges incident with v. The method scans v’s adjacency list from the beginning and removes every vertex corresponding to a redundant edge until the list is out or more than two non-redundant edges have been found. The number of find operations during the call is therefore at most three greater than the number of redundant edges found. The actual redundancy of an edge will be detected at most once during the algorithm (not from both endpoints, that is), because an edge becomes redundant if one of its endpoints has been deleted or the two endpoints are joined. For this reason, the total number of find operations inside some Check() during the whole algorithm is \(m+3C\), where C is the number of Check() calls.

We claim that \(C\le m\). Indeed, every Check(v) call, either in Step (a) or Step (b), can be associated with the vertex v “losing” one or more degrees, that is, having one or more vertices on v’s adjacency list which has just been deleted. In Step (a3), \({\bar{w}}\) is adjacent to some vertex in \([{\bar{u}}]\) that is being deleted. In Step (b7), f represents the union of \({\bar{f}}_1\) and \({\bar{f}}_2\), each of which is losing a degree by deleting the center c. Consequently, the number of Check() calls cannot exceed m, the number of edges in G. (Mind v’s neighbor that is being deleted, therefore it is losing all of its degrees.)

Other than the find s inside Check(), Step (a) and Step (b) together will perform at most mfind operations in total. Thus, the grand total of find s is at most \(3m+m+m = 5m\), and the total number of union s is at most \(n-1\). Any other cost will clearly remain under the \({\mathcal {O}}(m)\) bound. The overall time complexity of the algorithm is therefore\(\square \)

Now we return to the question of finding a true linear-time algorithm for reduction. As we have indicated above, the problem is related to the issue of deleting edges from the graph and still being able to maintain a fixed data structure that shows e.g. the cut edges of the graph and/or some other information. This general problem is known in the literature by the name decremental dynamic connectivity. Edges are deleted one-by-one and in the meantime queries are made about the graph being connected or not. It is somewhat more difficult to display the set of cut edges than to show the set of connected components as an answer to a query. Of course, one would hope for an implementation of decremental dynamic connectivity by which the amortized cost of one operation (delete an edge or display the components/cut edges) is constant. Unfortunately, no such implementation exists at present. The best solution for decremental dynamic connectivity uses \({\mathcal {O}}(\log n(\log \log n)^3)\) time (on a pointer machine) for connectivity queries (Thorup 2000) and \({\mathcal {O}}(\log ^4 n)\) time for cut-edge queries (Gabow et al. 2001). Both methods employ search as a fundamental tool.

We believe that an amortized constant-time implementation exists for decremental dynamic connectivity, which solution is structural, rather than search-based. Such a solution would bring the well-known reverse delete minimum spanning tree algorithm in line with Kruskal’s one in the sense that both would require \({\mathcal {O}}(m)\) time only, provided that the set of edges has previously been sorted according to weights. As for now, however, even a \({\mathcal {O}}(\log n)\)-time solution for decremental dynamic connectivity would be a breakthrough result. Other than an efficient implementation for reverse delete, it would also provide an algorithm to decide the UPM property of graphs in \({\mathcal {O}}(m\log n)\) time. Due to Theorem 3, this problem is a special case of decremental dynamic connectivity with cut edge queries, hence the projected \({\mathcal {O}}(m\log n)\) time complexity. Our conjecture is, however, that the UPM decision problem can be tackled by an \({\mathcal {O}}(m)\) algorithm even if general decremental dynamic connectivity fails to be constant-time. The presently fastest algorithm for deciding the UPM property is still the search-based one by Gabow et al. (2001), which uses \({\mathcal {O}}(m\log ^4n)\) time. Needless to say, a structural type constant-time decremental dynamic connectivity implementation would also support a true \({\mathcal {O}}(m)\)-time reduction algorithm to implement our combined leaf-and-line reduction procedure.

We start out by providing a simple alternative proof of the characterization result obtained by Levit and Mandrescu (2016) on UPM graphs having the König property. In our language, the characterization says that these graphs are exactly the zero-leaf-reducible ones.

At this point, even though it is an aside, we take the opportunity to prove a sharper version of Lovász and Plummer (1986, Corollary 5.3.14) on the maximum number of edges in a simple (i.e., no loops or multiple edges) UPM graph.

Encouraged by Corollary 1, one would expect a similar characterization of all zero-reducible graphs in terms of a tangible connection between \(\tau \) and \(\nu \). A plausible candidate is articulated in the following conjecture.

Recall that a forbidden edge of G is one that is not part of any maximum matching in G. In case of a UPM graph, these are the edges not belonging to the UPM of G.

Examples 2 and 3 show that Conjecture 1 fails in both directions. The failure of the conjecture implies that it is not possible to calculate k(G) for a zero-reducible graph G with the following simple greedy algorithm, which appears to be justified by the fact that leaf reduction preserves the König deficiency.Even if we knew the “appropriate” way to delete edges in step 2, the algorithm would still not work. It gives a wrong answer for G in Example 2, the right one for G in Example 3, but that graph is not zero-reducible.

The irreducibility of the graph G in Fig. 5c raises the following question. Why don’t we disregard the multiplicity of edges during reduction? If we did, our graph in Fig. 5c would be zero-reducible. The reason is to preserve the UPM property during reverse reduction, which could be lost by simply forgetting the multiplicity of edges. (Luckily not in the concrete example graph G, which is UPM to begin with.) Nevertheless, in the end we could still check if the UPM property was lost by de facto reversing the steps of the reduction in practically the same amount of time. This issue is therefore mainly theoretical.

Now we are ready to prove the main result of this section on the intractability of computing k(G) for a zero-reducible graph G.

Judging by the simplicity of the above proof, the reader might have the impression that the statement of Theorem 7 is trivial. In order to see how much it is not, consider the following corollary, which would be very difficult to handle in the absence of this theorem.

One can find two different definitions in the literature for a graph G to almost have the König property. The obvious one (Levit and Mandrescu 2012) is simply equivalent to the condition \(k(G)=1\). The second definition (Larson and Pepper 2011) postulates that, while G itself does not have the König property, there exists a vertex \(v\in V(G)\) for which \(G-v\) does. It is evident that the classes of graphs satisfying these two definitions are not comparable. Combining the “almost” distinction with the König and/or UPM properties, one obtains the following potential meaningful definitions. For brevity, K will stand for the König property from this point on, just like UPM abbreviates the property of having a unique perfect matching.

Since the term “almost K and UPM” is rather ambiguous, especially in the context of Definition 3, it needs further clarification. Definition 4 is about a graph G that is definitely not UPM (mind that G and \(G-v\) cannot both be UPM), \(G-v\) is K, while G itself may or may not be K. In other words, G is almost UPM with respect to some \(v\in V(G)\) (i.e., UPM disregarding v) such that \(G-v\) has the König property. To emphasize this meaning, graphs satisfying Definition 4 will rather be referred to as almost K&UPM graphs. Similarly, almost K UPM graphs will be explicitly called (K-1) UPM. In the same vein we define (K-n) UPM graphs as UPM graphs with König deficiency n, and almost (K-n)&UPM graphs as almost UPM graphs G with respect to some vertex \(v\in V(G)\) such that \(G-v\) has König deficiency n. Notice that, e.g. a (K-1) and almost UPM graph can be either almost K&UPM or almost (K-1)&UPM (but not both, of course).

As a further notational convenience, we identify an almost UPM graph as a pointed graph (G, v), indicating the vertex \(v\in V(G)\) for which \(G-v\) is UPM as the designated point in G. The point v will, however, often be omitted from this couple if it is understood or irrelevant. Clearly, the point v in an almost UPM graph G need not be unique, but in general it cannot be arbitrary either.

Our goal is to characterize (K-1) UPM graphs and almost K&UPM graphs in terms of suitable reductions. To understand the connection between these two classes of graphs, let \((G_1,v_1)\) and \((G_2,v_2)\) be two almost UPM graphs with designated points \(v_1\) and \(v_2\), and construct the UPM graph G by taking the disjoint union of \(G_1\) and \(G_2\) and connecting \(v_1\) with \(v_2\) by a (matching-) positive cut edge.

If G is K, then of course both \(G_1-v_1\) and \(G_2-v_2\) must be K and UPM. (Remember the proof of Lemma 1.) Therefore \(G_i\) (\(i=1,2\)) is almost K&UPM. Conversely, if \(G_1-v_1\) and \(G_2-v_2\) are K, then G is either K or K-1, depending on whether one of \(v_1\) or \(v_2\) could be “squeezed in” as a further independent vertex in the union \(S_1\cup S_2\) of appropriate maximum independent sets \(S_i\) of \(G_i\) (\(i=1,2\)).

If G is K-1, then the following cases are possible.

See Fig. 7 for a graphical summary of these cases. In the figure, circles identify mandatory independent vertices, ones that must be present in every maximum independent set of G. A dashed circle means that the vertex may or may not be mandatory independent in the respective half of the graph, but when it is, it will be lost during the overall count.

An immediate conclusion of the analysis above is that every simple (K-1) UPM graph G has at least one subdividing or leaf vertex. Indeed, by Lemma 1, every K UPM graph, as “one half” \(G_1\) or \(G_2\) of G, has a leaf v, which might turn into a subdividing vertex when connecting it to either \(v_1\) or \(v_2\) according to the decomposition by Fig. 7. By the same token, every almost K&UPM graph, too, has a subdividing or leaf vertex. Along these lines, the characterization of almost K&UPM graphs in terms of reduction is the key to the characterization of (K-1) UPM graphs, which then leads to a linear-time decision algorithm for these graphs. Moving on, we hope to have a similar characterization for (K-2) UPM graphs through a characterization of almost (K-1)&UPM graphs, so we could decide the (K-2) UPM property as well in linear time. Unfortunately one cannot continue this line of reasoning for (K-3) UPM graphs, since these graphs do not necessarily have a subdividing vertex or leaf. See Fig. 8 for the smallest UPM graph with no multiple edges that is free from subdividing vertices and leaves, and verify that \(k(G)=3\), indeed. Nevertheless, a case-by-case analysis according to the decomposition outlined in Fig. 7 can be carried out for all UPM graphs relating to their König deficiency. Such an analysis suggests an inductive method to calculate k(G) for an arbitrary UPM graph G. We know by Theorem 7, however, that this method is not likely to result in an exact polynomial-time algorithm.

In the present study we deal with the characterization of K and almost UPM graphs only, leaving the rest of the work to a forthcoming paper. Clearly, if (G, v) is such a graph, then v must be mandatory independent. Moreover, \(G-v\) is still K. See Fig. 7A, top half.

Notice that the leaf vertex presented in the above proof is different from v. Therefore we also have a simple reduction algorithm to decide if a pointed graph (G, v) is K and almost UPM (with respect to v, that is). In other words, we have the following corollary.

Using Theorem 8 and Corollary 4 one can easily decide in linear time if a graph G (pointed graph (G, v)) is K and almost UPM. It is still an interesting open question, however, if one can design a linear-time algorithm to find the set of all points v for which a graph (G, v) is K and almost UPM.

Motivated by the characterization (Levit and Mandrescu 2016) of UPM graphs having the König property, we have introduced a confluent and terminating reduction system on graphs, and shown that this reduction can be carried out in practically linear time. As a consequence, zero-reducible graphs, forming a substantial subclass of UPM graphs, are decidable in linear time. We have also given a necessary and sufficient condition for the König property to be preserved in one inverse reduction step. As a negative result, we have proved that the problem of finding the König deficiency of a zero-reducible graph is NP-complete. Finally, we have generalized the Levit and Mandrescu type characterization to almost UPM graphs having the König property.