\(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems (Q1177173)

The complexity class \(\Delta^ P_ 2\) is the class of problems solvable in polynomial time using oracles in \(NP\). The main result of the paper gives a fairly general class of \(\Delta^ P_ 2\)-complete problems which are of the following kind: Let \(G=(V,E)\) be a graph with a linearly ordered vertex set \(V\). For a given hereditary property \(\Pi\) on graphs find the lexicographically first maximal (lfm) subset \(U\subseteq V\) such that \(U\) induces a connected subgraph satisfying \(\Pi\). Without the connectedness condition the \(P\)-completeness of the lfm subgraph problem is known for any nontrivial polynomial-time testable property \(\Pi\). The connectedness, however, makes the problem harder, as it is shown here. The definition of the lfm connected subgraph problem for \((LFMCSP(\Pi))\) is as follows: Instance: A graph \(G=(V,E)\) with linear order on \(V\) and a vertex \(v\in V\) Question: Let \(U\) be the lfm subset of \(V\) whose induced subgraph is connected and satisfies \(\Pi\). Is then \(v\in U\)? The main result shows the following: Let \(\Pi\) be a property satisfying the following conditions: (i) \(\Pi\) is hereditary on induced subgraphs. (ii) \(\Pi\) is determined by the blocks. (iii) \(\Pi\) is nontrivial on connected graphs. (iv) \(\Pi\) is polynomial-time testable. Then \(LFMCSP(\Pi)\) is \(\Delta^ P_ 2\)-complete. The \(\Delta^ P_ 2\)-completeness of the lfm induced path problem and the \(\Delta^ P_ 2\)-completeness of the lfm rooted tree problem for directed graphs are also shown. The last problem becomes polynomial-time solvable when it is restricted to topologically sorted dags. For degree 4 the problem is \(P\)-complete and for degree 3 it is shown to be in \(NC^ 2\).