Faster, higher, easier: Toward a systematic study of parameterized vertex and edge selection problems

Abstract

We consider the decision and counting versions of the two problem families Λ-Factor and (σ,ρ)-DomSet which generalize Matching, Dominating Set, and Independent Set for suitable choices of sets Λ, σ, and ρ of non-negative integers. For Λ-Factor, for a given graph G, the goal is to find a set of edges S ⊆ E(G) such that, for every vertex v, the number of incident edges from S is contained in Λ. For (σ,ρ)-DomSet, for a given graph G, the goal is to find a set of vertices S ⊆ V(G) such that, for every vertex in S, the number of adjacent vertices in S is contained in σ and, for every vertex not contained in S, the number of adjacent vertices in S is contained in ρ. We restrict ourselves to the cases when Λ, σ, and ρ are finite or cofinite and prove efficient algorithms for the two problem families parameterized by treewidth. We complement these algorithmic results by conditional lower bounds, which are based on a variant of the Strong Exponential-Time Hypothesis, to prove that the algorithms are optimal in most cases. When the cofinite sets exclude only few degrees, we additionally parameterize by the number of forbidden values and provide improved algorithmic results. We extend the general algorithms to the counting versions and provide matching lower bounds for this setting.

In dieser Arbeit betrachten wir die Entschiedungs- und Zählvarianten von Λ-Factor und (σ,ρ)-DomSet. Abhängig von den Mengen Λ, σ und ρ von nicht-negativen Zahlen, erfassen wir damit unter anderem Matching, Independent Set oder Dominating Set. Das Ziel von Λ-Factor ist, für einen gegebenen Graphen G eine Kantenmenge S ⊆ E(G) zu finden, sodass für jeden Knoten v die Anzahl der angrenzenden Kanten in S in Λ liegt. Das Ziel von (σ,ρ)-DomSet ist, für einen gegebenen Graphen G eine Knotenmenge S ⊆ V(G) zu finden, sodass für jeden Knoten v in S die Zahl der Nachbarn in S in σ liegt und für jeden Knoten v, der nicht in S liegt, die Zahl der Nachbarn in S in ρ liegt. Wenn die Mengen Λ, σ und ρ oder ihre Komplemente zu ℕ endlich sind, geben wir durch eine Parametrisierung anhand der Baumweite (treewidth) effiziente Algorithmen für beide obigen Problemfamilien an. Mit bedingten unteren Schranken basierend auf einer Variante der Starken Exponentialzeit Hypothese (SETH) beweisen wir, dass unsere Programme annähernd optimal sind. Wenn extrem wenige Grade verboten sind, parametrisieren wir (zusätzlich zur Baumweite) anhand dieser Zahl und ermöglichen so einen deutlich besseren Algorithmus. Wir erweitern die Beweise auf die Zählvarianten der betrachteten Probleme und zeigen, dass die Algorithmen in diese Fällen optimal (in Abhängigkeit von der Baumweite) sind.