Dekel Tsur

In the 3-Leaf Power Vertex Deletion (resp., 3-Leaf Power Edge Deletion ) problem, the input is a graph G and an integer k , and the goal is to decide whether there is a set of at most k vertices (resp., edges) whose removal from G results in a graph that is a 3-leaf power. In this paper we give $$O^*(4.237^k)$$ -time algorithms for 3-Leaf Power Vertex Deletion and 3-Leaf Power Edge Deletion .

In the A -Multi3-Hitting Set problem (A-M3HS), where $$A \subseteq \{1,2,3\}$$ A ⊆ { 1 , 2 , 3 } , the input is a hypergraph G in which the hyperedges have sizes at most 3 and an integer k, and the goal is to decide if there is a set S of at most k vertices such that $$|S \cap e| \in A$$ | S ∩ e | ∈ A for every hyperedge e. In this paper we give $$O^*(2.027^k)$$ O ∗ ( 2 . 027 k ) -time algorithms for $$\{1\}$$ { 1 } -M3HS and $$\{1,3\}$$ { 1 , 3 } -M3HS, and an $$O^*(1.381^k)$$ O ∗ ( 1 . 381 k ) -time algorithm for $$\{2\}$$ { 2 } -M3HS.

In the 3-Hitting Set problem, the input is a hypergraph $G$ such that the size of every hyperedge of $G$ is at most 3, and an integers $k$, and the goal is to decide whether there is a set $S$ of at most $k$ vertices such that every hyperedge of $G$ contains at least one vertex from $S$. In this paper we give an $O^*(2.0409^k)$-time algorithm for 3-Hitting Set.