Yota Otachi
• Member for 11 years, 3 months
• Last seen this week

126 views

The famous graph (the complement of the disjoint union of $n/3$ triangles) with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ as an induced subgraph. ...

141 views

The problem is polynomial-time solvable. Observe that we have to pick exactly one vertex from each color class to form a $k$-clique. If there is a vertex $x \in V_{i}$ that has no neighbor in some $V_{... View answer 1 answers 5 votes 200 views Accepted answer 9 votes To Question 1: The graphs induced by such edge sets are known as pseudoforests. As your proof of the membership to #P implies, an edge set is the image of a selection function if and only if the graph ... View answer 1 answers 6 votes 336 views Accepted answer 9 votes Your parameter "naive treewidth" is known as tree-partition-width in the literature. It is known that if a graph has constant treewidth and constant maximum degree, then it has constant tree-partition-... View answer 2 answers 6 votes 179 views Accepted answer 8 votes I think the following example with four points answers your question (though it gives multi-sets of distances). See Reconstructing Sets From Interpoint Distances by Skiena, Smith, and Lemke for more ... View answer 1 answers 16 votes 732 views Accepted answer 14 votes I don't have a complete answer, but I think both problems are open. The paper by Jajcay, Malni&#x10D;, Maru&scaron;i&#x10D; [3] is related to your first question. They provide some tools to test ... View answer 3 answers 16 votes 457 views Accepted answer 25 votes Your first problem is the hypergraph transversal problem (aka the HITTING SET problem). The second problem is the FEEDBACK VERTEX&nbsp;SET problem. Both the problems are NP-complete. View answer 1 answers 15 votes 480 views Accepted answer 7 votes Your problem is Maximum Common Edge Subgraph Problem (Max CES) defined as follows: given two graphs$G$and$G'$, find a graph$H$with the maximum number of edges that is isomorphic to a subgraph of$...

534 views

There is a linear-time algorithm for determining the prime factors of connected graphs with respect to the Cartesian product. See the paper by Imrich and Peterin.

348 views
The bandwidth problem is $W[t]$-hard for all $t$. It was shown by Bodlaender et al. in "Beyond NP-completeness for problems of bounded width." See the paper. On the other hand, it is also known that ...
The pathwidth of $P^3_k$ can be determined as a corollary to some known results. FitzGerald [2] showed that the bandwidth of $P^3_k$ is $\lfloor \frac{3}{4} k^{2} + \frac{1}{2} k \rfloor$. Harper [3] ...