2026-08-21T18:34:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27474 2026-08-21T14:42:41Z ddc:004 open_access

The Complexity of Edge-Induced Greedy Subgraph Building Algorithms Within P Hassan, Zohair Raza Hemaspaandra, Edith P-completeness parallelizability lexicographically first edge problems A common approach used to efficiently solve problems is to develop sequential greedy algorithms. Such algorithms are easily implemented and provide polynomial-time solutions. A natural next step towards building more efficient algorithms is to develop parallel algorithms. However, sequential greedy algorithms seldom lead to parallel algorithms; computing the output of sequential greedy algorithms is often shown to be P-complete and thus "inherently sequential" under the commonly believed assumption that P ≠ NC, where NC is the class of efficiently parallelizable problems. Greedy edge-induced (resp., vertex-induced) subgraph building algorithms for a property π operate like so. For given graph G, a subgraph of G is built by adding edges (resp., vertices) in a given order unless the inclusion of said edge (resp., vertex) would contradict property π within the subgraph. For vertex-induced greedy subgraph building algorithms, Miyano (1989) provided a comprehensive result: computing the subgraph output by such algorithms is typically P-complete. In contrast, little is known about its edge-induced counterpart. In this work, we analyze the complexity of the Lexicographically First Maximal H-free edge-induced subgraph problem, which is concerned with computing the output of greedy edge-induced subgraph building algorithms where the property π is that the subgraph is H-free. This gives us insight into the largely overlooked edge-induced versions of greedy subgraph building algorithms and into how graph structure influences the complexity of such algorithms. Our primary contribution is a trichotomy theorem for the cases where H is a tree: we show that the problem is either P-complete, CC-complete, or in L, where CC is the class of problems solvable using comparator circuits - or, equivalently, problems reducible to the lexicographically first maximal matching problem. In contrast, the vertex-induced version is either P-complete or in L, and such dichotomy theorems are much more common. Our additional technical contributions include: (1) an iterative approach to hardness proofs by focusing on a set of "smaller" problems and extending hardness via simple constructions, and (2) expanding on the scarce set of problems known to be CC-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zohair Raza Hassan and Edith Hemaspaandra 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.92 urn:nbn:de:0030-drops-274745 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.92 eng https://creativecommons.org/licenses/by/4.0/legalcode